mersenneforum.org what is the best primality software?
 Register FAQ Search Today's Posts Mark Forums Read

2022-09-20, 16:40   #56
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·29·127 Posts

Quote:
 Originally Posted by LaurV I need a million dollars. I need it tomorrow!
Today won't do? Multimillionaire supermodel, by lunch time, please.

 2022-09-21, 03:40 #57 bbb120     "特朗普trump" Feb 2019 朱晓丹没人草 22×3×11 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=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
 2022-09-21, 07:35 #58 bbb120     "特朗普trump" Feb 2019 朱晓丹没人草 100001002 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
2022-09-21, 13:36   #59
Dr Sardonicus

Feb 2017
Nowhere

185116 Posts

Quote:
 Originally Posted by bbb120 reason two:when odd number is very very very big,it is very very very hard to hit pseudoprime!
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.

2022-09-22, 03:26   #60
bbb120

"特朗普trump"
Feb 2019

22×3×11 Posts

Quote:
 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.

2022-09-22, 05:13   #61
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

5·7·191 Posts

Quote:
I threw a fair die and it came up 2.

Can't get more random than that.

2022-09-22, 05:32   #62
Uncwilly
6809 > 6502

"""""""""""""""""""
Aug 2003
101×103 Posts

101010100011012 Posts

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

2022-09-22, 12:27   #63
Dr Sardonicus

Feb 2017
Nowhere

3·52·83 Posts

(my emphasis)
Quote:
 Originally Posted by bbb120 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!!
Quote:

2022-09-23, 01:36   #64
bbb120

"特朗普trump"
Feb 2019

22·3·11 Posts

Quote:
 Originally Posted by Dr Sardonicus (my emphasis)
http://www.janfeitsma.nl/math/psp2/statistics

I only have statistics data of base 2，

2022-09-23, 02:57   #65
chalsall
If I May

"Chris Halsall"
Sep 2002

2B4D16 Posts

Quote:
 Originally Posted by bbb120 I only have statistics data of base 2，
In some rare cases, the SNR can actually be negative.

2022-09-23, 04:27   #66
VBCurtis

"Curtis"
Feb 2005
Riverside, CA

2×2,819 Posts

Quote:
 Originally Posted by chalsall In some rare cases, the SNR can actually be negative.
Viewing can make you dumber. We agree.

 Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 289 2023-01-30 19:55 bur GPU Computing 6 2020-08-28 06:20 JonathanM Information & Answers 25 2020-06-16 02:47 marco_calabresi Information & Answers 3 2009-04-17 19:44 TTn PSearch 0 2004-05-04 13:16

All times are UTC. The time now is 18:46.

Sat Feb 4 18:46:00 UTC 2023 up 170 days, 16:14, 1 user, load averages: 1.26, 0.99, 0.96