mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-11-20, 23:51   #1
amenezes
 
Aug 2020

2×5 Posts
Smile Primality Certificates.

Are there any reliable Primality Certificates for Mersenne Numbers that are prime that cannot be faked?
amenezes is offline   Reply With Quote
Old 2021-11-21, 12:03   #2
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3,061 Posts
Default

Quote:
Originally Posted by amenezes View Post
Are there any reliable Primality Certificates for Mersenne Numbers that are prime that cannot be faked?
Depends on what you mean. I have a stash of PRP proof result files for assorted known Mersenne primes. These could conceivably be run through the server processing and cert issue. Since the known Mersenne primes have already been redundantly verified with multiple LL runs on separate hardware and separate software, not much would be gained by getting one more result per known prime, consisting of PRP-P "Yup, it's Probably prime all right." Except that the verifiable delay function on which the proof and certification is based tells us both that the full computation was run, and that it executed correctly, so serves as a reliability check of the generating software's implementation of proof generation. (Not faked, and no serious errors.)
To my knowledge no Mersenne prime discovery has yet been made by running PRP first, giving a PRP-P result, and then confirming with LL tests, as would occur for the next one. So consequently none have been found by PRP and proof generation. M82589933 is the only one that might have happened on, since the first PRP tests were for ~77.5M and above, so excluding the next lower M77232917 and lower. See also the last several entries on https://www.mersenneforum.org/showpo...46&postcount=6 for some related links.
kriesel is online now   Reply With Quote
Old 2021-11-21, 13:32   #3
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

OP wants something different. A primality certificate for Mersenne primes, so a (very) fast proof when 2^p-1 is prime (where p is an odd prime).

Let r=2+sqrt[3] and calculate v=r^(2^(p-2)) in Z[N,sqrt[3]], where N=2^p-1. Lucas Lehmer test says (in an equivalent form) that N is prime iff v=k*sqrt[3].
The advantage of this form is that you can use error checking and giving certificates as like for 3^(2^p) mod N calculation without any probable prime issues, giving an answer to your question. It is hard to fake this.

But why are we using the prp form? Because the calculation of v is at least two times slower than a standard LL or prp test with error checking.
R. Gerbicz is offline   Reply With Quote
Old 2021-11-21, 15:46   #4
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

2·3,061 Posts
Default

This paper states the Pepin test for Fermats, and the Lucas-Lehmer for Mersennes, provide certificates.
https://www.ams.org/journals/mcom/19...-0866117-4.pdf
kriesel is online now   Reply With Quote
Old 2021-11-21, 16:55   #5
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

1,531 Posts
Default

Quote:
Originally Posted by kriesel View Post
This paper states the Pepin test for Fermats, and the Lucas-Lehmer for Mersennes, provide certificates.
https://www.ams.org/journals/mcom/19...-0866117-4.pdf
Yes, and with that oldish certificates you would only double check the first computation, what Gimps has done in the past. Then call the new method as fast certificate, because you need there roughly ~log2(N)/1024 (=p/1024 for Mp) or even fewer multiplications, but you'll have only this certification if you do the long log2(N) multiplications mod N (with built-in error checks).
R. Gerbicz is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primo version 4 certificates danaj FactorDB 11 2016-11-24 01:59
primo primality certificates - (un)lucky numbers klajok Factoring 0 2011-07-21 08:23
Primality searches and primality successes marco_calabresi Information & Answers 3 2009-04-17 19:44
primality of ((p+1)^p-1)/p^2 maxal Math 23 2008-03-09 21:09
How RSA certificates worked in Hotmail koders333 Science & Technology 1 2005-10-02 04:34

All times are UTC. The time now is 15:19.


Wed Jan 26 15:19:38 UTC 2022 up 187 days, 9:48, 1 user, load averages: 1.38, 1.44, 1.34

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.

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