mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2020-01-05, 17:15   #56
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 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.
Here is my latest creation, which is (1)+(1)+(1)+(2)+2 selfridges:

Code:
// Usage: b3(n,opt1,opt2,opt3,opt4) where:
//  opt1: (3^(2*r)-4)^((n-1)/2) = -1
//  opt2: (3^(2*(r+1))-4)^((n-1)/2) = -1
//  opt3: (3)^(n-1) = 1
//  opt4: (3*x)^((n+1)/2) = 3*kronecker(3*(3^(r+1)+2),n)
// default: (3*x)^((n+1)/2) = 3*kronecker(3*(3^(r)+2),n)
// b3(n,1,1,1,1) : good for large batch work
// b3(n,0,0,0,0) : the quickest test
// b3(n,0,0,0,1) : most likely not needed for large numbers
{
b3(n,opt1,opt2,op3,opt4)=
local(r=1,A=a=3,Sq,nm1=n-1,nm1d2=nm1/2,BIN,LEN,k,s,t,temp);
if(n==2||n==3||n==5||n==7||n==11||n==13||n==757||n==1093||n==2269||n==797161,return(1));
if(gcd(420,n)!=1,return(0));
if(issquare(n),return(0));
Sq=a*a;while(kronecker(Sq-4,n)!=-1||kronecker(9*Sq-4,n)!=-1,
 r++;a=(a*3)%n;Sq=a*a;if(a==A,return(0)));
if(opt1&&Mod(Sq-4,n)^nm1d2!=-1,return(0));
if(opt2&&Mod(9*Sq-4,n)^nm1d2!=-1,return(0));
if(opt3&&Mod(3,n)^nm1!=1,return(0));
BIN=binary(n+1);LEN=length(BIN)-1;
s=3;t=0;for(k=2,LEN,
 temp=(s*(a*s+2*t))%n;t=((t-s)*(t+s))%n;s=temp;
 if(BIN[k],temp=3*a*s+3*t;t=-3*s;s=temp));
if(s%n!=0||t%n!=(3*kronecker(3*(a+2),n))%n,return(0));
if(opt4,a=a*3;s=3;t=0;for(k=2,LEN,
 temp=(s*(a*s+2*t))%n;t=((t-s)*(t+s))%n;s=temp;
 if(BIN[k],temp=3*a*s+3*t;t=-3*s;s=temp));
 if(s%n!=0||t%n!=(3*kronecker(3*(a+2),n))%n,return(0)));
return(1);
}

Last fiddled with by paulunderwood on 2020-01-05 at 19:08
paulunderwood is offline   Reply With Quote
Old 2020-01-05, 18:01   #57
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
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.
I have reached 4.2*10^10 -- all unique. Time to switch to GMP.

Edit: GMP has reached 2.2*10^11 and still any passes are unique for an n.

Also the above example is the only one for which 2*r != o+1. It is also the only one for which n%4==1 and the only one for which n%6==1. But, I am no closer to a proof of uniqueness nor why the original amazing 6 version has no counterexamples for n<1.8*10^13.

Edit 2: There are 1393 "counterexamples" for n<10^12. Given n they are all unique.

Last fiddled with by paulunderwood on 2020-01-13 at 08:39
paulunderwood is offline   Reply With Quote
Old 2020-01-07, 21:43   #58
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333910 Posts
Default

Flip-flopping back to the \(2x = b^r + \sqrt{\Delta}\) where \(\Delta\) is the discriminant of the equation \(x^2-b^rx+1=0\). Let \(a=b^r\) and \(b=2\). Then \[2x = 2^r + \sqrt{\Delta}\].
It was discussed in my (ill-fated) paper that taking a Frobenius 2x-PRP implied a Fermat 2-PRP test. Furthermore, without the Euler \(\Delta\)-PRP test there is a counterexample for n=517567487401 and r=246436369. My latest idea is to take Fermat 2-PRP out of the Frobenius test and put in Euler \(\Delta\)-PRP test, but since 2 divides \(\Delta\) it actually remains! To wit I have the following test which I will code up in GMP and run a verification test.

Let a=2^r and D=4^r-4 and test:
  • gcd(3,n)=1
  • !issquare(n)
  • kronecker(D,n)=-1
  • gcd(a^2-1,n)=1
  • gcd(a^2-2,n)=1
  • Mod(2,n)^(n-1)=1
  • Mod(Mod(1,n)*D*x,x^2-a*x+1)^(n+1)=D^2


