20210406, 22:04  #23  
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·1,571 Posts 
To add to what AXN and VBCurtis already said, 
Quote:
"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? 

20210406, 23:57  #24  
Mar 2016
101000101_{2} Posts 
Quote:
First changing the title of this thread and then asking ? 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 

20210407, 00:51  #25 
Feb 2017
Nowhere
1000110111000_{2} 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^(f1) == 1 (mod fR) for every multiplicatively invertible residue in (R/fR). Thus r^((f1)/4) is a fourth root of 1 for every invertible r. For the choice of r = a + b*i, we have r^((f1)/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. 
20210407, 15:11  #26 
Mar 2016
5^{2}×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. 
20210408, 15:35  #27 
Feb 2017
Nowhere
4536_{10} Posts 
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 nonresidue (mod f), then (Mod(a,f) + Mod(b,f)*i)^((f1)/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 nonresidue (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)^(f1)/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. 
20210408, 23:32  #28 
Mar 2016
5^{2}×13 Posts 
13361 is the smallest counterexample for this test.
http://devalco.de/unit_circle/system...php?prim=13361 1+10i was the base. 
20210409, 00:41  #29  
Sep 2002
Database er0rr
3,673 Posts 
Quote:
Last fiddled with by paulunderwood on 20210409 at 00:42 

20210409, 00:50  #30 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2·3·1,571 Posts 

20210409, 01:13  #31  
Feb 2017
Nowhere
1000110111000_{2} Posts 
Quote:
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 P_{1} and P_{2}. Then R/fR = R/P_{1} x R/P_{2}; 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 nonresidue (mod f), then a + b*i will be a square in one of these copies, but not in the other^{†}; say in R/P_{1} but not in R/P_{2}. As a consequence, (Mod(a,f) + Mod(b,f)*i)^((f1)/2) = Mod(C,f) + Mod(D, f)*i == +1 in R/P_{1} but 1 in R/P_{2}. Since P_{1} and P_{2} are conjugate, taking complex conjugates gives Mod(C,f)  Mod(D,f)*i == 1 in R/P_{1} but +1 in R/P_{2}; 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)^((f1)/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, P_{1} = (1 + 4*i)R, P_{2} = (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/P_{1} and R/P_{2}. 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 P_{1}, but none of the differences are in P_{2}; that is, 1 + 2*i is a square in R/P_{1} but not in R/P_{2}. 

20210409, 17:31  #32  
Mar 2016
145_{16} Posts 
Quote:
What about an adding pretest like q^((f1)/2)=f1 mod f. This costs only one Selfridge and should exclude the counterexamples. Quote:
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. 

20210409, 19:21  #33  
Sep 2002
Database er0rr
3,673 Posts 
Quote:
Last fiddled with by paulunderwood on 20210409 at 19:24 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
1+1 Selfridges PRP test  paulunderwood  Miscellaneous Math  21  20201120 13:16 
For which types of primes is GPU primality test software available?  bur  GPU Computing  6  20200828 06:20 
Beta test project found new primes  ltd  Prime Sierpinski Project  7  20060923 04:53 
Re New test for Mersenne Primes  K Ramsey  Miscellaneous Math  6  20060604 09:45 
Alternative Test for Primes.  mfgoode  Math  37  20060319 18:03 