20220920, 16:40  #56 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
2·3^{3}·127 Posts 

20220921, 03:40  #57 
"特朗普trump"
Feb 2019
大陆China
74_{16} Posts 
why use fermat test instead of miller rabin test?
reason one: fermat test is a little efficient than miller rabin test reason two:when odd number is very very very big,it is very very very hard to hit pseudoprime! let us study the code of miller rabin test and fermat test Code:
Clear["Global`*"]; (*miller rabin test,n0 big odd integer,a0 base*) MillerRabin[n0_,a0_]:=Module[{n=n0,a=a0,s,m,t1,k}, s=0;m=n1;While[Mod[m,2]==0,m=m/2;s=s+1]; t1=PowerMod[a,m,n]; If[t1==1,Return[True]]; k=0;While[k<s1&&t1!=n1,k=k+1;t1=Mod[t1^2,n]]; If[t1==n1,Return[True],Return[False]] ](*miller rabin子函数*) (*费马测试子函数*) Fermat[n0_,a0_]:=Module[{n=n0,a=a0}, If[PowerMod[a,n1,n]==1,Return[True],Return[False]] ](*费马测试,费马小定理*) look at the picture below of attachment! we can find fermat test is a little efficient than miller test . look at the table http://www.janfeitsma.nl/math/psp2/statistics Code:
limit #psp 10^19 91210364 approximate 10^19/Log[10^19] =2.28576*10^17 prime numbers below 10^19 , but only has 91210364 pseudoprimes(base 2)below 10^19, 10^19/Log[10^19]/91210364 =2.50603*10^9, so when the tested number is very very large,hit a prime number is very very very easy than hit a pseudoprime!! Last fiddled with by Dr Sardonicus on 20220921 at 12:33 Reason: User request 
20220921, 07:35  #58 
"特朗普trump"
Feb 2019
大陆China
2^{2}×29 Posts 
according the prime number theory ,there are
=>according the prime number theorem ,there are maybe someone can help me modify the last reply, I cannot edit it now 
20220921, 13:36  #59  
Feb 2017
Nowhere
5992_{10} Posts 
Quote:
Then 2^(N1) == 1 (mod N) [and 2^((N1)/2) == 1 (mod N) also]. So N "passes" Fermat and MillerRabin to the base 2. So far, only 51 primes p are known for which 2^p  1 is actually prime, whereas 2^p  1 is known to be composite for all other primes p up to whatever the current doublechecked milestone is. So for large N = 2^p  1 I'd say it's a lot easier to hit a pseudoprime than it is to hit a prime. 

20220922, 03:26  #60  
"特朗普trump"
Feb 2019
大陆China
2^{2}×29 Posts 
Quote:


20220922, 05:13  #61 
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}·13·127 Posts 

20220922, 05:32  #62 
6809 > 6502
"""""""""""""""""""
Aug 2003
101×103 Posts
29F8_{16} Posts 

20220922, 12:27  #63  
Feb 2017
Nowhere
2^{3}·7·107 Posts 
(my emphasis)
Quote:


20220923, 01:36  #64 
"特朗普trump"
Feb 2019
大陆China
2^{2}×29 Posts 

20220923, 02:57  #65 
If I May
"Chris Halsall"
Sep 2002
Barbados
10673_{10} Posts 

20220923, 04:27  #66 
"Curtis"
Feb 2005
Riverside, CA
1010101101100_{2} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
FastECPP software and >50000 digit primality proof (reposted from NMBRTHRY)  Batalov  And now for something completely different  192  20220912 17:00 
For which types of primes is GPU primality test software available?  bur  GPU Computing  6  20200828 06:20 
Fastest software for Mersenne primality test?  JonathanM  Information & Answers  25  20200616 02:47 
Primality searches and primality successes  marco_calabresi  Information & Answers  3  20090417 19:44 
Software  TTn  PSearch  0  20040504 13:16 