mersenneforum.org Amazing 6
 Register FAQ Search Today's Posts Mark Forums Read

 2020-07-22, 02:08 #67 paulunderwood     Sep 2002 Database er0rr 5·23·29 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 5×23×29 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 333510 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 5·23·29 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

5·23·29 Posts
A very short paper

Attached Files
 Two_Parameter_Probable_Prime_Test.pdf (40.5 KB, 37 views)

Last fiddled with by paulunderwood on 2020-07-28 at 03:05

 2020-07-28, 18:53 #72 paulunderwood     Sep 2002 Database er0rr 5×23×29 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 64078 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

333510 Posts
Second draft

Attached Files
 Two_Parameter_Probable_Prime_Test.pdf (39.7 KB, 15 views)

 2020-08-03, 14:20 #75 paulunderwood     Sep 2002 Database er0rr 1101000001112 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 5·23·29 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

 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:58.

Mon Aug 10 05:58:40 UTC 2020 up 24 days, 1:45, 2 users, load averages: 1.64, 1.54, 1.43