N-1 primality test

[Citrix]

I am just wondering in the n-1 primality test must p-1 be completely factorizable.

Can p be (a^a-1)/(a-1) where a is prime
then p-1 = (a^a-a)/(a-1)

clearly a^(a-1)-1 can be split into a^(a-1)/2+1 and a^(a-1)/2-1


Can this factorization be used to prove these numbers prime or not?

Citrix

[wblipp]

Originally Posted by Citrix

I am just wondering in the n-1 primality test must p-1 be completely factorizable.

No. If you have prime factors for 33% of n-1, PFGW can prove the number prime. There are other methods that can squeeze out proofs with slightly less, although I know of no simple tools for such proofs. Check out back posts on the Yahoo PFGW group (also download PFGW from there).

[R.D. Silverman]

Originally Posted by wblipp

No. If you have prime factors for 33% of n-1, PFGW can prove the number prime. There are other methods that can squeeze out proofs with slightly less, although I know of no simple tools for such proofs. Check out back posts on the Yahoo PFGW group (also download PFGW from there).

One can do even better. If you have sufficient factors of any of

p-1, p+1, p^2+1, p^2+p+1, p^2-p+1, such that the product exceeds
n^1/3, then you can do a full primality proof with "old fashioned" methods.

The Cyclotomy (aka Cohen-Lenstra-Bosma, etc.) Method even improves upon
this. It can use results from *many* cyclotomic rings simultaneously...

[xilman]

Originally Posted by R.D. Silverman

One can do even better. If you have sufficient factors of any of

p-1, p+1, p^2+1, p^2+p+1, p^2-p+1, such that the product exceeds
n^1/3, then you can do a full primality proof with "old fashioned" methods.

The Cyclotomy (aka Cohen-Lenstra-Bosma, etc.) Method even improves upon
this. It can use results from *many* cyclotomic rings simultaneously...

Though the latter is a real pig to implement, not least because of the difficulty of debugging. There are so many side cases that are executed with very low priority on "random" inputs and it can be hard to concoct test data to exercise them.

I've implemented the simple form of Cohen-Lenstra version and made a start on Bosma's improved version but gave up after a while.


Paul