Last fiddled with by paulunderwood on 2020-01-13 at 07:27
paulunderwood is offline   Reply With Quote
Old 2020-01-13, 00:22   #59
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Here is the relevant paper, which will be updated with more test results as they come in.

Edit 14/1/20: Tested to n<5*10^11. Pari/GP script change, squishing a bug.
Edit2 14/1/20: Made the Frobenius test tighter. Script adjusted accordingly.
Edit3 15/1/20: Final Version. Results recorded. Slight script change.


Last fiddled with by paulunderwood on 2020-01-15 at 22:52
paulunderwood is offline   Reply With Quote
Old 2020-01-14, 18:42   #60
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default Brainstorming again.

So the solutions for x of x^2-a*x+1 = 0 are \[x=\frac{a\pm\sqrt{\Delta}}{2}\] Multiplying by \(\Delta\) we get \[\Delta x=\frac{\Delta a\pm\sqrt{\Delta^3}}{2}\]Sub-testing Frobenius \(\Delta x\)-PRP and Fermat a-PRP preserves the automorphism: \[\frac{\Delta}{x}=\frac{\Delta a\mp\sqrt{\Delta^3}}{2}\].

Tests look good now -- no more elementry pseudoprimes (except for "a" a power of 3). I will do some more testing and write up a "a Free Parameter" paper.

Counterexamples found with David Broadhurst's script.

There seems to be no way I can get a general case -- just a=2^r seems to work and that is as hard as BPSW to find a counterexample. I give up!

Last fiddled with by paulunderwood on 2020-01-14 at 23:15
paulunderwood is offline   Reply With Quote
Old 2020-01-18, 06:27   #61
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333910 Posts
Default

Well that about wraps it up for this thread. I will check the 2 selfridge original amazing 6 up to 1.5*10^14.

Here is some (1)+(1)+(2)+2 selfridges code that is pseudoprime-defying:

Code:
// Usage: t56(n,par1,opt1,opt2,opt3) where:
//  par1: trial division limit -- must be less than n.
//  opt1: (5^(2*r)-4)^((n-1)/2) = -1 (mod n)
//  opt2: (6^(2*r)-4)^((n-1)/2) = -1 (mod n)
//  opt3: (5*x)^((n+1)/2) = 5*kronecker(5*(5^(r)+2),n) (mod n, x^2-5^r*x+1)
//  default: (6*x)^((n+1)/2) = 6*kronecker(6*(6^(r)+2),n) (mod n, x^2-6^r*x+1)
// t56(n,10000,1,1,1) : good for large batch work
// t56(n,0,0,0,0) : the quickest test for a single n
// t56(n,0,0,0,1) : most likely not needed
{
t56(n,par1,opt1,op2,opt3)=
local(r=1,a=5,A=6,Sq,g,nm1d2=(n-1)/2,BIN,LEN,k,s,t,temp);
if(n==2||n==3||n==5||n==7||n==11||n==13,return(1));
if(gcd(60060,n)!=1,return(0));
if(issquare(n),return(0));
forprime(p=17,par1,if(n%p==0,return(0)));
if(opt1||opt3,
Sq=a*a;while(kronecker(Sq-4,n)!=-1,
g=gcd((Sq-1)*(Sq-2),n);if(1<g&&g<n,return(0),a=a*5%n;Sq=Sq*25%n));
g=gcd((Sq-1)*(Sq-2),n);if(1<g&&g<n,return(0)));
if(opt1&&Mod(Sq-4,n)^nm1d2!=-1,return(0));
Sq=A*A;while(kronecker(Sq-4,n)!=-1,
g=gcd((Sq-1)*(Sq-2),n);if(1<g&&g<n,return(0),A=A*6%n;Sq=Sq*36%n));
g=gcd((Sq-1)*(Sq-2),n);if(1<g&&g<n,return(0));
if(opt2&&Mod(Sq-4,n)^nm1d2!=-1,return(0));
BIN=binary(n+1);LEN=length(BIN)-1;
if(opt3,
s=5;t=0;for(k=2,LEN,
 temp=(s*(a*s+2*t))%n;t=((t-s)*(t+s))%n;s=temp;
 if(BIN[k],temp=5*a*s+5*t;t=-5*s;s=temp));
if(s%n!=0||t%n!=5*kronecker(5*(a+2),n)%n,return(0)));
s=6;t=0;for(k=2,LEN,
 temp=(s*(A*s+2*t))%n;t=((t-s)*(t+s))%n;s=temp;
 if(BIN[k],temp=6*A*s+6*t;t=-6*s;s=temp));
if(s%n!=0||t%n!=6*kronecker(6*(A+2),n)%n,return(0));
return(1);
}

