When , the Lucas sequences and satisfy certain
Pell equations:
Relations between sequences with different parameters
For any number c, the sequences and with
have the same discriminant as and :
For any number c, we also have
Other relations
The terms of Lucas sequences satisfy relations that are generalizations of those between
Fibonacci numbers and
Lucas numbers. For example:
Divisibility properties
Among the consequences is that is a multiple of , i.e., the sequence
is a
divisibility sequence. This implies, in particular, that can be
prime only when n is prime.
Another consequence is an analog of
exponentiation by squaring that allows fast computation of for large values of n.
Moreover, if , then is a
strong divisibility sequence.
Let N be an integer
relatively prime to 2Q. If the smallest positive integer r for which N divides exists, then the set of n for which N divides is exactly the set of multiples of r.
If P and Q are
even, then are always even except .
If P is even and Q is odd, then the
parity of is the same as n and is always even.
If P is odd and Q is even, then are always odd for .
If P and Q are odd, then are even if and only if n is a multiple of 3.
A
prime factor of a term in a Lucas sequence that does not divide any earlier term in the sequence is called primitive.
Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive prime factor.[2] Indeed, Carmichael (1913) showed that if D is positive and n is not 1, 2 or 6, then has a primitive prime factor. In the case D is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte[3] shows that if n > 30, then has a primitive prime factor and determines all cases has no primitive prime factor.
Specific names
The Lucas sequences for some values of P and Q have specific names:
Lucas sequences are used in some primality proof methods, including the
Lucas–Lehmer–Riesel test, and the N+1 and hybrid N−1/N+1 methods such as those in Brillhart-Lehmer-Selfridge 1975.[4]
LUC is a
public-key cryptosystem based on Lucas sequences[5] that implements the analogs of
ElGamal (LUCELG),
Diffie–Hellman (LUCDIF), and
RSA (LUCRSA). The encryption of the message in LUC is computed as a term of certain Lucas sequence, instead of using
modular exponentiation as in RSA or Diffie–Hellman. However, a paper by Bleichenbacher et al.[6] shows that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed.
Software
Sagemath implements and as lucas_number1() and lucas_number2(), respectively.[7]
^P. J. Smith; M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117.
CiteSeerX10.1.1.32.1835.
Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (2nd ed.). Birkhäuser. pp. 107–121.
ISBN0-8176-3743-5.
When , the Lucas sequences and satisfy certain
Pell equations:
Relations between sequences with different parameters
For any number c, the sequences and with
have the same discriminant as and :
For any number c, we also have
Other relations
The terms of Lucas sequences satisfy relations that are generalizations of those between
Fibonacci numbers and
Lucas numbers. For example:
Divisibility properties
Among the consequences is that is a multiple of , i.e., the sequence
is a
divisibility sequence. This implies, in particular, that can be
prime only when n is prime.
Another consequence is an analog of
exponentiation by squaring that allows fast computation of for large values of n.
Moreover, if , then is a
strong divisibility sequence.
Let N be an integer
relatively prime to 2Q. If the smallest positive integer r for which N divides exists, then the set of n for which N divides is exactly the set of multiples of r.
If P and Q are
even, then are always even except .
If P is even and Q is odd, then the
parity of is the same as n and is always even.
If P is odd and Q is even, then are always odd for .
If P and Q are odd, then are even if and only if n is a multiple of 3.
A
prime factor of a term in a Lucas sequence that does not divide any earlier term in the sequence is called primitive.
Carmichael's theorem states that all but finitely many of the terms in a Lucas sequence have a primitive prime factor.[2] Indeed, Carmichael (1913) showed that if D is positive and n is not 1, 2 or 6, then has a primitive prime factor. In the case D is negative, a deep result of Bilu, Hanrot, Voutier and Mignotte[3] shows that if n > 30, then has a primitive prime factor and determines all cases has no primitive prime factor.
Specific names
The Lucas sequences for some values of P and Q have specific names:
Lucas sequences are used in some primality proof methods, including the
Lucas–Lehmer–Riesel test, and the N+1 and hybrid N−1/N+1 methods such as those in Brillhart-Lehmer-Selfridge 1975.[4]
LUC is a
public-key cryptosystem based on Lucas sequences[5] that implements the analogs of
ElGamal (LUCELG),
Diffie–Hellman (LUCDIF), and
RSA (LUCRSA). The encryption of the message in LUC is computed as a term of certain Lucas sequence, instead of using
modular exponentiation as in RSA or Diffie–Hellman. However, a paper by Bleichenbacher et al.[6] shows that many of the supposed security advantages of LUC over cryptosystems based on modular exponentiation are either not present, or not as substantial as claimed.
Software
Sagemath implements and as lucas_number1() and lucas_number2(), respectively.[7]
^P. J. Smith; M. J. J. Lennon (1993). "LUC: A new public key system". Proceedings of the Ninth IFIP Int. Symp. On Computer Security: 103–117.
CiteSeerX10.1.1.32.1835.
Hans Riesel (1994). Prime Numbers and Computer Methods for Factorization. Progress in Mathematics. Vol. 126 (2nd ed.). Birkhäuser. pp. 107–121.
ISBN0-8176-3743-5.