 mersenneforum.org Divertimento -- Four Lucas Tests
 Register FAQ Search Today's Posts Mark Forums Read  2022-01-31, 15:32 #34 paulunderwood   Sep 2002 Database er0rr 5·29·31 Posts Generalization Based on a Lucas PRP test over x^2-b^r*x+b, I have come up with a general test: Code: {tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1))); kronecker(b,n)==-1&& kronecker(t-4,n)==1&& gcd(t-3,n)==1&& gcd(t-2,n)==1&& gcd(t-1,n)==1&& gcd(r-1,n-1)==1&& Mod(b,n)^((n-1)/2)==-1&& Mod(Mod(z,n),z^2-(t-2)*z+1)^((n+1)/2)==-1;} Testing is slow with 3 nested loops. Can you find a counterexample? Edit: I just noticed this test does not work for primes 3, 5, 7, 17, 23 and 31. Bigger primes have plenty of scope given by the parameters. I made a programming error in Pari/GP, taking a gcd of a fraction when coding the above in a different way. So the above script easily gives counterexamples. Oh well! Last fiddled with by paulunderwood on 2022-02-01 at 02:40   2022-02-05, 06:26 #35 paulunderwood   Sep 2002 Database er0rr 5·29·31 Posts Generalization II I have now devised a general test of the polynomial x^2-b^r*x+b with an Euler PRP test for the discriminant b^(2*r)-4*b: Code: {tst(n,b,r)=local(t=lift(Mod(b,n)^(2*r-1)),k=kronecker(b,n)); gcd(b,n)==1&& gcd(t-1,n)==1&& gcd(t-2,n)==1&& gcd(t-3,n)==1&& kronecker(t-4,n)==-k&& Mod(b,n)^((n-1)/2)==k&& Mod(t-4,n)^((n-1)/2)==-k&& Mod(Mod(z,n),z^2-(t-2)*z+1)^((n+1)/2)==k;} (I think that is coded up properly). Can you fool this 1+1+2 Selfridge "restricted domain" PRP test? Edit: I found some frauds for n=287051. Because 2 appears as the denominator for the solution to x I have added a Fermat base 2 PRP test and am trying to find a pseudoprime to this new test. Edit 2: A counterexample is tst(79786523,206932265,1) Last fiddled with by paulunderwood on 2022-03-10 at 00:20   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Batalov And now for something completely different 9 2017-06-28 16:56 R.D. Silverman Factoring 19 2012-09-07 17:24 WraithX Programming 11 2010-09-23 23:22 storm5510 Math 22 2009-09-24 22:32 Dougal Information & Answers 9 2009-02-06 10:25

All times are UTC. The time now is 00:25.

Sun Feb 5 00:25:04 UTC 2023 up 170 days, 21:53, 1 user, load averages: 1.11, 1.16, 0.99