 mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read  2020-07-22, 02:08 #67 paulunderwood   Sep 2002 Database er0rr 2×3×19×31 Posts two parameter test Let f=x^2-2^r*x+b=0 with solutions 2*x = 2^r +- sqrt(4^r-4*b). Test Frobenius(2x) w.r.t. f and Euler-PRP(4^r-4*b) = -1 (all mod n), with the provisos kronecker(4^r -4*b,n)==-1 and gcd(4^r-2*b,n)==1 and gcd(4^r-b,n)==1 and not b|n. The Forbenius test can be broken into a 2-PRP test and a Frobenius test on x. Here is the test. For any non-square n find r and b:b%n!=0 gcd(4^r-b,n)==1 gcd(4^r-2*b,n)==1 kronecker(4^r-4*b,n)==-1 and test:Mod(2,.n)^(n-1)==1 Mod(4^r-4*b,n)^((n-1)/2)==-1 Mod(Mod(1,n)*x,x^2-2^r*x+b)^(n+1)==b Edit: I changed gcd(4^r-b^2,n) to gcd(4^r-b,n). Edit2: I think gcd(4^r-b)==1 can be replaced by: (gcd(b-1,n)==1&&gcd(4^r-1,n)==1)||(gcd(b+1,n)==1&&gcd(4^r+1,n)==1) Last fiddled with by paulunderwood on 2020-07-23 at 22:44   2020-07-27, 10:15 #68 paulunderwood   Sep 2002 Database er0rr 2·3·19·31 Posts most general test Let x^2-a*x+b=0. The solutions are x=a/2 +- sqrt(a^2-4*b)/2. The test is: b%n!=0 !issquare(n) gcd(a^2-b,n)==1 gcd(a^2-2*b,n)==1 kronecker(a^2-4*b,n)==-1 Mod(a^2/4-b,n)^((n-1)/2)==-1 Mod(a/2,n)^(n-1)==1 Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b   2020-07-27, 11:51 #69 paulunderwood   Sep 2002 Database er0rr 2·3·19·31 Posts To fool 2-PSPs and Carmichael numbers lists gcd(a^2-3*b,n)==1 is also required.    2020-07-27, 14:23 #70 paulunderwood   Sep 2002 Database er0rr DCE16 Posts most general test (revised) I found some counterexamples to the above. The revised test: b%n!=0 !issquare(n) gcd(a^2-b,n)==1 gcd(a^2-2*b,n)==1 gcd(a^2-3*a,n)==1 kronecker(a^2-4*b,n)==-1 Mod(a^2/4-b,n)^((n-1)/2)==-1 //Euler PRP Mod(a/2,n)^((n-1)/2)==konecker(lift(Mod(a/2,n)),n) //Euler PRP Mod(Mod(1,n)*x,x^2-a*x+b)^(n+1)==b //Frobenius PRP Further testing is ongoing. A little bit of theory... Let f = x^2-a*x+b=0 (which has roots x = a/2 +- sqrt(a^2-4*b)/2). a = x+b/x mod f if kronecker(a^2-4*b,n)==-1. a^2-2*b = x^2+b^2/x^2 mod f (a^2-2*b)^2-2*b^2 = x^4+b^4/x^4 mod f If gcd((a^2-2*b)^2-2*b^2,n)!=1 then d | R.H.S. and we can use Gaussian Elimination on the co-efficient of x and the term without x. This is complicated, but early calculations show that the GCDs given in the test above are sufficient and that there is no need to consider further recursions, Here is a counterexample: [n,a,b]=[1894955311, 1756017110, 1]. Back to the drawing board; znlog(a,Mod(2,n)) == [] Last fiddled with by paulunderwood on 2020-07-27 at 14:54   2020-07-28, 02:05   #71
paulunderwood

Sep 2002
Database er0rr

2·3·19·31 Posts A very short paper Attached Files Two_Parameter_Probable_Prime_Test.pdf (40.5 KB, 89 views)

