View Single Post
Old 2021-02-19, 10:41   #16
paulunderwood
 
paulunderwood's Avatar
 
Sep 2002
Database er0rr

EE616 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