mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-02-16, 03:26   #12
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,863 Posts
Thumbs up

Quote:
Originally Posted by paulunderwood View Post
Consider respectively the matrices [1,a;1,1] and [1,1-a;1,1] whose characteristic equations are:

y^2-2*y+1-a=0
y^2-2*y+a=0

with solutions:

y=1+-sqrt(a)
y=1+-sqrt(1-a)

Restrict to kronecker(a,n)==-1 and kronecker(1-a,n)==-1

Now transform the characteristic equations (ignoring Euler "Q"-PRP tests) to

z^2-(4/(1-a)-2)*z+1=0
z^2-(4/a-2)*z+1=0

With a Fermat base 2 PRP test I propose:

Code:
{
tst(n,a)=Mod(2,n)^(n-1)==1&&
kronecker(a,n)==-1&&
kronecker(1-a,n)==-1&&
Mod(Mod(z,n),z^2-(4/(1-a)-2)*z+1)^((n+1)/2)==-1&&
Mod(Mod(z,n),z^2-(4/a-2)*z+1)^((n+1)/2)==-1;
}
Doing the same mathematics with matrices [b,a;1,b] and [b,b^2-a;1,b] leads to a test which is not producing counterexamples:

Code:
{
tst(n,a,b)=local(Q=b^2-a);
kronecker(a,n)==-1&&
kronecker(Q,n)==-1&&
Mod(2,n)^(n-1)==1&&
Mod(Mod(z,n),z^2-(4*b^2/Q-2)*z+1)^((n+1)/2)==-1&&
Mod(Mod(z,n),z^2-(4*b^2/a-2)*z+1)^((n+1)/2)==-1;
}
Furthermore, when a=b=2 then b^2-a=2 which cuts the test down to a Fermat 2-PRP test and a strong Lucas test over z^2-6*z+1

Last fiddled with by paulunderwood on 2021-02-16 at 04:13
paulunderwood is offline   Reply With Quote
Old 2021-02-18, 02:33   #13
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

386310 Posts
Talking Unique solution test

Code:
{
tst(n,a)=local(A=a^2+a);
kronecker(A,n)==-1&&
kronecker(a,n)==-1&&
Mod(A,n)^((n-1)/2)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1
}
I am running this test against Richard Pinch's Carmichael number list and with David Broadhurst's CRT Semi-prime Pari/GP script.

The latter has only produced unique solutions for a given n, making 2 rounds with different a's sufficient for a primality proof?!?!?

Those pesky primes! I just found 2 solutions for 2728624939. However gcd(a1^2-a2^2,n)>1

I have now found n with 3 or 4 solutions too, and gcd(ai^2-aj^2,n)>1 for i != j.

I am seeing the same sort of GCDs for A=a+1 and kronecker(A,n)==-1. Hence the corresponding test can be done for suitable {a, a+1} and {a+1,a+2} which reduces the number of sub-tests, and no GCD need be calculated.

Last fiddled with by paulunderwood on 2021-02-18 at 05:03
paulunderwood is offline   Reply With Quote
Old 2021-02-18, 13:51   #14
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

597910 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
Code:
{
tst(n,a)=local(A=a^2+a);
kronecker(A,n)==-1&&
kronecker(a,n)==-1&&
Mod(A,n)^((n-1)/2)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1
}
I am running this test against Richard Pinch's Carmichael number list and with David Broadhurst's CRT Semi-prime Pari/GP script.
Given a Carmichael number N or a semiprime p*q, what code do you run against it, exactly? Surely you're not looping over possible a, that would take forever.
CRGreathouse is offline   Reply With Quote
Old 2021-02-18, 14:26   #15
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

F1716 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Given a Carmichael number N or a semiprime p*q, what code do you run against it, exactly? Surely you're not looping over possible a, that would take forever.
I found a counterexample to the above test for n=137975195359.

I am now testing:

Code:
{tst(n,a)=kronecker(a,n)==-1&&kronecker(a-1,n)==1&&kronecker(a+1,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&Mod(a-1,n)^((n-1)/2)==1&&Mod(a+1,n)^((n-1)/2)==-1&&
Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==-1;}

{tst1(p,q)=local(n=p*q,u=[]);
for(a=2,p-3,if((n%(p-1)==1)||
Mod(a,p)^(n-1)==1&&Mod(a-1,p)^(n-1)==1&&Mod(a+1,p)^(n-1)==1&&
Mod(Mod(x,p),x^2-(4*a/(a-1)-2)*x+1)^(n+1)==1,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
if(#V,for(v=1,#V,print([n,V[v],gcd(V[v]^2-V[1]^2,n)])));V;}

{forprime(p=7,10000000,for(k=4,12,q=1+2*k*(p-1);
if(ispseudoprime(q),tst2(p,q))));
print("\\\\ "round(gettime/1000)" seconds");}
(For Carmichael I do loop over a and yes it is too slow to run.)

This test has zero or a unique solution for n so far; These unique solutions have either a+3==n or a+1/a+6 == 0 mod n.

I found a non-unique solution. So I have added justifiable Fermat 2-PRP into the test and am running again.

Last fiddled with by paulunderwood on 2021-02-19 at 06:05 Reason: FIXED JACOBI SYMBOL
paulunderwood is offline   Reply With Quote
Old 2021-02-19, 10:41   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,863 Posts
Arrow Rationale

The rationale for the above test:
  1. Matrix: [a,a;1,a]
  2. Characteristic eqn: y^2-2*a+a^2-a==0
  3. Solutions: y = a +- sqrt(a)
  4. "Strong" transform: z^2-2*(a+1)/(a-1)*z+1=0 and Euler-(a^2-a)==-1
  5. Solutions: z = (a+1)/(a-1) +- sqrt((a+1)^2/(a-1)^2 - 1) = (a+1)/(a-1) +- 2*sqrt(a)/(a-1)
  6. Note1: if kronecker(a,n)==-1 and kronecker(a^2-a,n)==-1 then kronecker(a-1,n)==1
  7. Note2: If a=-3 then z^2-z+1 = 0 => cyclotomic
  8. Query1: Why is gcd(a^2+6*a+1,n)==1 needed?
  9. Query2: is there a pseudoprime for this test?

Code:
{
tst(n,a)=
gcd(a+3,n)==1&&
gcd(a^2+6*a+1,n)==1&&
kronecker(a,n)==-1&&
kronecker(a-1,n)==1&&
kronecker(a+1,n)==-1&&
Mod(2,n)^(n-1)==1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(a-1,n)^((n-1)/2)==1&&
Mod(a+1,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(4*a/(a-1)-2)*z+1)^((n+1)/2)==-1;
}
I found 4 counterexamples for n = 6192880203469

Last fiddled with by paulunderwood on 2021-02-21 at 05:49 Reason: wrong n
paulunderwood is offline   Reply With Quote
Old 2021-02-21, 05:21   #17
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

386310 Posts
Question All Euler-PRP = -1

I am now testing:

Code:
{tst(n,a)=kronecker(a,n)==-1&&kronecker(a-1,n)==-1&&kronecker(a+1,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&Mod(a-1,n)^((n-1)/2)==-1&&Mod(a+1,n)^((n-1)/2)==-1&&
Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==1;}

{tst1(p,q)=local(n=p*q,u=[]);
for(a=2,p-2,if((n%(p-1)==1)||
Mod(a,p)^(n-1)==1&&Mod(a-1,p)^(n-1)==1&&Mod(a+1,p)^(n-1)==1&&
Mod(Mod(x,p),x^2-(4*a/(a-1)-2)*x+1)^(n+1)==1,
u=concat(u,a)));Mod(u,p);}

{tst2(p,q)=local(n=p*q,up,uq,a,V=[]);
up=tst1(p,q);if(#up,uq=tst1(q,p);if(#uq,
for(i=1,#up,for(j=1,#uq,a=lift(chinese(up[i],uq[j]));
if(tst(n,a),V=concat(V,a))))));V=vecsort(V);
if(#V,for(v=1,#V,print([n,V[v],gcd(V[v]+3,n),gcd(3*V[v]+1,n),gcd(V[v]^2+6*V[v]+1,n)])));V;}

{forprime(p=7,1000000,for(k=4,12,q=1+2*k*(p-1);
if(ispseudoprime(q)&&Mod(2,p*q)^(p*q)==2,tst2(p,q))));
print("\\\\ "round(gettime/1000)" seconds");}
This takes about 90 hours.

I found a counterexample for n=415681338623.

Now I am testing with a 3-PRP test too since "3" is in the GCDs.

Last fiddled with by paulunderwood on 2021-02-21 at 14:58
paulunderwood is offline   Reply With Quote
Old 2021-02-21, 16:17   #18
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,863 Posts
Default

Latest test:
Code:
{EulerPRP(a,n)=Mod(a,n)^((n-1)/2)==kronecker(a,n);}

{
tst(n,a)=
gcd(a+3,n)==1&&
gcd(3*a+1,n)==1&&
gcd(a^2+6*a+1,n)==1&&
kronecker(a,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
EulerPRP(2,n)&&
EulerPRP(3,n)&&
EulerPRP(a-1,n)&&
EulerPRP(a+1,n)&&
Mod(Mod(x,n),x^2-(4*a/(a-1)-2)*x+1)^((n+1)/2)==kronecker(a*(a-1),n);
}
If this fails I will have hit a brick wall.

Last fiddled with by paulunderwood on 2021-02-21 at 16:33
paulunderwood is offline   Reply With Quote
Old 2021-02-21, 18:57   #19
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,863 Posts
Question Big question

Are the solutions to b^2 = 2^i*3^j + 1 finite? (i, j >= 0)

I have only found b in [2, 3, 5 ,7, 17].

Last fiddled with by paulunderwood on 2021-02-21 at 19:38
paulunderwood is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
I found the primality test, there seems to be no composite numbers that pass the test sweety439 sweety439 7 2020-02-11 19:49
Modifying the Lucas Lehmer Primality Test into a fast test of nothing Trilo Miscellaneous Math 25 2018-03-11 23:20
Double check LL test faster than first run test lidocorc Software 3 2008-12-03 15:12
Will the torture test, test ALL available memory? swinster Software 2 2007-12-01 17:54
A primality test for Fermat numbers faster than P├ępin's test ? T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 16:28.


Wed Oct 20 16:28:05 UTC 2021 up 89 days, 10:57, 0 users, load averages: 1.71, 1.31, 1.43

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.