Fast algorithms for LUC digital signature computation

Recently, a digital signature scheme based on a special type of Lucas function has been proposed which is free from the multiplicative attack on the RSA digital signature (P. Smith and M. Lennon, 1993). A disadvantage of this new digital signature scheme LUC is that it takes more computation than the RSA does. An important property, V(x+y)=V(x)×V(y)-V(x-y), of this special type of Lucas function is exploited to develop fast algorithms to make the LUC digital signature perform more efficiently. A parallel architecture for the proposed fast algorithms is developed. Besides the fast algorithm constructions, the paper shows that there exist many similar computational and mathematical aspects between the exponentiation and the special type of Lucas function considered