mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2016-03-08, 19:57   #1
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23×241 Posts
Default 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
a1call is offline   Reply With Quote
Old 2016-03-08, 20:37   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

Quote:
Originally Posted by a1call View Post
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 View Post
Are there any deterministic primality tests based on factorials or primorials?
Yes. Wilson's theorem
paulunderwood is offline   Reply With Quote
Old 2016-03-08, 20:37   #3
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×5×593 Posts
Default

The list is not nearly exhaustive -- there are probably hundreds of methods if you include computationally infeasible approaches.
CRGreathouse is offline   Reply With Quote
Old 2016-03-08, 20:38   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·5·593 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
No. It misses out KP (Kolyvagin-Pomerance) (30% factorisation) and CHG (Coppersmith–Howgrave-Graham) (25% factorisation).
Don't forget CIDE!
CRGreathouse is offline   Reply With Quote
Old 2016-03-08, 21:00   #5
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·241 Posts
Default

Thank you for the replies.
Thanks for the Wilson's Theorem Link.
a1call is offline   Reply With Quote
Old 2016-03-08, 21:04   #6
PawnProver44
 
PawnProver44's Avatar
 
"NOT A TROLL"
Mar 2016
California

197 Posts
Post

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.
PawnProver44 is offline   Reply With Quote
Old 2016-03-08, 21:13   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

10111001010102 Posts
Default

Quote:
Originally Posted by PawnProver44 View Post
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?
CRGreathouse is offline   Reply With Quote
Old 2016-03-08, 22:45   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22·2,281 Posts
Cool

Quote:
Originally Posted by paulunderwood View Post
No. It misses out KP (Kolyvagin-Pomerance) (30% factorisation) ...
Konyagin, actually.
His ancestor was good at chess, probably. (Kon' = lit. horse = (chess) Bishop)
Batalov is offline   Reply With Quote
Old 2016-03-08, 22:56   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

2×1,723 Posts
Default

Quote:
Originally Posted by Batalov View Post
Konyagin, actually.
His ancestor was good at chess, probably. (Kon' = lit. horse = (chess) Bishop)
Thanks for the correction, Serge.
paulunderwood is offline   Reply With Quote
Old 2016-03-08, 23:18   #10
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·241 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
a1call is offline   Reply With Quote
Old 2016-03-09, 20:08   #11
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

23·241 Posts
Default

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<n2

Here is the verification code in the WDP. You cam create a free account here:

https://develop.wolframcloud.com/app/

Start a notebook and copy and paste the code below as "Wolfram language input" and press Shift+Enter to run.
Try different n values.

Code:
n=19;

p0=NextPrime[n !-n^2];
p1=n !-p0;
Print[n,"!-",p0,"=",p1," is Prime is ",PrimeQ[p1],"."]
The delay for larger n values is due to NextPrime function in the code (Which is used to find a prime large enough to satisfy the inequality condition) and not subtraction.

This potentially opens up a proof to thousands (and by extension unlimited number) of new primes.
Take any factorial n!, find a known prime that if subtracted from the factorial yields a sum smaller than n2 and you are guaranteed that the sum is a prime. No other primality test is required.
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How long will it be until MM61 is within practical reach of PRP/primality testing? Stargate38 Operazione Doppi Mersennes 14 2020-01-29 20:35
GQQ: a "deterministic" "primality" test in O(ln n)^2 Chair Zhuang Miscellaneous Math 21 2018-03-26 22:33
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
a new Deterministic primality testing wsc812 Computer Science & Computational Number Theory 36 2013-03-04 06:25
maximum theoretical speed of LL test w/o bandwidth limitations? 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

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.