what is the best primality software?

[kriesel]

Originally Posted by LaurV

I need a million dollars. I need it tomorrow!

Today won't do? Multimillionaire supermodel, by lunch time, please.

[bbb120]

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

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=n-1;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<s-1&&t1!=n-1,k=k+1;t1=Mod[t1^2,n]];
    If[t1==n-1,Return[True],Return[False]]
](*miller rabin子函数*)
(*费马测试子函数*)
Fermat[n0_,a0_]:=Module[{n=n0,a=a0},
    If[PowerMod[a,n-1,n]==1,Return[True],Return[False]]
](*费马测试,费马小定理*)

let n to be the odd number which needs to test primality,
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

limit	#psp
10^19	91210364

according the prime number theorem ,there are
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!!

[bbb120]

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

[Dr Sardonicus]

Originally Posted by bbb120

<snip>
reason two:when odd number is very very very big,it is very very very hard to hit pseudoprime!
<snip>

Not at all. Let p be a prime number, and let N = 2^p - 1.

Then 2^(N-1) == 1 (mod N) [and 2^((N-1)/2) == 1 (mod N) also].

So N "passes" Fermat and Miller-Rabin 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 double-checked 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.

[bbb120]

Originally Posted by Dr Sardonicus

Not at all. Let p be a prime number, and let N = 2^p - 1.

Then 2^(N-1) == 1 (mod N) [and 2^((N-1)/2) == 1 (mod N) also].

So N "passes" Fermat and Miller-Rabin 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 double-checked 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.

please choose your base at random!

[retina]

Originally Posted by bbb120

please choose your base at random!

I threw a fair die and it came up 2.

Can't get more random than that.

[Uncwilly]

Originally Posted by bbb120

please choose your base at random!

Since, I don't yet know what p is, I will take that as my random choice.

[Dr Sardonicus]

(my emphasis)

Originally Posted by bbb120

<snip>
according the prime number theorem ,there are
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!!

Originally Posted by bbb120

please choose your base at random!

[bbb120]

Originally Posted by Dr Sardonicus

(my emphasis)

http://www.janfeitsma.nl/math/psp2/statistics

I only have statistics data of base 2，

[chalsall]

Originally Posted by bbb120

I only have statistics data of base 2，

In some rare cases, the SNR can actually be negative.

[VBCurtis]

Originally Posted by chalsall

In some rare cases, the SNR can actually be negative.

Viewing can make you dumber. We agree.