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

2·811 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
Near Grandkid

53·19 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
 
"Bob Silverman"
Nov 2003
North of Boston

755810 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

79×149 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 offline   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 10:13.


Fri Jun 9 10:13:26 UTC 2023 up 295 days, 7:42, 0 users, load averages: 0.80, 1.15, 1.03

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”