20210128, 08:33  #1 
Sep 2002
Database er0rr
4,129 Posts 
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^22)^n==x+2, print([n]))) } 
20210129, 18:19  #2 
Sep 2002
Database er0rr
1000000100001_{2} Posts 
Since for the above test I am working mod x^22 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^22)^n==x+1, print([n]))) } Last fiddled with by paulunderwood on 20210129 at 18:20 
20210130, 11:14  #3 
Sep 2002
Database er0rr
4,129 Posts 
generalization
The general test is:
Code:
{ tst(a,n)= kronecker(a,n)==1&&Mod(a,n)^((n1)/2)==1&& Mod(Mod(x+1,n),x^2a)^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 20210130 at 13:14 
20210201, 00:17  #4 
Sep 2002
Database er0rr
10041_{8} Posts 
I have tested for a<sqrt(n) all Carmichael numbers < 10^14.
Test recap for nonsquare odd n:
Note: by way of the binomial theorem and Frobenius automorphism, for prime n: x^n+1 = x + 1 (mod n, x^2a) => x^(n1) = 1 (mod n, x^2a) => a^((n1)/2) = 1 mod n Last fiddled with by paulunderwood on 20210203 at 04:50 
20210205, 03:40  #5 
Sep 2002
Database er0rr
4,129 Posts 
For n==5 mod 8 it seems that testing Mod(Mod(x+1,n),x^2+2)^n==x+1 is sufficient.

20210209, 02:05  #6  
Sep 2002
Database er0rr
4,129 Posts 
Quote:
Last fiddled with by paulunderwood on 20210215 at 20:50 

20210210, 00:04  #7 
Sep 2002
Database er0rr
4,129 Posts 
in coding up the above test, I realized that it is 1+3 selfridges  where a selfridge is the time taken to do a fermatPRP 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 1a: An implicit 1a 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 leftright 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 20210210 at 01:21 
20210210, 23:29  #8 
Sep 2002
Database er0rr
4,129 Posts 
Taking powers of x+1 (mod n, x^2a) is the same as taking powers of M:=[1,a;1,1] mod n. The characteristic equation of M is y^22*y+1a=0 whose solutions are y=1 + sqrt(a). So we can take a Frobenius test of y over (y1)^2a, trivially a Fermat 1PRP test and an EulerPRP test for base a. Since we know y=1+x, this Frobenius test is the same as doing it for x+1 over x^2a.
Why do I require that a<sqrt(n)? I cannot answer this. I know x^2a == 0 mod n but cannot make further progress. Last fiddled with by paulunderwood on 20210212 at 01:10 
20210214, 21:01  #9 
Sep 2002
Database er0rr
4,129 Posts 
x+a+1
Powers of x+a+1 (mod n, x^2a) is the same as powers of [a+1,a;1,a+1] mod n. The characteristic equation of this matrix is:
y^22*(a+1)*y+(a+1)^2a=0 whose solution is y=(a+1)+sqrt(a). Doing the old FrobeniusFermatEuler trick gives the following test: Code:
{ tst(n,a)= kronecker(a,n)==1&& Mod(a,n)^((n1)/2)==1&& Mod(a+1,n)^n==a+1&& Mod(Mod(x+a+1,n),x^2a)^n==x+a+1 } In fact the Frobenius test over y^2P*y+Q can be transformed into one over z^2(P^2/Q2)*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)^((n1)/2)==1&& Mod(a+1,n)^(n1)==1&& Mod(Q,n)^((n1)/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) } 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 20210215 at 05:20 Reason: Strengthened Lucas PRP test 
20210215, 05:42  #10 
Sep 2002
Database er0rr
1000000100001_{2} Posts 
x+1 revisited  brain storming
Without much ado, I am testing:
Code:
{ tst(n,a)=local(Q=1a); kronecker(a,n)==1&& kronecker(Q,n)==1&& gcd(a+3,n)==1&& gcd(3*a+1,n)==1&& Mod(a,n)^((n1)/2)==1&& Mod(Q,n)^((n1)/2)==1&& Mod(Mod(z,n),z^2(4/Q2)*z+1)^((n+1)/2)==1; } Last fiddled with by paulunderwood on 20210215 at 08:23 Reason: formulating 
20210215, 22:17  #11 
Sep 2002
Database er0rr
4,129 Posts 
1+2+2 selfridges
Consider respectively the matrices [1,a;1,1] and [1,1a;1,1] whose characteristic equations are:
y^22*y+1a=0 y^22*y+a=0 with solutions: y=1+sqrt(a) y=1+sqrt(1a) Restrict to kronecker(a,n)==1 and kronecker(1a,n)==1 Now transform the characteristic equations (ignoring Euler "Q"PRP tests) to z^2(4/(1a)2)*z+1=0 z^2(4/a2)*z+1=0 With a Fermat base 2 PRP test I propose: Code:
{ tst(n,a)=Mod(2,n)^(n1)==1&& kronecker(a,n)==1&& kronecker(1a,n)==1&& Mod(Mod(z,n),z^2(4/(1a)2)*z+1)^((n+1)/2)==1&& Mod(Mod(z,n),z^2(4/a2)*z+1)^((n+1)/2)==1; } Last fiddled with by paulunderwood on 20210215 at 22:23 
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  20200211 19:49 
Modifying the Lucas Lehmer Primality Test into a fast test of nothing  Trilo  Miscellaneous Math  25  20180311 23:20 
Double check LL test faster than first run test  lidocorc  Software  3  20081203 15:12 
Will the torture test, test ALL available memory?  swinster  Software  2  20071201 17:54 
A primality test for Fermat numbers faster than Pépin's test ?  T.Rex  Math  0  20041026 21:37 