Register FAQ Search Today's Posts Mark Forums Read

 2022-10-14, 17:40 #1 paulunderwood     Sep 2002 Database er0rr 23×3×11×17 Posts Fun with quadratic discriminant Sure, I harp on about x^2-a*x+1=0 enough. It has discriminant D=a^2-4 which is (a-2)*(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(x-1,n),x^2-a*x+1)^(n+1) and Mod(Mod(x+1,n),x^2-a*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 [a-1,-1;1,-1]^(n+1) mod n. These matrices have characteristic equations y^2-(a+2)*y+(a+2)==0 and y^2--(a-2)*y-(a-2)=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)^((n-1)/2)==kronecker(a+2,n). Simplifying the equation in z to z^2-a*z+1 and multiplying the two bases of the tests together we get the test: tst1(n,a)=Mod(Mod((a+2)*z,z^2-a*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(2-a)*z,z^2+a*z+1)^((n+1)/2)==2-a. 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^2-1,n)==1 and ensure a is not 0. More to follow on the verification process... Last fiddled with by paulunderwood on 2022-10-14 at 19:12
 2022-10-14, 20:44 #2 paulunderwood     Sep 2002 Database er0rr 23·3·11·17 Posts Here are the two major sub-tests: Code: {tst1(n,a)=Mod(Mod((a+2)*z,n),z^2-a*z+1)^((n+1)/2)==a+2;} {tst2(n,a)=Mod(Mod((2-a)*z,n),z^2+a*z+1)^((n+1)/2)==2-a;} The grand test to be fooled is: Code: {tst(n,a)= n%2==1&& a!=0&& kronecker(a^2-4,n)==-1&& gcd(a^2-1,n)==1&& tst1(n,a)&& tst2(n,a);} The algorithm is: Code: {alg(n)= if(n==2||n==3,return(1)); if(n%2==0,return(0)); if(issquare(n),return(0)); a=3;while(kronecker(a^2-4,n)!=1||gcd(a^2-1,n)!=1,a++); tst1(n,a)&&tst2(n,a);} My verification code based on the "big assumption" above: Code: {vtst(lb,ub)= if(lb%6!=5,lb++); forstep(lb,ub,6 if(!ispseudoprime(n)&&tst1(n,1), for(a=3,(n-1)/2, if(kronecker(a^2-4,n)==-1&&tst1(n,a)&&tst2(n,a), r=[n,a,gcd(a^2-1,n)]; print(r);write("vtst_results",r)))));} (The tst2(n,1) is equivalent to n%6==5 for which the jacobi symbol of discriminant -3 is -1.) Last fiddled with by paulunderwood on 2022-10-15 at 00:18 Reason: fixed tst. tst1 and tst2
2022-10-15, 00:19   #3
paulunderwood

Sep 2002
Database er0rr

23·3·11·17 Posts

Quote:
 tst(1091*26161, 2093977) 1
Fooled

 Similar Threads Thread Thread Starter Forum Replies Last Post Zcyyu Miscellaneous Math 40 2021-08-28 02:51 carpetpool Abstract Algebra & Algebraic Number Theory 6 2018-11-28 13:16 carpetpool Miscellaneous Math 5 2018-03-13 13:37 bhelmes Computer Science & Computational Number Theory 3 2017-05-27 01:33 carpetpool Miscellaneous Math 14 2017-02-18 19:46

All times are UTC. The time now is 14:36.

Thu Feb 2 14:36:42 UTC 2023 up 168 days, 12:05, 1 user, load averages: 1.05, 1.06, 1.10