Last fiddled with by paulunderwood on 2020-01-18 at 20:10
paulunderwood is offline   Reply With Quote
Old 2020-06-29, 02:48   #62
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.
If we use the polynomial x^2-2^r*x-1 instead and further let r=0, the test is
  • gcd(6,n)==1
  • !issquare(n)
  • kronecker(5,n)==-1
  • Mod(Mod(1,n)*2*x,x^2-x-1)^(n+1)==-4

Which is similar to Chen and Greene, but can be further strengthened with incumbent Mod(5,n)^((n-1)/2)==-1 (Euler).

Last fiddled with by paulunderwood on 2020-06-29 at 03:57
paulunderwood is offline   Reply With Quote
Old 2020-07-08, 06:56   #63
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Default Q=-1 and a 35/45 selfridge test?

Based on the solutions to x^2-a*x-1=0, the following test seems to have, where they exist, 6 solutions for n==1 mod 4, or 8 solutions for n==3 mod 4. (a<=(n-1)/2). I have only tested semiprimes! Are there more solutions for more than 2 factors?

{
tst(n,a)=gcd(6,n)==1&&
!issquare(n)&&
gcd(a^2+1,n)==1&&
gcd(a^2+2,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-a*x-1)^(n+1)==-4;
}

This test is 1+1+3 selfridges. So are 35/45 selfridges enough to prove primality?

With a=2^r there are no solutions to the above test, even without the Euler PRP sub-test, for n<1679173512841 -- 3 selfridges.

Edit: 22446821032921, has 12 solutions for "a" non-powers of 2. Bang goes the "35/45 selfridges" idea.

Edit2: 28818109404559 has 16 solutions -- still now powers of 2 below that for certain semiprimes. For any n<2130149048737 the 3 selfridges test is enough when a=2^r

Edit3: 51060231479447 has 24 solutions. Conjecture: (For semiprimes) the solutions, where they exist, number 2^i*3^j, i+j>1.

Edit4: 179632779884293, has 10 solutions.

Last fiddled with by paulunderwood on 2020-07-19 at 07:31
paulunderwood is offline   Reply With Quote
Old 2020-07-16, 23:00   #64
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

333910 Posts
Default 1+1 selfridges

I have a 1+1 selfridges test that works for non-Mersenne numbers at least 337<n<1M and Carmichael Number < 10^16 and PSP-2 < 2*10^11 (in progress)
  • gcd(6,n)==1
  • !issquare(n)
  • find the minimal r>2 and let a=2^r:
    • kronecker(a^2-4,n)==-1
    • kronecker(a^2+4,n)==-1
    • gcd(a^6-1,n)==1
    • gcd(r,n-1)==1
  • and then test
    • Mod(a^2+4,n)^((n-1)/2)==-1
    • Mod(a-2,n)^((n-1)/2)==kronecker(a-2,n)
Here is the code I used:

Code:
{
forstep(n=11,1000000,2,
if(gcd(6,n)==1&&!ispseudoprime(n)&&!issquare(n),
r=3;a=2^r;while(kronecker(a^2-4,n)!=-1||
 kronecker(a^2+4,n)!=-1||
 gcd(a^6-1,n)!=1||
 gcd(r,n-1)!=1,
r++;a*=2;if(a>n,a-=n);if(a==1,break));
if(a!=1&&
 Mod(a-2,n)^((n-1)/2)==kronecker(a-2,n)&&
 Mod(a^2+4,n)^((n-1)/2)==-1,
  print([n,a]))))
}
Edit I made a coding error So conclusions are bad.

Last fiddled with by paulunderwood on 2020-07-17 at 06:35
paulunderwood is offline   Reply With Quote
Old 2020-07-17, 12:03   #65
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32×7×53 Posts
Default

