20200722, 02:08  #67 
Sep 2002
Database er0rr
2×3×19×31 Posts 
two parameter test
Let f=x^22^r*x+b=0 with solutions 2*x = 2^r + sqrt(4^r4*b). Test Frobenius(2x) w.r.t. f and EulerPRP(4^r4*b) = 1 (all mod n), with the provisos kronecker(4^r 4*b,n)==1 and gcd(4^r2*b,n)==1 and gcd(4^rb,n)==1 and not bn.
The Forbenius test can be broken into a 2PRP test and a Frobenius test on x. Here is the test. For any nonsquare n find r and b:
Edit: I changed gcd(4^rb^2,n) to gcd(4^rb,n). Edit2: I think gcd(4^rb)==1 can be replaced by: (gcd(b1,n)==1&&gcd(4^r1,n)==1)(gcd(b+1,n)==1&&gcd(4^r+1,n)==1) Last fiddled with by paulunderwood on 20200723 at 22:44 
20200727, 10:15  #68 
Sep 2002
Database er0rr
2·3·19·31 Posts 
most general test
Let x^2a*x+b=0. The solutions are x=a/2 + sqrt(a^24*b)/2.
The test is:

20200727, 11:51  #69 
Sep 2002
Database er0rr
2·3·19·31 Posts 
To fool 2PSPs and Carmichael numbers lists gcd(a^23*b,n)==1 is also required.

20200727, 14:23  #70 
Sep 2002
Database er0rr
DCE_{16} Posts 
most general test (revised)
I found some counterexamples to the above.
The revised test:
Further testing is ongoing. A little bit of theory... Let f = x^2a*x+b=0 (which has roots x = a/2 + sqrt(a^24*b)/2). a = x+b/x mod f if kronecker(a^24*b,n)==1. a^22*b = x^2+b^2/x^2 mod f (a^22*b)^22*b^2 = x^4+b^4/x^4 mod f If gcd((a^22*b)^22*b^2,n)!=1 then d  R.H.S. and we can use Gaussian Elimination on the coefficient 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 20200727 at 14:54 
20200728, 02:05  #71 
Sep 2002
Database er0rr
2·3·19·31 Posts 
A very short paper
Last fiddled with by paulunderwood on 20200728 at 03:05 
20200728, 18:53  #72 
Sep 2002
Database er0rr
2×3×19×31 Posts 
Simplification
Recap: The solutions to x^22^r*x+b=0 are x=2^(r1)+sqrt(4^(r1)b).
Let r=1. Then the solutions are to the equation x^22*x+b=0 which are x=1+sqrt(1b) We have to have kronecker(1b,n)==1, gcd(4b,n)==1 and gcd(42*b,n)==1. So no Fermat PRP test is needed; Just Frobenius+Euler. I want to combine these into one test: (x*(b1))^((n+1)/2) == sqrt(b)*(b1)*kronecker(X,n) (mod n, x^22*x+b) where b is quadratic residue. But what is X? Last fiddled with by paulunderwood on 20200728 at 19:09 
20200730, 01:10  #73 
Sep 2002
Database er0rr
2·3·19·31 Posts 
Answer and warning
Apart form the illformed question, writing b=s^2 (and found by trial and error) the answer is:
(x*(1s^2))^((n+1)/2) == s*(1s^2)*kronecker(2*(1s),n) (mod n, x^22*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: (1b)^((n1)/2 == 1 (mod n) x^(n+1) == b (mod n, x^22*x+b) where kronecker(1b,n)==1 and gcd(42*b,n)==1 and gcd(4b,n)==1. Last fiddled with by paulunderwood on 20200730 at 01:27 
20200802, 09:15  #74 
Sep 2002
Database er0rr
2×3×19×31 Posts 
Second draft

20200803, 14:20  #75 
Sep 2002
Database er0rr
2×3×19×31 Posts 
1+1 selfridges
Here is a 1+1 selfridges algorithm:
Given a nonsquare n find b:
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 20200803 at 15:49 
20200803, 19:36  #76 
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 20200803 at 19:38 
20200826, 00:07  #77 
Sep 2002
Database er0rr
2×3×19×31 Posts 
The solutions to x^22*x2^r=0 are 1 + sqrt(1+2^r). This forms the basis of a test for nonsquare odd n:
I have tested the case r=0 against Feitsma's PSP2 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 subtest gcd(2^r+2,n)==1. Edit 2: 2289717532901 passes Mod(3,n)^((n1)/2)==1&&Mod(Mod(1,n)*x,x^22*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 20200827 at 04:34 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Don't miss this amazing trick that the moon is going to do!  Uncwilly  Astronomy  6  20180201 05:40 
Amazing result in P1  Miszka  Information & Answers  2  20140704 17:11 
Amazing academic resource  Xyzzy  Lounge  6  20120325 22:57 
Amazing!!!  R.D. Silverman  Factoring  5  20060126 09:14 
Two Amazing Things  clowns789  Hardware  1  20031227 16:57 