mersenneforum.org > Math N-1 primality test
 Register FAQ Search Today's Posts Mark Forums Read

 2005-09-19, 03:24 #1 Citrix     Jun 2003 112·13 Posts N-1 primality test 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
2005-09-19, 03:52   #2
wblipp

"William"
May 2003
New Haven

2×32×131 Posts

Quote:
 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).

2005-09-19, 14:36   #3
R.D. Silverman

Nov 2003

22·5·373 Posts

Quote:
 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...

2005-09-19, 15:06   #4
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

5·2,053 Posts

Quote:
 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

 Similar Threads Thread Thread Starter Forum Replies Last Post Trilo Miscellaneous Math 25 2018-03-11 23:20 Prime95 Miscellaneous Math 19 2014-08-23 04:18 shawn Miscellaneous Math 5 2007-07-17 17:55 Guilherme Math 2 2004-11-26 05:29 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 19:34.

Mon Sep 28 19:34:38 UTC 2020 up 18 days, 16:45, 1 user, load averages: 2.05, 1.66, 1.70