mersenneforum.org  

Go Back   mersenneforum.org > New To GIMPS? Start Here! > Information & Answers

Reply
 
Thread Tools
Old 2022-05-03, 16:51   #1
rian
 
May 2022

116 Posts
Default Will Fermat primality test fail early?

I searched the forum but found no answer.



I selected a Mersenne number with a self written program. All my checks say it is prime but it is not exhaustive.



So I installed mprime, selected Advanced/Test and entered my Mersenne number.


It says "primality test .. using FMA3 FFT .. Iteration: .." with an ETA in about two weeks.





My question:


If the number is not prime will it then fail early meaning will it most probably recognize that it is not prime before the two weeks and tell me so?


Or will I have to wait for the full two weeks until the Fermat primality test (which I think this test is if I see it correctly) finally says that the number is not prime if it is not?
rian is offline   Reply With Quote
Old 2022-05-03, 16:59   #2
retina
Undefined
 
retina's Avatar
 
"The unspeakable one"
Jun 2006
My evil lair

11001110010102 Posts
Default

Quote:
Originally Posted by rian View Post
If the number is not prime will it then fail early meaning will it most probably recognize that it is not prime before the two weeks and tell me so?
Nope.
Quote:
Originally Posted by rian View Post
Or will I have to wait for the full two weeks until the Fermat primality test (which I think this test is if I see it correctly) finally says that the number is not prime if it is not?
Yup.

There aren't any shortcuts. You gotta wait till the very end before the answer is completed.
retina is online now   Reply With Quote
Old 2022-05-03, 17:43   #3
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

3·2,281 Posts
Default

Quote:
Originally Posted by rian View Post
I searched the forum but found no answer.

I selected a Mersenne number with a self written program. All my checks say it is prime but it is not exhaustive.

So I installed mprime, selected Advanced/Test and entered my Mersenne number.

It says "primality test .. using FMA3 FFT .. Iteration: .." with an ETA in about two weeks.
What checks were those?
Trial factoring or P-1 factoring, P+1, etc, may find a factor and reveal composite nature early.
That they do not find a factor, is consistent with but not evidence of a prime. (About 1/3 of composite Mersennes survive prudent levels of factoring attempts.)
Primality testing (LL) or probably-prime (PRP) do not have the potential to provide early answers. Accurate execution of all required iterations is needed.

Welcome to the forum. You may find parts of the reference info collection useful or informative.

Last fiddled with by kriesel on 2022-05-03 at 17:44
kriesel is offline   Reply With Quote
Old 2022-05-03, 18:25   #4
Prime95
P90 years forever!
 
Prime95's Avatar
 
Aug 2002
Yeehaw, FL

29×277 Posts
Default

Quote:
Originally Posted by rian View Post
I selected a Mersenne number with a self written program. All my checks say it is prime but it is not exhaustive.
I hope your checks included visiting this page: https://www.mersenne.org/report_exponent/
Prime95 is online now   Reply With Quote
Old 2022-05-03, 19:01   #5
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

23·32·47 Posts
Default

Quote:
Originally Posted by rian View Post
I selected a Mersenne number with a self written program. All my checks say it is prime but it is not exhaustive.
Unless you are very skilled at programming in assembly language and programming Fast Fourier transforms, your program is most likely at least 10 times slower than mprime, so unless you spent months checking with your own program those checks probably do not mean too much.

Quote:
Originally Posted by rian View Post
Or will I have to wait for the full two weeks until the Fermat primality test (which I think this test is if I see it correctly) finally says that the number is not prime if it is not?
Yes, these numbers are so big that a simple Fermat test that takes seconds on "normal" everyday sized numbers will take days, weeks or months, depending on your hardware and which size of exponent you chose.

Last fiddled with by ATH on 2022-05-03 at 19:02
ATH is offline   Reply With Quote
Old 2022-05-03, 23:17   #6
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

152738 Posts
Default

