 mersenneforum.org a d̶e̶t̶e̶r̶m̶i̶n̶i̶s̶t̶i̶c̶ test for primes p=1 or p=7 mod 8 with 2 (??) Selfridges
 Register FAQ Search Today's Posts Mark Forums Read  2021-04-06, 22:04   #23
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100110100102 Posts Quote:
 -- Professor! I have invented the universal solvent! It dissolves everything! -- Very well, but where do you keep it? (!)
Or in the words of my newfound (old) friend Steven Wright:
"You can't have everything. Where would you put it?"

@B.H. Why would you expect me to answer your question if you completely ignored mine and left it without answer?  2021-04-06, 23:57   #24
bhelmes

Mar 2016

5058 Posts Quote:
 Originally Posted by Batalov @B.H. Why would you expect me to answer your question if you completely ignored mine and left it without answer?
A peaceful and pleasant night for you, Batalov

Nevertheless I gave a mathematical explication and some arguments just some messages before.

There is an implementation in php of the algorithm in the attachment availible. (I changed the .php to .c, otherwise I could not upload it)

The implementation of the algorithm is not difficult to understand.

Enjoy your coffee and the algorithm   Attached Files suf_test_primes.c (2.7 KB, 14 views)  2021-04-07, 00:51 #25 Dr Sardonicus   Feb 2017 Nowhere 11B916 Posts If f is prime and f == 7 (mod 8) , q is prime, q == 1 (mod 4) and (q/f) = -1, let q = a^2 + b^2; a, b integers. Let R = Z[i], the ring of Gaussian integers. Then R/fR = GF(f^2), the field of f^2 elements. Then (a + b*i)^f == a - b*i (mod fR) so (a + b*i)^(f+1) == q (mod fR). So if (a + b*i)^((f+1)/4) = c + d*i (mod fR), we have (c + d*i)^4 == q (mod fR). Since (q/f) = -1, we have c*d =/= 0 (mod f). That's probably enough to show that c + d*i == c + c*i or c - c*i (mod f), but I'm too lazy to work out the details. I do not see offhand a way to decide between c + c*i and c - c*i. So for f == 7 (mod 8), f prime implies something close to what you seem to be claiming. As to the reverse implication, that the congruence implies f is prime, I would be more inclined to look for counterexamples than a proof. If f is prime and f == 1 (mod 8), fR splits into two prime ideals of norm f, and, consequently r^(f-1) == 1 (mod fR) for every multiplicatively invertible residue in (R/fR). Thus r^((f-1)/4) is a fourth root of 1 for every invertible r. For the choice of r = a + b*i, we have r^((f-1)/4) = c + d*i (mod fR) is a primitive fourth root of unity, so the values of c and d are square roots of 1/2 (mod f). I don't see any reason offhand to conclude that they are the same square root of 1/2 (mod f). As with the other case, I would be more inclined to look for counterexamples to the reverse implication than a proof.  2021-04-07, 15:11   #26
bhelmes

Mar 2016

52·13 Posts The last program version had some errors, which I fixed in the new attached version. You have to substitute .c with .php

I think the program is easy to understand.

I run up to 8000 and there was no counterexample.
(php is a bit slow ...)

@Dr. Sardonicus : Do I verify the 4th or the 8th root ?

@Batalov : I think, a simple fermat test costs one Selfridge,
a test in the complex plane 3 Selfridges, but a test in the complex plane reduced to the unit circle 2. I would like to use the last one. Correctify me, if I am wrong.
Attached Files suf_test_primes.c (3.1 KB, 14 views)  2021-04-08, 15:35   #27
Dr Sardonicus

Feb 2017
Nowhere

11B916 Posts Quote:
 Originally Posted by bhelmes @Dr. Sardonicus : Do I verify the 4th or the 8th root ?
My bad, it's a fourth root of 1 when f == 1 (mod 8) is prime. Computing a few examples indicates that when

f is prime, f == 1 (mod 8), and the odd prime q = a^2 + b^2 is a quadratic non-residue (mod f),

then (Mod(a,f) + Mod(b,f)*i)^((f-1)/4) = c + d*i with c^2 == d^2 (mod f),

but it is not clear to me why c^2 == d^2 (mod f) in this case. There's almost certainly an "obvious" reason I'm simply overlooking.

I note that 29 = 2^2 + 5^2 is a quadratic non-residue (mod 17), and

(Mod(2,17)+ Mod(5,17)*i)^4 == 7 - 7*i (mod 17R).

In any case, (c^2 + d^2)^2 == (a^2 + b^2)^(f-1)/2 == -1 (mod f).

The complication in this case is that with R = Z[i] as before, fR is no longer prime; R/fR is the direct product of two copies of the finite field of f elements, corresponding to the two conjugate factors of fR.  2021-04-08, 23:32 #28 bhelmes   Mar 2016 52·13 Posts 13361 is the smallest counterexample for this test. http://devalco.de/unit_circle/system...php?prim=13361 1+10i was the base.     2021-04-09, 00:41   #29
paulunderwood

Sep 2002
Database er0rr

3,673 Posts Quote:
 Originally Posted by bhelmes 13361 is the smallest counterexample for this test. http://devalco.de/unit_circle/system...php?prim=13361 1+10i was the base.   Nice try. n==3 mod 4 has no counterexample for the two selfridges test (2+i)^(n+1)==5 mod (n,i^2+1) for n<2^50.

Last fiddled with by paulunderwood on 2021-04-09 at 00:42  2021-04-09, 00:50   #30
Batalov

"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·3·1,571 Posts Quote:
 Originally Posted by bhelmes 13361 is the smallest counterexample for this test.
Now I believe that it is deterministic It is a bilingual illiterate* deterministic not-a-test!

____
* (c) by Steven Wright.  2021-04-09, 01:13   #31
Dr Sardonicus

Feb 2017
Nowhere

13·349 Posts Quote:
 Originally Posted by bhelmes 13361 is the smallest counterexample for this test. http://devalco.de/unit_circle/system...php?prim=13361 1+10i was the base.   Ah, excellent! You've learned something: As a definitive primality test, as Dr. McCoy might have said, "It's dead, Jim."

You might also consider in future looking for counterexamples before posting about "definitive primality tests" entailing implications that "go the wrong way."

I also learned something. I finally realized something fairly obvious about the case f prime, f == 1 (mod 8). In R = Z[i], f is the product of two conjugate prime ideals, say P1 and P2.

Then R/fR = R/P1 x R/P2; the direct product of two copies of the finite field of f elements. These are "different" copies, though.

If q = a^2 + b^2 is a quadratic non-residue (mod f), then a + b*i will be a square in one of these copies, but not in the other; say in R/P1 but not in R/P2. As a consequence,

(Mod(a,f) + Mod(b,f)*i)^((f-1)/2) = Mod(C,f) + Mod(D, f)*i == +1 in R/P1 but -1 in R/P2. Since P1 and P2 are conjugate, taking complex conjugates gives

Mod(C,f) - Mod(D,f)*i == -1 in R/P1 but +1 in R/P2; that is

Mod(C,f) - Mod(D,f)*i == -(Mod(C,f) + Mod(D,f)*i); that is, C = 0.

Now for (Mod(a,f) + Mod(b,f)*i)^((f-1)/4) = Mod(c,f) + Mod(d, f)*i, whose square is Mod(C,f) + Mod(D, f), this means Mod(c^2 - d^2, f) = 0; that is, d = c or -c.

It was actually kind of interesting seeing this play out in an actual example. I took f = 17, P1 = (1 + 4*i)R, P2 = (1 - 4*i)R, q = 5, and a + b*i = 1 + 2*i. The squares (mod 17) are 1, 2, 4, 8, 9, 13, 15, and 16. These may also be used to represent the squares in R/P1 and R/P2.

Taking 1 + 2*i - 1, 2, 4, 8, 9, 13, 15, and 16, we find that 1 + 2*i - 9 = -8 + 2*i = 2*i*(1 + 4*i) is in P1, but none of the differences are in P2; that is, 1 + 2*i is a square in R/P1 but not in R/P2.  2021-04-09, 17:31   #32
bhelmes

Mar 2016

14516 Posts Quote:
 Originally Posted by Dr Sardonicus If q = a^2 + b^2 is a quadratic non-residue (mod f), then a + b*i will be a square in one of these copies, but not in the other†; say in R/P1 but not in R/P2. As a consequence,

This costs only one Selfridge and should exclude the counterexamples.

Quote:
 Originally Posted by paulunderwood n==3 mod 4 has no counterexample for the two selfridges test (2+i)^(n+1)==5 mod (n,i^2+1) for n<2^50.

Thanks a lot of your amazing work, I get a bit jealous of your speed.

@Batalov: Sure it is deterministic, sometime you have to add some conditions.   2021-04-09, 19:21   #33
paulunderwood

Sep 2002
Database er0rr

3,673 Posts Quote:
 Originally Posted by bhelmes What about an adding pretest like q^((f-1)/2)=f-1 mod f. This costs only one Selfridge and should exclude the counterexamples.
Whatever you do with 1+1+1+..+1+2 selfridges there will always be counterexamples if you allow a free parameter. I am not saying there will not exist counterexamples for 1+1+1..+1+2+2 -- they are just harder to find. The exception being the classical proofs.

Last fiddled with by paulunderwood on 2021-04-09 at 19:24  Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post paulunderwood Miscellaneous Math 21 2020-11-20 13:16 bur GPU Computing 6 2020-08-28 06:20 ltd Prime Sierpinski Project 7 2006-09-23 04:53 K Ramsey Miscellaneous Math 6 2006-06-04 09:45 mfgoode Math 37 2006-03-19 18:03

All times are UTC. The time now is 21:10.

Tue May 11 21:10:48 UTC 2021 up 33 days, 15:51, 0 users, load averages: 3.03, 2.49, 2.16