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