2022-01-31, 15:32 | #34 |
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;} 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 |
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;} 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 | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
Lucas and Fibonacci primes | Batalov | And now for something completely different | 9 | 2017-06-28 16:56 |
Lucas Table | R.D. Silverman | Factoring | 19 | 2012-09-07 17:24 |
Need help with Lucas Sequences... | WraithX | Programming | 11 | 2010-09-23 23:22 |
Lucas-Lehmer Test | storm5510 | Math | 22 | 2009-09-24 22:32 |
Lucas-Lehmer | Dougal | Information & Answers | 9 | 2009-02-06 10:25 |