20220503, 16:51  #1 
May 2022
1_{8} Posts 
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? 
20220503, 16:59  #2  
Undefined
"The unspeakable one"
Jun 2006
My evil lair
2^{2}·13·127 Posts 
Quote:
Quote:
There aren't any shortcuts. You gotta wait till the very end before the answer is completed. 

20220503, 17:43  #3  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
15335_{8} Posts 
Quote:
Trial factoring or P1 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 probablyprime (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 20220503 at 17:44 

20220503, 18:25  #4  
P90 years forever!
Aug 2002
Yeehaw, FL
1111101101000_{2} Posts 
Quote:


20220503, 19:01  #5  
Einyen
Dec 2003
Denmark
2^{2}×7×11^{2} Posts 
Quote:
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 20220503 at 19:02 

20220503, 23:17  #6  
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
1ADD_{16} Posts 
Quote:
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 doublecheck, 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 LucasLehmer 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 20220503 at 23:18 

20220503, 23:37  #7 
If I May
"Chris Halsall"
Sep 2002
Barbados
2^{3}×3×5×89 Posts 

20220504, 02:49  #8 
Mar 2019
3·101 Posts 

20220504, 05:24  #9 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest
13·23^{2} Posts 
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? 
20220504, 12:52  #10 
"6800 descendent"
Feb 2005
Colorado
2D5_{16} Posts 
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 overlycriticizing other's posting styles also. 
20220504, 21:30  #11  
Mar 2019
100101111_{2} Posts 
Quote:
Those things are all relevant. But if one goes back to the OP question: Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Why does MillerRabin test fail?  calimero22  Computer Science & Computational Number Theory  7  20180909 16:49 
Proof of Primality Test for Fermat Numbers  princeps  Math  15  20120402 21:49 
The fastest primality test for Fermat numbers.  Arkadiusz  Math  6  20110405 19:39 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 
Very early stress test fault  nightic  Software  2  20030605 06:25 