Thread: kronecker(2,n)==-1 test View Single Post
 2021-02-19, 10:41 #16 paulunderwood     Sep 2002 Database er0rr EE616 Posts Rationale The rationale for the above test: Matrix: [a,a;1,a] Characteristic eqn: y^2-2*a+a^2-a==0 Solutions: y = a +- sqrt(a) "Strong" transform: z^2-2*(a+1)/(a-1)*z+1=0 and Euler-(a^2-a)==-1 Solutions: z = (a+1)/(a-1) +- sqrt((a+1)^2/(a-1)^2 - 1) = (a+1)/(a-1) +- 2*sqrt(a)/(a-1) Note1: if kronecker(a,n)==-1 and kronecker(a^2-a,n)==-1 then kronecker(a-1,n)==1 Note2: If a=-3 then z^2-z+1 = 0 => cyclotomic Query1: Why is gcd(a^2+6*a+1,n)==1 needed? 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