mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2005-09-19, 03:24   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

112·13 Posts
Default 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
Citrix is offline   Reply With Quote
Old 2005-09-19, 03:52   #2
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

2×32×131 Posts
Default

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).
wblipp is offline   Reply With Quote
Old 2005-09-19, 14:36   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

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...
R.D. Silverman is offline   Reply With Quote
Old 2005-09-19, 15:06   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"๐’‰บ๐’ŒŒ๐’‡ท๐’†ท๐’€ญ"
May 2003
Down not across

5·2,053 Posts
Default

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
xilman is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
New Mersenne primality test Prime95 Miscellaneous Math 19 2014-08-23 04:18
there is another way to test the primality of a no shawn Miscellaneous Math 5 2007-07-17 17:55
AKS Primality Test Guilherme Math 2 2004-11-26 05:29
A primality test for Fermat numbers faster than Pรฉpin's test ? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.