mersenneforum.org A Theoretical (vs. Proficient/Practical) Deterministic Primality Test
 Register FAQ Search Today's Posts Mark Forums Read

 2016-03-08, 19:57 #1 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23×241 Posts A Theoretical (vs. Proficient/Practical) Deterministic Primality Test Hi, Is this list exhaustive? http://primes.utm.edu/prove/ Are there any deterministic primality tests based on factorials or primorials? The following routine is based on my infamous Theorem 1. The following code is restricted by the ability to calculate the factorial and is not particularly fast but is as deterministic as trial-division (though faster) and can determine a factor if the input is composite. The largest prime I used without making the factorial too large for WDP is: 200000000000027 Any comments are greatly anticipated. You can copy and paste the code in Wolfram Development Platform. Try different prp values and press Shift+Enter to run: Code: prp=919 ; Print[prp," is PRP is ",PrimeQ[prp]]; squareroot=Floor[Sqrt[prp]]; factorial=squareroot !; a=factorial; b=prp; c=2; While[c>1, c=Mod[a,b]; a=b; b=c; ] If[c==0,Print[prp," is divisible by ",a],Print[prp," is definitely Prime."]] Last fiddled with by a1call on 2016-03-08 at 19:59
2016-03-08, 20:37   #2
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by a1call Is this list exhaustive? http://primes.utm.edu/prove/
No. It misses out KP (Kolyvagin-Pomerance) (30% factorisation) and CHG (Coppersmith–Howgrave-Graham) (25% factorisation).

Quote:
 Originally Posted by a1call Are there any deterministic primality tests based on factorials or primorials?
Yes. Wilson's theorem

 2016-03-08, 20:37 #3 CRGreathouse     Aug 2006 2×5×593 Posts The list is not nearly exhaustive -- there are probably hundreds of methods if you include computationally infeasible approaches.
2016-03-08, 20:38   #4
CRGreathouse

Aug 2006

2·5·593 Posts

Quote:
 Originally Posted by paulunderwood No. It misses out KP (Kolyvagin-Pomerance) (30% factorisation) and CHG (Coppersmith–Howgrave-Graham) (25% factorisation).
Don't forget CIDE!

 2016-03-08, 21:00 #5 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23·241 Posts Thank you for the replies. Thanks for the Wilson's Theorem Link.
 2016-03-08, 21:04 #6 PawnProver44     "NOT A TROLL" Mar 2016 California 197 Posts I would not recommend using Wilson's theorem to prove large primes. The computations are far to long for anyone to calculate. I would rather go with Fermat's Theorem. I hope someone would come up with a more easier theorem someday.
2016-03-08, 21:13   #7
CRGreathouse

Aug 2006

10111001010102 Posts

Quote:
 Originally Posted by PawnProver44 I would not recommend using Wilson's theorem to prove large primes. The computations are far to long for anyone to calculate. I would rather go with Fermat's Theorem. I hope someone would come up with a more easier theorem someday.
Agreed, it's useless computationally. But just for fun:
Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?

2016-03-08, 22:45   #8
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts

Quote:
 Originally Posted by paulunderwood No. It misses out KP (Kolyvagin-Pomerance) (30% factorisation) ...
Konyagin, actually.
His ancestor was good at chess, probably. (Kon' = lit. horse = (chess) Bishop)

2016-03-08, 22:56   #9
paulunderwood

Sep 2002
Database er0rr

2×1,723 Posts

Quote:
 Originally Posted by Batalov Konyagin, actually. His ancestor was good at chess, probably. (Kon' = lit. horse = (chess) Bishop)
Thanks for the correction, Serge.

2016-03-08, 23:18   #10
a1call

"Rashid Naimi"
Oct 2015
Remote to Here/There

23·241 Posts

Quote:
 Originally Posted by CRGreathouse Agreed, it's useless computationally. But just for fun: Has Stirling’s Formula ever been applied, with interesting consequence, to Wilson’s Theorem?
Thank you for that link. It is very informative and interesting, though I do not personally agree with the consensus reached. But that's likely due to my ignorance and lack of math skills.
Thanks again.

 2016-03-09, 20:08 #11 a1call     "Rashid Naimi" Oct 2015 Remote to Here/There 23·241 Posts Here is perhaps a more useful application of the Opening-Post concept. Let p1 be: p1=n!-p0 Then: p1 is Prime for all integers n>3 and all Prime numbers p0 where p1

 Similar Threads Thread Thread Starter Forum Replies Last Post Stargate38 Operazione Doppi Mersennes 14 2020-01-29 20:35 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33 Trilo Miscellaneous Math 25 2018-03-11 23:20 wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25 ixfd64 Hardware 30 2012-03-05 06:16

All times are UTC. The time now is 23:14.

Sat Oct 24 23:14:51 UTC 2020 up 44 days, 20:25, 1 user, load averages: 1.71, 1.77, 1.74