mersenneforum.org what is the best primality software?
 User Name Remember Me? Password
 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 朱晓丹没人草 13210 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 朱晓丹没人草 22×3×11 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

2·3·17·61 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

150328 Posts

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

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

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

22×7×389 Posts

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

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

Feb 2017
Nowhere

2×3×17×61 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:
 Originally Posted by bbb120 please choose your base at random!

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

2·72·113 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·32·313 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 02:42.

Thu Feb 2 02:42:43 UTC 2023 up 168 days, 11 mins, 1 user, load averages: 1.61, 1.69, 1.51

Copyright ©2000 - 2023, 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.

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