[net.math] primality test of k*2^n-1

mira@nsc.UUCP (Mira Green) (12/11/85)

I have heard that there is a special primality test for numbers of the form:

		     n
		k * 2  - 1    k,n integer and n is large

	(perhaps something similar to the special test for k=1?)

Would someone post such a method to the net?

thank you

bs@faron.UUCP (Robert D. Silverman) (12/12/85)

> I have heard that there is a special primality test for numbers of the form:
> 
> 		     n
> 		k * 2  - 1    k,n integer and n is large
> 
> 	(perhaps something similar to the special test for k=1?)
> 
> Would someone post such a method to the net?
> 
> thank you

The test is quite similar to that for 2^p-1. It uses the fact that the
factorization of (k*2^n - 1) + 1 is known. One simply constructs an
appropriate Lucas sequence and checks that the rank of apparition of the
number you are testing in that sequence has the correct value. See,
for example, "New Primality Criteria and Factorizations of 2^n +/- 1",
Brillhart, Lehmer, and Selfridge, Mathematics of Computation V29 (1975)

The exact details of the test are too involved to relate here. However,
I quote the following theorem:

Construct a Lucas sequence: U   = P U  - Q U       U  = 0,   U  = 1
			     n        n-1    n-2      0         1
 
and let D = P^2 - 4Q  so that the Jacobi symbol (D|N) = -1 where N
is the number we wish to test.
 
Then if N divides U   but N does not divide U        for each prime q 
	           N+1                       (N+1)/q
dividing N+1 then N is prime.

Bob Silverman