Here is a test that will test all n<2^64

gcd(30,n)==1;
Mod(2,n)^((n-1)/2)==kronecker(2,n)
Mod(3,n)^((n-1)/2)==kronecker(3,n)
Mod(7,n)^((n-1)/2)==kronecker(7,n)
Mod(15,n)^((n-1)/2)==kronecker(15,n)
Mod(31,n)^((n-1)/2)==kronecker(31,n)
Mod(63,n)^((n-1)/2)==kronecker(63,n)
Mod(127,n)^((n-1)/2)==kronecker(127,n)
Mod(255,n)^((n-1)/2)==kronecker(255,n)
Mod(511,n)^((n-1)/2)==kronecker(511,n)
Mod(1023,n)^((n-1)/2)==kronecker(1023,n)

Let a=5^r with minimal 0<r< log(n)
(If log(n) is exceeded declare n to be composite.)
Find kronecker(a,n)==-1
Test Mod(a,n)^((n-1)/2)==-1

Here is the program I used on Feitsma's 2-PSP list:

Code:
{
b=5;for(v=1,#V,n=V[v];if(gcd(30,n)==1&&
Mod(2,n)^((n-1)/2)==kronecker(2,n)&&
Mod(3,n)^((n-1)/2)==kronecker(3,n)&&
Mod(7,n)^((n-1)/2)==kronecker(7,n)&&
Mod(15,n)^((n-1)/2)==kronecker(15,n)&&
Mod(31,n)^((n-1)/2)==kronecker(31,n)&&
Mod(63,n)^((n-1)/2)==kronecker(63,n)&&
Mod(127,n)^((n-1)/2)==kronecker(127,n)&&
Mod(255,n)^((n-1)/2)==kronecker(255,n)&&
Mod(511,n)^((n-1)/2)==kronecker(511,n)&&
Mod(1023,n)^((n-1)/2)==kronecker(1023,n),
 t=1;a=b;r=1;l=log(n);while(kronecker(a,n)!=-1,
 if(gcd(a-1,n)!=1,t=0;break);
 a*=b;a%=n;r++;if(a==1||r>l,t=2;break));
if(t==1&&Mod(a,n)^((n-1)/2)==-1,print([n,a,l]))))
}
Instead of the numbers above, I can use 2,3,5,7,11,13,17,19 which is quicker.

Edit: Testing for kronecker(5^r,n)==-1 is stupid. I can replace it with kronecker(a^2-4,n)==-1 and test Mod(a^2-4,n)==-1. For this I need 2,3,5,7,11,13,17,19,23,29,31,37 and b=2

Last fiddled with by paulunderwood on 2020-07-17 at 16:14 Reason: not needed 2047
paulunderwood is offline   Reply With Quote
Old 2020-07-17, 18:11   #66
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

32·7·53 Posts
Cool tests for n%4==3 and n%4==1

You may be familiar with the test for n = 3 mod 4:

Mod(Mod(1,n)*x+2,x^2+1)^(n+1)==5 (2 selfridges),

I have a test for the other half, n = 1 mod 4:

Code:
{
forstep(n=1,10000000000,4,
if(gcd(6,n)==1&&
Mod(2,n)^n==2&&
!ispseudoprime(n)&&
!issquare(n),
 a=4;while(kronecker(a^2-4,n)!=-1,a*=2;a%=n;if(a==1,break));
 r=Mod(Mod(1,n)*x,x^2-a*x+1)^(n+1);
 if(r==1,print([n,a]))))
}
Silence is golden for this 1+2 selfridges test!

That is:
  • gcd(6,n)==1
  • !issquare(n)
  • a=2^r minimal r>1: kronecker(a^2-4,n)==-1
  • Mod(2,n)^n==2
  • Mod(Mod(1,n)*x,x^2-a*x+1)^(n+1)==1

The last two steps can be combined into 2 selfridges thusly:

Mod(Mod(1,n)*2*x,x^2-a*x+1)^(n+1)==4

(Note: this stems from earlier posts in this thread, and the second test here can be applied to n = 3 mod 4 as well.)
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 14:51.

Sat Aug 15 14:51:04 UTC 2020 up 2 days, 11:26, 1 user, load averages: 1.91, 1.79, 1.75

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.