Solving x^2 + x + 1 == 0 (mod mp)

[Batalov]

Originally Posted by paulunderwood

I given this some more thought.

PRP does Mod(3,mp)^(2^p-2) == 1,
which is at best Mod(3,mp)^2^p == 9,
whereas what I propose is Mod(3,mp)^2^(p-1) == -3.

Exactly. Mod(3,mp)^2^p == 9 is the PRP test.

So, for the saving of 1 squaring* you are proposing something that you haven't proved.
It can (?) be proven but you didn't demonstrate it.
And then it will still be a PRP test, whereas LL test is a primality test at another 0.000001% cost of subtracting 2 at each iteration.

Additionally, your code doesn't implement the "square_carefully" for the first and last 30-50 iterations, which could be lead to false positives and negatives for large p values. But P95 likely does.

P.S. Finally, I can't shake the feeling that solving x² + x +1 == 0 (mod mp) wasn't a red herring. Where is it used in this test?
____________
* which is a staggering 0.000001% saving!

[LaurV]

That is the "square root of 9" test (or square root of any quadratic residue). Because m=2^p-1 is 3 (mod 4), then -1 is a non-residue, and therefore one can apply these formulas to get the square root of 9, which, if m is prime, it is either 3 or -3. If m is not prime, you will get other numbers. But the fact that you will get another number is not proved, there are no counterexamples and it is believed to be true, but unless a proof will be available, this is only a PRP test.

[paulunderwood]

If you can solve x^2+3 == 0 (mod mp), then mp is prime, I think

[R. Gerbicz]

Originally Posted by paulunderwood

If you can solve x^2+3 == 0 (mod mp), then mp is prime, I think

False. x=14697820651 and p=37 is a counter-example. Just used Pari-Gp and Wolfram Alpha: https://www.wolframalpha.com/input/?...2%5E37-1%5D%5D

[science_man_88]

Originally Posted by paulunderwood

If you can solve x^2+3 == 0 (mod mp), then mp is prime, I think

I think you should try remainder math within the mersennes themselves or something like that for a while because that can be related somewhat to the reduced LL test. 2*x^2-1 etc. I do have things I've found about it around this forum and in some PM's I've sent at one point but this might help you think about modular math more ?

[paulunderwood]

Originally Posted by R. Gerbicz

False. x=14697820651 and p=37 is a counter-example. Just used Pari-Gp and Wolfram Alpha: https://www.wolframalpha.com/input/?...2%5E37-1%5D%5D

Is this easily done? Can the non-existence of a solution help screen out prime exponents?

[R. Gerbicz]

Originally Posted by paulunderwood

Is this easily done? Can the non-existence of a solution help screen out prime exponents?

The x solution exists iff kronecker(-3,q)=1 for all q|2^p-1, so it doesn't really helps.