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

2020-01-05, 17:15   #56
paulunderwood

Sep 2002
Database er0rr

32·7·53 Posts

Quote:
 Originally Posted by carpetpool 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

2020-01-05, 18:01   #57
paulunderwood

Sep 2002
Database er0rr

333910 Posts

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

 2020-01-07, 21:43 #58 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts 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
2020-01-13, 00:22   #59
paulunderwood

Sep 2002
Database er0rr

64138 Posts

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.
Edit3 15/1/20: Final Version. Results recorded. Slight script change.

Attached Files

Last fiddled with by paulunderwood on 2020-01-15 at 22:52

 2020-01-14, 18:42 #60 paulunderwood     Sep 2002 Database er0rr D0B16 Posts 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
 2020-01-18, 06:27 #61 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts 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
2020-06-29, 02:48   #62
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.
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

 2020-07-08, 06:56 #63 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts 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
 2020-07-16, 23:00 #64 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts 1+1 selfridges I have a 1+1 selfridges test that works for non-Mersenne numbers at least 3372 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 testMod(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
 2020-07-17, 12:03 #65 paulunderwood     Sep 2002 Database er0rr 32×7×53 Posts 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 0l,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
 2020-07-17, 18:11 #66 paulunderwood     Sep 2002 Database er0rr 32·7·53 Posts 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.)

 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 14:03.

Sat Aug 15 14:03:02 UTC 2020 up 2 days, 10:38, 1 user, load averages: 1.72, 1.69, 1.69