Last fiddled with by paulunderwood on 2020-07-28 at 03:05   2020-07-28, 18:53 #72 paulunderwood   Sep 2002 Database er0rr 2×3×19×31 Posts Simplification Recap: The solutions to x^2-2^r*x+b=0 are x=2^(r-1)+-sqrt(4^(r-1)-b). Let r=1. Then the solutions are to the equation x^2-2*x+b=0 which are x=1+-sqrt(1-b) We have to have kronecker(1-b,n)==-1, gcd(4-b,n)==1 and gcd(4-2*b,n)==1. So no Fermat PRP test is needed; Just Frobenius+Euler. I want to combine these into one test: (x*(b-1))^((n+1)/2) == sqrt(b)*(b-1)*kronecker(X,n) (mod n, x^2-2*x+b) where b is quadratic residue. But what is X? Last fiddled with by paulunderwood on 2020-07-28 at 19:09   2020-07-30, 01:10 #73 paulunderwood   Sep 2002 Database er0rr 2·3·19·31 Posts Answer and warning Apart form the ill-formed question, writing b=s^2 (and found by trial and error) the answer is: (x*(1-s^2))^((n+1)/2) == s*(1-s^2)*kronecker(2*(1-s),n) (mod n, x^2-2*x+s^2), Warning: this "fused" Euler and Frobenius test produces pseudoprimes. Testing to date has not found a counterexample when they are applied separately: (1-b)^((n-1)/2 == -1 (mod n) x^(n+1) == b (mod n, x^2-2*x+b) where kronecker(1-b,n)==-1 and gcd(4-2*b,n)==1 and gcd(4-b,n)==1. Last fiddled with by paulunderwood on 2020-07-30 at 01:27   2020-08-02, 09:15   #74
paulunderwood

Sep 2002
Database er0rr

2×3×19×31 Posts Second draft  Attached Files Two_Parameter_Probable_Prime_Test.pdf (39.7 KB, 81 views)   2020-08-03, 14:20 #75 paulunderwood   Sep 2002 Database er0rr 2×3×19×31 Posts 1+1 selfridges Here is a 1+1 selfridges algorithm: Given a non-square n find b: kronecker(b,n)==1 kronecker(1-b,n)==-1 gcd(4-b,n)==1 gcd(4-2*b,n)==1 and test Mod(b,n)^((n-1)/2)==1 Mod(1-b,n)^((n-1)/2)==-1 I will try to explain my reasoning later. Later reason: programming error The argument does not stack up. It was entirely based on the Euler test of post #74 and without the Frobenius part. Last fiddled with by paulunderwood on 2020-08-03 at 15:49   2020-08-03, 19:36 #76 paulunderwood   Sep 2002 Database er0rr 2·3·19·31 Posts House of cards [n,b] = [79786523, 2982537] is a counterexample to the test given in post #74 where r=1. This was overlooked because of the same programming error indicated in post #75. The only thing to be lifted from the ashes is that b is not minimal. The cases where |b| =1 (post #71) have no counterexamples for n<5*10^12. Last fiddled with by paulunderwood on 2020-08-03 at 19:38   2020-08-26, 00:07 #77 paulunderwood   Sep 2002 Database er0rr 2×3×19×31 Posts The solutions to x^2-2*x-2^r=0 are 1 +- sqrt(1+2^r). This forms the basis of a test for non-square odd n: kronecker(1+2^r,n)==-1 Mod(1+2^r,n)^((n-1)/2)==-1 Mod(Mod(1,n)*x,x^2-2*x-2^r)^(n+1)==-2^r I have tested the case r=0 against Feitsma's PSP-2 database (2^64) i.e. those for which kronecker(2,n)==-1. Not having many free cycles at the moment, I have tested all r for n<10^5. Edit: On further testing I found this anomoly: [476971, Mod(476969, 476971)]. Henceforth I add the sub-test gcd(2^r+2,n)==1. Edit 2: 2289717532901 passes Mod(-3,n)^((n-1)/2)==-1&&Mod(Mod(1,n)*x,x^2-2*x+4)^(n+1)==4. Thus gcd(2^r+4,n)==1 is required. My quest is now to find counterexamples for which 2^r != -2 nor -4 mod n. Edit 3: [n,a]=[37870128451, 26812337209];gcd(a+2,n) 1403273. Last fiddled with by paulunderwood on 2020-08-27 at 04:34   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Uncwilly Astronomy 6 2018-02-01 05:40 Miszka Information & Answers 2 2014-07-04 17:11 Xyzzy Lounge 6 2012-03-25 22:57 R.D. Silverman Factoring 5 2006-01-26 09:14 clowns789 Hardware 1 2003-12-27 16:57

All times are UTC. The time now is 05:19.

Wed Jan 27 05:19:39 UTC 2021 up 55 days, 1:30, 0 users, load averages: 3.55, 3.12, 3.05