Will Fermat primality test fail early?

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





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?

[retina]

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.

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.

[kriesel]

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.

[Prime95]

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.

I hope your checks included visiting this page: https://www.mersenne.org/report_exponent/

[ATH]

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.

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.

[kriesel]

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.

From mprime's readme.txt:

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.

[chalsall]

Originally Posted by kriesel

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?

[mathwiz]

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

[kriesel]

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?

[PhilF]

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.

[mathwiz]

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:

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.