Primality test for number n satisfying n^f -1 divisible by a large power of m.

Pedro Berrizbeitia, CU Boulder & University Simon Bolivar, Caracas, Venezuela

In the talk we will present a general theory for determining the primality of numbers n satisfying n^f - 1 is divisible by a large power of a given and relatively small positive integer m. Large means that m^s > \sqrt n (although the condition may be relaxed). The theory is based on properties of Gaussian Sums and Jacobi sums of characters of order m. A theorem of Lenstra (known as Lenstra's Theorem) is used to prove the main theoretical result of the paper. Concrete aspects of the implementation of the test are discussed for numbers n satisfying the condition for f=1, 2, 4 and for m=17.