mersenneforum.org  

Go Back   mersenneforum.org > Prime Search Projects > Proth Prime Search

Closed Thread
 
Thread Tools
Old 2022-09-20, 16:40   #56
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·33·127 Posts
Default

Quote:
Originally Posted by LaurV View Post
I need a million dollars. I need it tomorrow!
Today won't do? Multimillionaire supermodel, by lunch time, please.
kriesel is online now  
Old 2022-09-21, 03:40   #57
bbb120
 
bbb120's Avatar
 
"特朗普trump"
Feb 2019
大陆China

7416 Posts
Default

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<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
Code:
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!!
Attached Thumbnails
Click image for larger version

Name:	fermat.jpg
Views:	22
Size:	41.3 KB
ID:	27339  

Last fiddled with by Dr Sardonicus on 2022-09-21 at 12:33 Reason: User request
bbb120 is offline  
Old 2022-09-21, 07:35   #58
bbb120
 
bbb120's Avatar
 
"特朗普trump"
Feb 2019
大陆China

22×29 Posts
Default

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
bbb120 is offline  
Old 2022-09-21, 13:36   #59
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

599210 Posts
Default

Quote:
Originally Posted by bbb120 View Post
<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.
Dr Sardonicus is offline  
Old 2022-09-22, 03:26   #60
bbb120
 
bbb120's Avatar
 
"特朗普trump"
Feb 2019
大陆China

22×29 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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!
bbb120 is offline  
Old 2022-09-22, 05:13   #61
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

22·13·127 Posts
Default

Quote:
Originally Posted by bbb120 View Post
please choose your base at random!
I threw a fair die and it came up 2.

Can't get more random than that.
retina is online now  
Old 2022-09-22, 05:32   #62
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

29F816 Posts
Default

Quote:
Originally Posted by bbb120 View Post
please choose your base at random!
Since, I don't yet know what p is, I will take that as my random choice.
Uncwilly is offline  
Old 2022-09-22, 12:27   #63
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

23·7·107 Posts
Default

(my emphasis)
Quote:
Originally Posted by bbb120 View Post
<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!!
Quote:
Originally Posted by bbb120 View Post
please choose your base at random!
Dr Sardonicus is offline  
Old 2022-09-23, 01:36   #64
bbb120
 
bbb120's Avatar
 
"特朗普trump"
Feb 2019
大陆China

22×29 Posts
Default

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

I only have statistics data of base 2,
bbb120 is offline  
Old 2022-09-23, 02:57   #65
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

1067310 Posts
Default

Quote:
Originally Posted by bbb120 View Post
I only have statistics data of base 2,
In some rare cases, the SNR can actually be negative.
chalsall is offline  
Old 2022-09-23, 04:27   #66
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10101011011002 Posts
Default

Quote:
Originally Posted by chalsall View Post
In some rare cases, the SNR can actually be negative.
Viewing can make you dumber. We agree.
VBCurtis is offline  
Closed Thread

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 2022-09-12 17:00
For which types of primes is GPU primality test software available? bur GPU Computing 6 2020-08-28 06:20
Fastest software for Mersenne primality test? JonathanM Information & Answers 25 2020-06-16 02:47
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
Software TTn PSearch 0 2004-05-04 13:16

All times are UTC. The time now is 11:33.


Mon Oct 3 11:33:45 UTC 2022 up 46 days, 9:02, 0 users, load averages: 1.71, 1.37, 1.16

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2022, 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.

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