mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Closed Thread
 
Thread Tools
Old 2021-04-06, 22:04   #23
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

3·43·73 Posts
Smile

To add to what AXN and VBCurtis already said, --
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?
Batalov is offline  
Old 2021-04-06, 23:57   #24
bhelmes
 
bhelmes's Avatar
 
Mar 2016

22·34 Posts
Default

Quote:
Originally Posted by Batalov View Post
@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

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
Attached Files
File Type: c suf_test_primes.c (2.7 KB, 11 views)
bhelmes is online now  
Old 2021-04-07, 00:51   #25
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

106528 Posts
Default

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.
Dr Sardonicus is offline  
Old 2021-04-07, 15:11   #26
bhelmes
 
bhelmes's Avatar
 
Mar 2016

1010001002 Posts
Default

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
File Type: c suf_test_primes.c (3.1 KB, 10 views)
bhelmes is online now  
Old 2021-04-08, 15:35   #27
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2·7·17·19 Posts
Default

Quote:
Originally Posted by bhelmes View Post
@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.
Dr Sardonicus is offline  
Old 2021-04-08, 23:32   #28
bhelmes
 
bhelmes's Avatar
 
Mar 2016

22×34 Posts
Default

13361 is the smallest counterexample for this test.
http://devalco.de/unit_circle/system...php?prim=13361
1+10i was the base.
bhelmes is online now  
Old 2021-04-09, 00:41   #29
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

7·523 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
paulunderwood is offline  
Old 2021-04-09, 00:50   #30
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100110010012 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Batalov is offline  
Old 2021-04-09, 01:13   #31
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

2×7×17×19 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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.
Dr Sardonicus is offline  
Old 2021-04-09, 17:31   #32
bhelmes
 
bhelmes's Avatar
 
Mar 2016

22·34 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
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,

What about an adding pretest like q^((f-1)/2)=f-1 mod f.
This costs only one Selfridge and should exclude the counterexamples.


Quote:
Originally Posted by paulunderwood View Post
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.


bhelmes is online now  
Old 2021-04-09, 19:21   #33
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

71158 Posts
Default

Quote:
Originally Posted by bhelmes View Post
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
paulunderwood is offline  
Closed Thread

Thread Tools


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

All times are UTC. The time now is 07:45.

Fri May 7 07:45:53 UTC 2021 up 29 days, 2:26, 0 users, load averages: 1.28, 1.48, 1.78

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.