University of Wyoming
Browse
UGRD_2010_Spring_Heimbuck_Karl.pdf (602.72 kB)

Lucas Sequences in Primality Testing

Download (602.72 kB)
presentation
posted on 2021-11-15, 18:41 authored by Karl Heimbuck
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.

History

Advisor

Mueller, Siguna

ISO

eng

Language

English

Publisher

University of Wyoming. Libraries

Department

  • Library Sciences - LIBS

Usage metrics

    UGRD 2010

    Keywords

    Licence

    Exports