mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

2019-12-24, 06:17   #45
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by paulunderwood In the above paper I stated that it is sufficient to test with minimal r for n<2^64 where a=2^r: gcd(6,n)==1 gcd(a^2-1,n)==1 gcd(a^2-2,n)==1 !issquare(n) kronecker(a^2-4,n)==-1 Mod(Mod1,n)*2*x,x^2-a*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n) Puzzle: use any r rather than a minimal r to find a counterexample. I have tested n< 10^10 and counting.

Solutions:

Code:
? [n,a]=[517567487401, 459234922019];print([n,a,ispseudoprime(n),znlog(a,Mod(2,n)),gcd(a^2-1,n)==1,gcd(a^2-2,n)==1,kronecker(a^2-4,n)==-1,Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n),Mod(a^2-4,n)^((n-1)/2)==-1])
[517567487401, 459234922019, 0, 246436369, 1, 1, 1, 1, 0]
? [n,a]=[517567487401, 470338872881];print([n,a,ispseudoprime(n),znlog(a,Mod(2,n)),gcd(a^2-1,n)==1,gcd(a^2-2,n)==1,kronecker(a^2-4,n)==-1,Mod(Mod(1,n)*2*x,x^2-a*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n),Mod(a^2-4,n)^((n-1)/2)==-1])
[517567487401, 470338872881, 0, 287348929, 1, 1, 1, 1, 0]
The final zeroes indicate that the pair [n, a] did not pass the Euler PRP test. Finding a counterexample that passes with the Euler PRP is not going to be attempted by me

Last fiddled with by paulunderwood on 2019-12-24 at 06:28

 2019-12-30, 01:00 #46 paulunderwood     Sep 2002 Database er0rr 1101000010112 Posts I have uploaded what I hope is the very final draft of my paper. It dots some i's and crosses some t's, inserts missing words, clarifies some points and there is a slight change in when "%" is done in the listed Pari/GP script. The code will be superceded by actual implimenters of the code in other languages such as C/C++/GMP/ASSEMBLY etc.who can do shifts and so forth. What is really hoped by me that it constitutes a proof of primality, or someone can summon up a counterexample.
 2019-12-30, 22:21 #47 paulunderwood     Sep 2002 Database er0rr 1101000010112 Posts The gift that keep on giving Since $2x=a+\sqrt{\Delta}$ and by the Frobenius automorphism $\frac{2}{x}\equiv a-\sqrt{\Delta} \pmod{n,x^2-ax+1}$, by subtraction and dividing out 2 I get $x^2-\sqrt{\Delta}x-1\equiv 0 \pmod{n,x^2-ax+1}$. If it is checked that $\Delta^\frac{n-1}{2}\equiv -1 \pmod{n}$ then all that remains -- apart form the g.c.d.s -- is to check that $(2x)^{n+1}\equiv -4 \pmod{n, x^2+x-1}$. This can only happen for kronecker(5,n)==-1. So a test for such n is: kronecker(5,n)==-1 gcd(a^2-1,n)==1 gcd(a^2-2,n)==1 !issquare(n) kronecker(a^2-4,n)==-1 Mod(a^2-4,n)^((n-1)/2)==-1 Mod(Mod(1,n)*2*x,x^2+x-1)^(n+1)==-4 (Note the last mod cannot take advantage of my 2 selfridge method -- maybe for these there is another trick for "fibonacci" expressions) If a=3 (or a=7) then \Delta is 5 anyway, The above test works for n<2^64 without the test Mod(a^2-4,n)^((n-1)/2)==-1 Last fiddled with by paulunderwood on 2019-12-31 at 11:14
2019-12-31, 11:10   #48
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by paulunderwood I have uploaded what I hope is the very final draft of my paper. It dots some i's and crosses some t's, inserts missing words, clarifies some points and there is a slight change in when "%" is done in the listed Pari/GP script. The code will be superceded by actual implimenters of the code in other languages such as C/C++/GMP/ASSEMBLY etc.who can do shifts and so forth. What is really hoped by me that it constitutes a proof of primality, or someone can summon up a counterexample.
Quote:
 4. Find any r where the Jacobi symbol J(22r − 4, n) is −1 and gcd(22r − 1, n) = 1 and gcd(22r − 2, n) = 1. If one is found with a non-trivial symbol equal to 0 or with either g.c.d. giving a factor before then declare n to be composite.
form the paper is problematic. As forumite ChrisZ pointed out to me in a pm n=2^61-1;b=8;r=41 gives a zero Jacobi symbol for a prime. I have updated the paper to:

Quote:
 4. Find any r where the Jacobi symbol J(b2r − 4, n) is −1. 5. If either gcd(b2r − 1, n) or gcd(b2r − 2, n) gives a factor then declare n to be composite.
And the script therein is cleaned up too.

Last fiddled with by paulunderwood on 2019-12-31 at 11:26

2019-12-31, 16:45   #49
paulunderwood

Sep 2002
Database er0rr

333910 Posts

The revised algorithm did not compute for numbers like 17*257. So I had to revise it again. It now says:

Quote:
 4. Find any r where the Jacobi symbol J(b2r − 4, n) is −1. If while searching either gcd(b2r − 1, n) or gcd(b2r − 2, n) gives a factor then declare n to be composite.
The script has also been updated accordingly in the paper

I hope there no more loopholes.

 2020-01-02, 18:49 #50 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts Counterexamples galore! It is trivial to find counterexamples. Here is one: Code: { [n,b,r]=[53317638559, 47290088223,1]; a=lift(Mod(b,n)^r); if(!ispseudoprime(n)&& !issquare(n)&& gcd(a^2-2,n)==1&& gcd(a^3-a,n)==1&& kronecker(a^2-4,n)==-1&& Mod(a^2-4,n)^((n-1)/2)==-1&& Mod(a,n)^(n-1)==1&& Mod(Mod(1,n)*2*x,x^2-*x+1)^((n+1)/2)==2*kronecker(2*(a+2),n), print("counterexample!")) } counterexample! Last fiddled with by paulunderwood on 2020-01-02 at 18:52
 2020-01-02, 21:42 #51 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts I am trying to patch things up. With r = 1 there are plenty of counterexamples. So we want to avoid any a=b^r=b i.e. b^(r-1)=1. So how about gcd(r-1,n^2-1)==1 as a condition? Edit: Au contraire, a=b^(6*r) seems good, but I will have to do some more experimentation. Last fiddled with by paulunderwood on 2020-01-02 at 23:53
2020-01-04, 11:08   #52
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

:
Quote:
 Originally Posted by paulunderwood I am trying to patch things up. With r = 1 there are plenty of counterexamples. So we want to avoid any a=b^r=b i.e. b^(r-1)=1. So how about gcd(r-1,n^2-1)==1 as a condition? Edit: Au contraire, a=b^(6*r) seems good, but I will have to do some more experimentation.
Actually a=b^(3*r) looks better, Here is my argument:
• a=b^r is problematic.
• does a=b^(3*r) solve it?
• Yes, because b^(3*r)!=b^r since there are checks for gcd(b^(2*r)-1,n)==1 and gcd(b^3-b,n)=1

Let me put it this way: Without all the mathematical arguments and using my intuition and experimental results, primailty can be established in 6 selfridges by running "the algorithm" with a=b^r and with a=b^(3*r). Whether I can prove all this is another matter...

Last fiddled with by paulunderwood on 2020-01-04 at 13:31

2020-01-05, 00:59   #53
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by paulunderwood : Actually a=b^(3*r) looks better, Here is my argument: a=b^r is problematic. does a=b^(3*r) solve it? Yes, because b^(3*r)!=b^r since there are checks for gcd(b^(2*r)-1,n)==1 and gcd(b^3-b,n)=1 Let me put it this way: Without all the mathematical arguments and using my intuition and experimental results, primailty can be established in 6 selfridges by running "the algorithm" with a=b^r and with a=b^(3*r). Whether I can prove all this is another matter...
More experiments foiled the above, but I have another idea...

Let a=3^r. This has a unique solution for "the algorithm" for composites precisely when r=(o+1)/2 where o is the multiplicative group order of 3 mod n
-- proof?

Now for the clever part: Test suitable r and r+1. They can't both have a solution. i.e. pass the tests, If they did then 2*r-1 = o and 2*(r+1) - 1= o. Consequently, 2*r-1 = 2*r+1. That is o = 2. Then 3^2=1 which is illegal and also n would be even. A contradiction.

 2020-01-05, 03:22 #54 carpetpool     "Sam" Nov 2016 4548 Posts Perhaps upon revising your algorithm, maybe testing it on one of the PRPs I sent you.
2020-01-05, 04:08   #55
paulunderwood

Sep 2002
Database er0rr

1101000010112 Posts

Quote:
 Originally Posted by carpetpool Perhaps upon revising your algorithm, maybe testing it on one of the PRPs I sent you.
Rather than coding anything up at the moment. I am running a previous script to see how far it goes:

Code:
{
b=3;forstep(n=3,100000000000000000,2,
if(!ispseudoprime(n)&&Mod(b,n)^(n-1)==1,
a=b;r=1;while(a!=1,
if(kronecker(a^2-4,n)==-1&&gcd(a^2-1,n)==1&&
Mod(Mod(1,n)*b*x,x^2-a*x+1)^((n+1)/2)==b*kronecker(b*(a+2),n),
z=(znorder(Mod(3,n))+1)/2;print([b,n,a,r,z]);
if(z!=r,quit));r++;a=(a*b)%n)))
}
If I turn into a "dual" PRP test then it will be (1)+2+2 selfridges

It just quitted with:

Code:
[3, 1479967201, 970736486, 101203, 124201/2]
It is however still a unique result.

Last fiddled with by paulunderwood on 2020-01-05 at 05:09

 Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 R.D. Silverman Factoring 5 2006-01-26 09:14 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 15:13.

Sat Aug 15 15:13:04 UTC 2020 up 2 days, 11:48, 0 users, load averages: 2.03, 1.92, 1.90