Quote:
Originally Posted by rian View Post
So I installed mprime, selected Advanced/Test and entered my Mersenne number.
There are at least two possible issues with this approach.
One, it does not reserve the exponent to you. Someone else might be already running it, have already run it, or get assigned it while you are independently running it. (Unless mprime tries to register exponents entered in Advanced/Test if you've configured to use primenet. I think it does not. Quick tests here with tiny exponents indicate it does not.)
Two, it does an LL test, probably with the 50% error detection rate Jacobi symbol check, not the far superior reliability PRP test with Gerbicz Error Check.
Three, you haven't indicated which version of mprime you installed, but it is likely capable of generating a PRP proof file, avoiding the chance of needing a possible additional full length double-check, allowing instead upload of the proof file and running a very quick certification (at typically under 1% of the cost of a full test). Proof file generation is not available in any known GIMPS software for LL tests; only PRP in mprime/prime95 or most recent versions of Gpuowl.

Maybe you've got some of those bases covered. Can't tell from post 1.

From mprime's readme.txt:
Code:
ADVANCED MENU
-------------

You should not need to use the Advanced menu.  This menu choice is
provided only for those who are curious.  Note that many of the menu choices
are grayed while testing is in progress.  Choose Test/Stop to activate
these menu choices.

The Test choice can be used to run a Lucas-Lehmer test on one Mersenne
number.  Enter the Mersenne number's exponent - this must be a prime
number between 5 and 560000000.

Last fiddled with by kriesel on 2022-05-03 at 23:18
kriesel is offline   Reply With Quote
Old 2022-05-03, 23:37   #7
chalsall
If I May
 
chalsall's Avatar
 
"Chris Halsall"
Sep 2002
Barbados

47·227 Posts
Default

Quote:
Originally Posted by kriesel View Post
There are at least two possible issues with this approach.
Ken. If I may please...

We are all very smart. Do we really have to prove it in every message?
chalsall is online now   Reply With Quote
Old 2022-05-04, 02:49   #8
mathwiz
 
Mar 2019

12F16 Posts
Default

Quote:
Originally Posted by chalsall View Post
Ken. If I may please...

We are all very smart. Do we really have to prove it in every message?
As far as I can tell, kriesel was trying to be helpful, but in his long, excessively rambling way (and conveying information that isn't entirely what OP asked).
mathwiz is online now   Reply With Quote
Old 2022-05-04, 05:24   #9
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

11010101110112 Posts
Default

Quote:
Originally Posted by mathwiz View Post
conveying information that isn't entirely what OP asked).
And possibly, the OP didn't know enough yet to ask about, but may very soon understand better because of what was posted.
What's better: twenty questions & minimal responses, or some informative response that's more helpful? Why be stingy with information?
kriesel is offline   Reply With Quote
Old 2022-05-04, 12:52   #10
PhilF
 
PhilF's Avatar
 
"6800 descendent"
Feb 2005
Colorado

52×29 Posts
Default

Guys:

1 - We have PLENTY of hard drive space for posts these days.
2 - We have LOTS of CPU power that keeps the databases quite responsive no matter how many posts there are or how long they are.
3 - We have POWERFUL GPUs these days that allows us to very quickly scroll our screens up, down, left, and right.
4 - We have TREMENDOUS bandwidth that isn't even close to becoming saturated, no matter how long winded we are or how many posts we create.
5 - We even have an OFF button.

So I don't really understand all the sensitivity to posters and their style.

We are already tough enough on those who do not possess PhD level math skills. In my opinion we don't need to add to that reputation by overly-criticizing other's posting styles also.
PhilF is online now   Reply With Quote
Old 2022-05-04, 21:30   #11
mathwiz
 
Mar 2019

1001011112 Posts
Default

Quote:
Originally Posted by PhilF View Post
So I don't really understand all the sensitivity to posters and their style.
The problem is kriesel babbling on about LL vs PRP, which version of mprime, etc.

Those things are all relevant. But if one goes back to the OP question:

Quote:
Originally Posted by rian
I selected a Mersenne number with a self written program. All my checks say it is prime but it is not exhaustive.
The OP needs to do some background reading about the absolute basics of GIMPS, mprime, and how to test exponents (and that a self-written program -- probably, but not certainly -- will be far slower). Additional details here are really irrelevant.
mathwiz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why does Miller-Rabin test fail? calimero22 Computer Science & Computational Number Theory 7 2018-09-09 16:49
Proof of Primality Test for Fermat Numbers princeps Math 15 2012-04-02 21:49
The fastest primality test for Fermat numbers. Arkadiusz Math 6 2011-04-05 19:39
A primality test for Fermat numbers faster than Pépin's test ? T.Rex Math 0 2004-10-26 21:37
Very early stress test fault nightic Software 2 2003-06-05 06:25

All times are UTC. The time now is 23:34.


Fri Sep 30 23:34:26 UTC 2022 up 43 days, 21:03, 0 users, load averages: 1.20, 1.05, 1.06

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.

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