mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2021-01-28, 08:33   #1
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Lightbulb kronecker(2,n)==-1 test

All is quiet from this run:

Code:
{
forstep(n=9,100000000,2,
if(!ispseudoprime(n)&&kronecker(2,n)==-1&&
Mod(Mod(x+2,n),x^2-2)^n==-x+2,
print([n])))
}
I can't generalize it without breaking it.
paulunderwood is offline   Reply With Quote
Old 2021-01-29, 18:19   #2
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

Since for the above test I am working mod x^2-2 the value of x can be taken to be sqrt(2) The base is (x+2) or sqrt(2)*(1+x). So I ran to n<2^64 using Feitsma's PSP list with the following program:

Code:
{
for(v=1,#V,n=V[v];
if(kronecker(2,n)==-1&&
Mod(Mod(x+1,n),x^2-2)^n==-x+1,
print([n])))
}
All quiet!

Last fiddled with by paulunderwood on 2021-01-29 at 18:20
paulunderwood is offline   Reply With Quote
Old 2021-01-30, 11:14   #3
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110001000012 Posts
Default generalization

The general test is:

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


I should have known. A counterexample [n,a]=[54029741, 36019827].

If a minimal "a" is used then things might work out, maybe less than the square root of n?


Last fiddled with by paulunderwood on 2021-01-30 at 13:14
paulunderwood is offline   Reply With Quote
Old 2021-02-01, 00:17   #4
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default

I have tested for a<sqrt(n) all Carmichael numbers < 10^14.

Test recap for non-square odd n:
  • a<sqrt(n)
  • Jacobi(a,n)==-1
  • a^((n-1)/2)==-1 (mod n)
  • (x+1)^n==-x+1 (mod n, x^2-a)

Note: by way of the binomial theorem and Frobenius automorphism, for prime n:

x^n+1 = -x + 1 (mod n, x^2-a)

=> x^(n-1) = -1 (mod n, x^2-a)

=> a^((n-1)/2) = -1 mod n

Last fiddled with by paulunderwood on 2021-02-03 at 04:50
paulunderwood is offline   Reply With Quote
Old 2021-02-05, 03:40   #5
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

1110001000012 Posts
Cool

For n==5 mod 8 it seems that testing Mod(Mod(x+1,n),x^2+2)^n==-x+1 is sufficient.
paulunderwood is offline   Reply With Quote
Old 2021-02-09, 02:05   #6
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

70418 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
  • a<sqrt(n)
  • Jacobi(a,n)==-1
  • a^((n-1)/2)==-1 (mod n)
  • (x+1)^n==-x+1 (mod n, x^2-a)
I have tested:
  • Carmichael numbers up to 10^14 with Pari/GP
  • semiprimes with David Broadhurst's CRT Pari/GP script -- 1 hour run
  • now with C+PrimeSieve all applicable "a" for all n < 2.6*10^8 and counting.

Last fiddled with by paulunderwood on 2021-02-15 at 20:50
paulunderwood is offline   Reply With Quote
Old 2021-02-10, 00:04   #7
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Smile

in coding up the above test, I realized that it is 1+3 selfridges -- where a selfridge is the time taken to do a fermat-PRP test. In section 2.5 "Implemenation of the test" [1] they seem to implement it very efficiently. I need to read their paper again to get 1+2 selfridges.

Also x+1 is equivalent to [1,a;1,1] whose determinant is 1-a: An implicit 1-a PRP test is done. A bonus!

[1] An Extended Quadratic Frobenius Primality Test with Average and Worst Case Error Estimates

Edit: having read that section I can see that squaring for intermediate value s*x+t during left-right exponentiation is given by

[s,t] = [2*s*t, (a*s+t)*(s+t)-(a+1)*s*t]

Multiplying by the base x+1 is simply:

[s,t] = [s+t, a*s+t]

Last fiddled with by paulunderwood on 2021-02-10 at 01:21
paulunderwood is offline   Reply With Quote
Old 2021-02-10, 23:29   #8
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E2116 Posts
Default

Taking powers of x+1 (mod n, x^2-a) is the same as taking powers of M:=[1,a;1,1] mod n. The characteristic equation of M is y^2-2*y+1-a=0 whose solutions are y=1 +- sqrt(a). So we can take a Frobenius test of y over (y-1)^2-a, trivially a Fermat -1-PRP test and an Euler-PRP test for base a. Since we know y=1+-x, this Frobenius test is the same as doing it for x+1 over x^2-a.

Why do I require that a<sqrt(n)? I cannot answer this. I know x^2-a == 0 mod n but cannot make further progress.


Last fiddled with by paulunderwood on 2021-02-12 at 01:10
paulunderwood is offline   Reply With Quote
Old 2021-02-14, 21:01   #9
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

E2116 Posts
Thumbs up x+a+1

Powers of x+a+1 (mod n, x^2-a) is the same as powers of [a+1,a;1,a+1] mod n. The characteristic equation of this matrix is:
y^2-2*(a+1)*y+(a+1)^2-a=0 whose solution is y=(a+1)+-sqrt(a). Doing the old Frobenius-Fermat-Euler trick gives the following test:

Code:
{
tst(n,a)=
kronecker(a,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(a+1,n)^n==a+1&&
Mod(Mod(x+a+1,n),x^2-a)^n==-x+a+1
}
Note there is an implicit Fermat a^2+a+1 PRP test from the determinant.

In fact the Frobenius test over y^2-P*y+Q can be transformed into one over z^2-(P^2/Q-2)*z+1 and a base a^2+a+1 Euler PRP test:

Code:
{
tst2(n,a)=local(Q=a^2+a+1);
kronecker(a,n)==-1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(a+1,n)^(n-1)==1&&
Mod(Q,n)^((n-1)/2)==kronecker(Q,n)&&
Mod(Mod(z,n),z^2-(2*a^2+6*a+2)/Q*z+1)^((n+1)/2)==kronecker(Q,n)
}
So two Euler, one Fermat and one Lucas PRP tests. (1+1+1+2 selfridges.)

Unless I made a programming error, no counterexamples so far...

Here is one: [n,a]=[32626447351, 2108403400]. The remedy is to add gcd(X,n)==1 where X=2*a^2+6*a+2.

Here is one that I can't dodge: [n,a] = [27536216921, 3753815259]

Last fiddled with by paulunderwood on 2021-02-15 at 05:20 Reason: Strengthened Lucas PRP test
paulunderwood is offline   Reply With Quote
Old 2021-02-15, 05:42   #10
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Default x+1 revisited -- brain storming

Without much ado, I am testing:

Code:
{
tst(n,a)=local(Q=1-a);
kronecker(a,n)==-1&&
kronecker(Q,n)==-1&&
gcd(a+3,n)==1&&
gcd(3*a+1,n)==1&&
Mod(a,n)^((n-1)/2)==-1&&
Mod(Q,n)^((n-1)/2)==-1&&
Mod(Mod(z,n),z^2-(4/Q-2)*z+1)^((n+1)/2)==-1;
}
I claim 3 rounds are enough with a0, a1 and a2, checking gcd(ai^2 - aj^2,n)>1 for some combination.


Last fiddled with by paulunderwood on 2021-02-15 at 08:23 Reason: formulating
paulunderwood is offline   Reply With Quote
Old 2021-02-15, 22:17   #11
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

3,617 Posts
Wink 1+2+2 selfridges

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;
}

Last fiddled with by paulunderwood on 2021-02-15 at 22:23
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:26.

Mon Apr 12 16:26:02 UTC 2021 up 4 days, 11:06, 1 user, load averages: 1.90, 1.97, 2.09

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.