20221014, 17:40  #1 
Sep 2002
Database er0rr
2^{3}×3×11×17 Posts 
Fun with quadratic discriminant
Sure, I harp on about x^2a*x+1=0 enough. It has discriminant D=a^24 which is (a2)*(a+2). As ever we are here only concerned with (D,n)==1.
The companion matrix of this characteristic equations is [a,1;1,0]. I now consider the tests Mod(Mod(x1,n),x^2a*x+1)^(n+1) and Mod(Mod(x+1,n),x^2a*x+1)^(n+1), for reasons which will become apparent. In terms of matrices these are [a+1,1;1,1]^(n+1) mod n and [a1,1;1,1]^(n+1) mod n. These matrices have characteristic equations y^2(a+2)*y+(a+2)==0 and y^2(a2)*y(a2)=0. Now you see the connection with the discriminant! The first equation can be transformed into Mod(Mod(z,n),z^2((a+2)^2/(a+2)2)*z+1)^((n+1)/2)==kronecker(a+2,n) and Mod(a+2,n)^((n1)/2)==kronecker(a+2,n). Simplifying the equation in z to z^2a*z+1 and multiplying the two bases of the tests together we get the test: tst1(n,a)=Mod(Mod((a+2)*z,z^2a*z+1)^((n+1)/2)==a+2. Doing the same process  some homework on your behalf  to the second test yields: tst2(n,a)=Mod(Mod(2a)*z,z^2+a*z+1)^((n+1)/2)==2a. Big assumption: I claim that any pseudoprime for both test combined also have a pseudoprime for tst1(n,1) and tst2(n,1), So the only thing left for the grand test is to check gcd(a^21,n)==1 and ensure a is not 0. More to follow on the verification process... Last fiddled with by paulunderwood on 20221014 at 19:12 
20221014, 20:44  #2 
Sep 2002
Database er0rr
2^{3}·3·11·17 Posts 
Here are the two major subtests:
Code:
{tst1(n,a)=Mod(Mod((a+2)*z,n),z^2a*z+1)^((n+1)/2)==a+2;} {tst2(n,a)=Mod(Mod((2a)*z,n),z^2+a*z+1)^((n+1)/2)==2a;} Code:
{tst(n,a)= n%2==1&& a!=0&& kronecker(a^24,n)==1&& gcd(a^21,n)==1&& tst1(n,a)&& tst2(n,a);} Code:
{alg(n)= if(n==2n==3,return(1)); if(n%2==0,return(0)); if(issquare(n),return(0)); a=3;while(kronecker(a^24,n)!=1gcd(a^21,n)!=1,a++); tst1(n,a)&&tst2(n,a);} Code:
{vtst(lb,ub)= if(lb%6!=5,lb++); forstep(lb,ub,6 if(!ispseudoprime(n)&&tst1(n,1), for(a=3,(n1)/2, if(kronecker(a^24,n)==1&&tst1(n,a)&&tst2(n,a), r=[n,a,gcd(a^21,n)]; print(r);write("vtst_results",r)))));} Last fiddled with by paulunderwood on 20221015 at 00:18 Reason: fixed tst. tst1 and tst2 
20221015, 00:19  #3  
Sep 2002
Database er0rr
2^{3}·3·11·17 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
New {function, criterion, theorem, conjecture} for discriminant of congruence  Zcyyu  Miscellaneous Math  40  20210828 02:51 
Trying to solve discriminant of a cubic polynomial by product method  carpetpool  Abstract Algebra & Algebraic Number Theory  6  20181128 13:16 
Quadratic PRP test  carpetpool  Miscellaneous Math  5  20180313 13:37 
the multiplicativ structur of the discriminant for quadratic polynomials  bhelmes  Computer Science & Computational Number Theory  3  20170527 01:33 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 