mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2019-12-24, 06:17   #45
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-12-30, 01:00   #46
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010112 Posts
Default

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.

paulunderwood is offline   Reply With Quote
Old 2019-12-30, 22:21   #47
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010112 Posts
Thumbs up 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
paulunderwood is offline   Reply With Quote
Old 2019-12-31, 11:10   #48
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2019-12-31, 16:45   #49
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333910 Posts
Default

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.
paulunderwood is offline   Reply With Quote
Old 2020-01-02, 18:49   #50
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default 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
paulunderwood is offline   Reply With Quote
Old 2020-01-02, 21:42   #51
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

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
paulunderwood is offline   Reply With Quote
Old 2020-01-04, 11:08   #52
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

:
Quote:
Originally Posted by paulunderwood View Post
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
paulunderwood is offline   Reply With Quote
Old 2020-01-05, 00:59   #53
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
:

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.

paulunderwood is offline   Reply With Quote
Old 2020-01-05, 03:22   #54
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

4548 Posts
Post

Perhaps upon revising your algorithm, maybe testing it on one of the PRPs I sent you.
carpetpool is offline   Reply With Quote
Old 2020-01-05, 04:08   #55
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1101000010112 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Don't miss this amazing trick that the moon is going to do! Uncwilly Astronomy 6 2018-02-01 05:40
Amazing result in P-1 Miszka Information & Answers 2 2014-07-04 17:11
Amazing academic resource Xyzzy Lounge 6 2012-03-25 22:57
Amazing!!! R.D. Silverman Factoring 5 2006-01-26 09:14
Two Amazing Things 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.