mersenneforum.org Will Fermat primality test fail early?
 Register FAQ Search Today's Posts Mark Forums Read

 2022-05-03, 16:51 #1 rian   May 2022 1 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?
2022-05-03, 16:59   #2
retina
Undefined

"The unspeakable one"
Jun 2006
My evil lair

655910 Posts

Quote:
 Originally Posted by rian 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 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.

2022-05-03, 17:43   #3
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

666810 Posts

Quote:
 Originally Posted by rian 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

2022-05-03, 18:25   #4
Prime95
P90 years forever!

Aug 2002
Yeehaw, FL

3×11×241 Posts

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.

2022-05-03, 19:01   #5
ATH
Einyen

Dec 2003
Denmark

2×52×67 Posts

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

2022-05-03, 23:17   #6
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

1A0C16 Posts

Quote:
 Originally Posted by rian 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.

Code:
ADVANCED MENU
-------------

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

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

2022-05-03, 23:37   #7
chalsall
If I May

"Chris Halsall"
Sep 2002

3×3,529 Posts

Quote:
 Originally Posted by kriesel There are at least two possible issues with this approach.

We are all very smart. Do we really have to prove it in every message?

2022-05-04, 02:49   #8
mathwiz

Mar 2019

2×3×72 Posts

Quote:
 Originally Posted by chalsall 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).

2022-05-04, 05:24   #9
kriesel

"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

22×1,667 Posts

Quote:
 Originally Posted by mathwiz 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?

 2022-05-04, 12:52 #10 PhilF     "6800 descendent" Feb 2005 Colorado 2×359 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 overly-criticizing other's posting styles also.
2022-05-04, 21:30   #11
mathwiz

Mar 2019

2·3·72 Posts

Quote:
 Originally Posted by PhilF 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post calimero22 Computer Science & Computational Number Theory 7 2018-09-09 16:49 princeps Math 15 2012-04-02 21:49 Arkadiusz Math 6 2011-04-05 19:39 T.Rex Math 0 2004-10-26 21:37 nightic Software 2 2003-06-05 06:25

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

Sun Aug 14 19:18:00 UTC 2022 up 38 days, 14:05, 2 users, load averages: 1.18, 1.10, 1.03