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 109C16 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 22·1,063 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

 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 18:50.

Sat Aug 13 18:50:46 UTC 2022 up 37 days, 13:38, 2 users, load averages: 0.98, 1.12, 1.09