Lucas Sequences in Primality Testing

Prime or composite? This classification determines whether or not integers can be used in digital security. One such way to begin testing an integers primality is with the Fermat test, which says that if n is a prime number and a is an integer then an-1 ≡ 1 mod n. However, the Fermat test in itself is not solely sufficient as a primality test since there are composite numbers that also pass the test. Thus, there is a need to look at alternative ways to test primality. Using Lucas numbers is one such way. Given integers P and Q, a Lucas sequence is defined as the Un and Vn such that Un+1= PUn – QUn-1 and Vn+1 = PVn-QVn-1. Like the Fermat test, Lucas numbers exhibit certain characteristics for prime numbers. This research looked at ways to combine the different Lucas characteristics not only with each other but with the Fermat test in order to determine combinations which could be advantageous in primality testing.