 mersenneforum.org kronecker(2,n)==-1 test
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read  2021-01-28, 08:33 #1 paulunderwood   Sep 2002 Database er0rr 3,617 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^2-2)^n==-x+2, print([n]))) } I can't generalize it without breaking it.    2021-01-29, 18:19 #2 paulunderwood   Sep 2002 Database er0rr 3,617 Posts Since for the above test I am working mod x^2-2 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^2-2)^n==-x+1, print([n]))) } All quiet! Last fiddled with by paulunderwood on 2021-01-29 at 18:20   2021-01-30, 11:14 #3 paulunderwood   Sep 2002 Database er0rr 1110001000012 Posts generalization The general test is: Code: { tst(a,n)= kronecker(a,n)==-1&&Mod(a,n)^((n-1)/2)==-1&& Mod(Mod(x+1,n),x^2-a)^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 2021-01-30 at 13:14   2021-02-01, 00:17 #4 paulunderwood   Sep 2002 Database er0rr 3,617 Posts I have tested for a x^(n-1) = -1 (mod n, x^2-a) => a^((n-1)/2) = -1 mod n Last fiddled with by paulunderwood on 2021-02-03 at 04:50   2021-02-05, 03:40 #5 paulunderwood   Sep 2002 Database er0rr 1110001000012 Posts For n==5 mod 8 it seems that testing Mod(Mod(x+1,n),x^2+2)^n==-x+1 is sufficient.   2021-02-09, 02:05   #6
paulunderwood

Sep 2002
Database er0rr

70418 Posts Quote:
 Originally Posted by paulunderwood a
I have tested:
• Carmichael numbers up to 10^14 with Pari/GP
• semiprimes with David Broadhurst's CRT Pari/GP script -- 1 hour run
• now with C+PrimeSieve all applicable "a" for all n < 2.6*10^8 and counting.

Last fiddled with by paulunderwood on 2021-02-15 at 20:50   2021-02-10, 00:04 #7 paulunderwood   Sep 2002 Database er0rr 3,617 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 fermat-PRP test. In section 2.5 "Implemenation of the test"  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 1-a: An implicit 1-a PRP test is done. A bonus!  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 left-right 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 2021-02-10 at 01:21   2021-02-10, 23:29 #8 paulunderwood   Sep 2002 Database er0rr E2116 Posts Taking powers of x+1 (mod n, x^2-a) is the same as taking powers of M:=[1,a;1,1] mod n. The characteristic equation of M is y^2-2*y+1-a=0 whose solutions are y=1 +- sqrt(a). So we can take a Frobenius test of y over (y-1)^2-a, trivially a Fermat -1-PRP test and an Euler-PRP test for base a. Since we know y=1+-x, this Frobenius test is the same as doing it for x+1 over x^2-a. Why do I require that a 2021-02-14, 21:01 #9 paulunderwood   Sep 2002 Database er0rr E2116 Posts x+a+1 Powers of x+a+1 (mod n, x^2-a) is the same as powers of [a+1,a;1,a+1] mod n. The characteristic equation of this matrix is: y^2-2*(a+1)*y+(a+1)^2-a=0 whose solution is y=(a+1)+-sqrt(a). Doing the old Frobenius-Fermat-Euler trick gives the following test: Code: { tst(n,a)= kronecker(a,n)==-1&& Mod(a,n)^((n-1)/2)==-1&& Mod(a+1,n)^n==a+1&& Mod(Mod(x+a+1,n),x^2-a)^n==-x+a+1 } Note there is an implicit Fermat a^2+a+1 PRP test from the determinant. In fact the Frobenius test over y^2-P*y+Q can be transformed into one over z^2-(P^2/Q-2)*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)^((n-1)/2)==-1&& Mod(a+1,n)^(n-1)==1&& Mod(Q,n)^((n-1)/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) } So two Euler, one Fermat and one Lucas PRP tests. (1+1+1+2 selfridges.) 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 2021-02-15 at 05:20 Reason: Strengthened Lucas PRP test   2021-02-15, 05:42 #10 paulunderwood   Sep 2002 Database er0rr 3,617 Posts x+1 revisited -- brain storming Without much ado, I am testing: Code: { tst(n,a)=local(Q=1-a); kronecker(a,n)==-1&& kronecker(Q,n)==-1&& gcd(a+3,n)==1&& gcd(3*a+1,n)==1&& Mod(a,n)^((n-1)/2)==-1&& Mod(Q,n)^((n-1)/2)==-1&& Mod(Mod(z,n),z^2-(4/Q-2)*z+1)^((n+1)/2)==-1; } I claim 3 rounds are enough with a0, a1 and a2, checking gcd(ai^2 - aj^2,n)>1 for some combination. Last fiddled with by paulunderwood on 2021-02-15 at 08:23 Reason: formulating   2021-02-15, 22:17 #11 paulunderwood   Sep 2002 Database er0rr 3,617 Posts 1+2+2 selfridges Consider respectively the matrices [1,a;1,1] and [1,1-a;1,1] whose characteristic equations are: y^2-2*y+1-a=0 y^2-2*y+a=0 with solutions: y=1+-sqrt(a) y=1+-sqrt(1-a) Restrict to kronecker(a,n)==-1 and kronecker(1-a,n)==-1 Now transform the characteristic equations (ignoring Euler "Q"-PRP tests) to z^2-(4/(1-a)-2)*z+1=0 z^2-(4/a-2)*z+1=0 With a Fermat base 2 PRP test I propose: Code: { tst(n,a)=Mod(2,n)^(n-1)==1&& kronecker(a,n)==-1&& kronecker(1-a,n)==-1&& Mod(Mod(z,n),z^2-(4/(1-a)-2)*z+1)^((n+1)/2)==-1&& Mod(Mod(z,n),z^2-(4/a-2)*z+1)^((n+1)/2)==-1; } Last fiddled with by paulunderwood on 2021-02-15 at 22:23   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post sweety439 sweety439 7 2020-02-11 19:49 Trilo Miscellaneous Math 25 2018-03-11 23:20 lidocorc Software 3 2008-12-03 15:12 swinster Software 2 2007-12-01 17:54 T.Rex Math 0 2004-10-26 21:37

All times are UTC. The time now is 16:26.

Mon Apr 12 16:26:02 UTC 2021 up 4 days, 11:06, 1 user, load averages: 1.90, 1.97, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.