Lucas sequence and cryptography (Q1911759)

In this paper the author recalls the definition for the Lucas sequence \(v_n (p)\). He then gives some properties of it and shows a method to calculate \(v_n(p)\) with an algorithm of complexity \(O(\log n)\). He then derives the following four properties for the sequence \[ (1) \quad v_n \circ v_m=v_{nm} \qquad (2) \quad v_n\circ v_m=v_m \circ v_n \qquad (3) \quad v_{m+1}(p) \equiv p \qquad (4) \quad v_{mr+l} (p) \equiv v_l(p). \] These four properties have a strong resemblance to the properties of the ordinary exponentiation; for instance, property one can be compared to \(\alpha^{n+m} = \alpha^n \alpha^m\). The function \(v_n(p)\) can be used as a kind of exponentiation in the ordinary discrete log based systems like Diffie-Hellman, RSA, El Gamal and DSA. The author shows this extensively. Finally he remarks that the Redei sequences have similar properties.