Recall the transformation of the state variables

*a* and

*b* in the fib-iter process of section

1.2.2:

*a* *a* +

*b* and

*b* *a*. Call this transformation

*T*, and observe that applying

*T* over and over again

*n* times, starting with 1 and 0, produces the pair

*F**i**b*(

*n* + 1) and

*F**i**b*(

*n*). In other words, the Fibonacci numbers are produced by applying

*T**n*, the

*n*th power of the transformation

*T*, starting with the pair (1,0). Now consider

*T* to be the special case of

*p* = 0 and

*q* = 1 in a family of transformations

*T**p**q* where

*T**p**q* transforms the pair (

*a*,

*b*) according to

*a* *b**q* +

*a**q* +

*a**p* and

*b* *b**p* +

*a**q*. Show that if we apply such a transformation

*T**p**q* twice, the effect is the same as using a single transformation

*T**p*'

*q*' of the same form, and compute

*p*' and

*q*' in terms of

*p* and

*q*. This gives us an explicit way to square these transformations, and thus we can compute

*T**n* using successive squaring, as in the fast-expt procedure. Put this all together to complete the following procedure, which runs in a logarithmic number of steps: