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

9,431 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

32510 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, 15 views)

 2021-04-07, 00:51 #25 Dr Sardonicus     Feb 2017 Nowhere 26×71 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, 16 views)

2021-04-08, 15:35   #27
Dr Sardonicus

Feb 2017
Nowhere

11C016 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

2×11×167 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

24D716 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

10001110000002 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

52·13 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

71328 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

 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 08:27.

Fri May 14 08:27:14 UTC 2021 up 36 days, 3:08, 0 users, load averages: 2.56, 2.54, 2.13