Efficient computation of full Lucas sequences

Recently, Yen and Laih (see IEE Poc. Comput. Digit. Tech., vol. 142, no. 2, p. 165-9, 1995) proposed an algorithm to compute LUC digital signatures quickly. This signature is based on a special type of Lucas sequence V_k. The authors generalise their method to any type of Lucas sequence, and extend it to the `sister´ Lucas sequence, U_k . As an application, the order of an elliptic curve over GF(2^m) is computed quickly