Divertimento -- Four Lucas Tests

[paulunderwood]

Originally Posted by paulunderwood

But then the pattern is broken by:

[2139155051, 2139155051, 75650, 18913, 307017169]
[2139155051, 43691, 75650, 22942, 1739818799]
[2139155051, 2139155051, 75650, 56738, 1832137882]
[2139155051, 43691, 75650, 60767, 399336252]

Assuming z%4==2 and Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n) are necessary conditions, -- poof anyone? -- the next to break "the pattern" is

{
for(v=305962,#V,n=V[v];
if(Mod(-2,n)^((n-1)/2)==kronecker(-2,n),
z=znorder(Mod(2,n));
if(z%4==2,
r=(z+2)/4;t=lift(Mod(2,n)^r);
if(Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n),
for(r=1,z,
t=lift(Mod(2,n)^r);
if(Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n),
g=gcd(t^2+2,n);print([v,n,g,z,r,t])))))))
}                                                               
[305962, 14280816152219, 14280816152219, 90099218, 22524805, 2626041506362]   
[305962, 14280816152219, 11342983441, 90099218, 31047704, 6085369776326]
[305962, 14280816152219, 14280816152219, 90099218, 67574414, 11654774645857]
[305962, 14280816152219, 11342983441, 90099218, 76097313, 8195446375893]

[paulunderwood]

Here is the algorithm for x^2-2^r*x-2

{
tst(n)=local(t=2); \\ t=2^r
if(n==2||n==3,return(1)); \\ trivialiies
if(n%2==0||issquare(n)||Mod(-2,n)^((n-1)/2)!=kronecker(-2,n),return(0)); \\ even and newton and euler
while(kronecker(t^2+8,n)!=-1,t=t*2%n;if(t==1,return(0))); \\ seek strong kronecker. If none found assume composite
gcd(t^2+2,n)==1&&Mod(Mod(x,n),x^2+(t^2/2+2)*x+1)^((n+1)/2)==kronecker(-2,n); \\ euclid and lucas
}

[paulunderwood]

For my blanket testing of all r, I notice those n that require a gcd are 5 mod 6. This will speed up a little of my search where "the pattern" holds.

Status: all 2-PSPs < 3*10^10 and using "the pattern" < 5*10^13. It's time to move over to GMP, where I can employ a Lucas chain, plus some other optimizations.

I also note that z=znorder(Mod(2,n)) is mostly small.

"The pattern" is where the test with r=(z+2)/4 passes and requires gcd(t^2+2,n).

[paulunderwood]

Originally Posted by paulunderwood

"The pattern" is where the test with r=(z+2)/4 passes and requires gcd(t^2+2,n).

If r=(z+2)/4 then the quadratic x^2+(t^2/2+2)*x+1 is x^2+(2^((z+2)/2)/2+2)*x+1 is x^2+(2^(z/2)*2/2+2)*x+1. Since 2^(z/2)==-1 then the quadratic reduces to x^2+x+1 which is cyclotomic. A similar observation for r=3*(z+2)/4-1 can be had.

I have now surpassed 9*10^11 for both quadratics x^2+(t^2/2+2)*x+1 and x^2+(t^2/4+2)*x+1 each with their incumbent Euler/Fermat PRP tests.

This about winds up this thread.

[paulunderwood]

Here my paper distilled from this thread

[paulunderwood]

It occurred to me that since the tests involve t^2+something that only half of t might be used. For example:

{
tst(n)=local(t=2,k=kronecker(-2,n),limit=2*log(n)*log(log(n)),l=0,nm1d2=(n-1)/2);
if(n==2||n==3,return(1));
if(n%2==0||issquare(n)||Mod(-2,n)^nm1d2!=k,return(0));
while(t>nm1d2||kronecker(t^2+8,n)!=-1,t=t*2%n;l++;if(t==1||l>limit,return(0)));
gcd(t^2+2,n)==1&&Mod(Mod(z,n),z^2+(t^2/2+2)*z+1)^((n+1)/2)==k;
}

Note the introduction of "t>nm1d2". I'll update the paper later along with testing below 2*log(n)*log(log(log(n)))

[paulunderwood]

Here us the revised paper. I'll leave the original up for contrast,

[paulunderwood]

I have coded up test #3 from the above paper.

// gcc -o prp prp.c -lgmp
// usages:-
// ./prp
// ./prp <integer>
// echo "print(<expression>)" | gp -q | ./prp

Edit: Added comments, an else, GCDs and more meaningful variable names.

BTW all 3 tests have been verified for all case below 2.5<10^13.

[paulunderwood]

Rather than taking gcd(4^r-4,n)==1 and gcd(4^r-2,n)==1 the substitute gcd((r-1)*(2*r-1),n-1)<=2 is quicker, resulting in the test:

{
tst(n,r)=local(k=kronecker(2,n);fr=lift(Mod(4,n)^r));
gcd((r-1)*(2*r-1),n-1)<=2&&
kronecker(fr-8,n)==-1&&
Mod(2,n)^((n-1)/2)==k&&
Mod(Mod(x,n),x^2-(fr/2-2)*x+1)^((n+1)/2)==k;
}

Although I titled this post "speed up", the real effect is to reduce the domain.

[paulunderwood]

We can fuse the Euler and Lucas test thusly:

{
tst(n,r)=local(fr=lift(Mod(4,n)^r));
gcd((r-1)*(2*r-1),n-1)<=2&&
kronecker(fr-8,n)==-1&&
Mod(Mod(2*x,n),x^2-(fr/2-2)*x+1)^((n+1)/2)==2;
}

To see it is 2 selfridges note that for binary exponentiation intermediate values:

(s*x+t)^2 = s*(s*a+t*2)*x + (t-s)*(t+s)
(s*x+t)*(2*x) = (s*a+t)*2*x - s*2

where a=4^r/2-2.

So the algorithm would be:

{
tst(n)=local(r=2,s=2,t=0,BIN=binary(n+1),LEN=length(BIN)-1,a,b,temp);
if(n==2,return(1));if(n%2==0,return(0));
if(issquare(n),return(0));
while(gcd((r-1)*(2*r-1),n-1)>2||kronecker(4^r-8,n)!=-1,r++);
a=2^(2*r-1)-2;
for(b=2,LEN,temp=s*(s*a+t*2)%n;t=(t-s)*(t+s)%n;s=temp;
 if(BIN[b],temp=(s*a+t)*2%n;t=-s*2%n;s=temp));
if(s==0&&t==2,return(1));0;
}

[paulunderwood]

The attached program returns exit(0) iff the input is 2-Euler PRP and Lucas PRP. (It also uses gcd((r-1)*(2*r-1),n-1)<=2.)

// gcc -o prp_v2 prp_v2.c -lgmp
// bash use case:-
/*
for i in {1..2281}; do 
    if ./prp_v2 $i; then 
        if echo "print(2^$i-1)" | gp -q | ./prp_v2; then
            echo "M$i Is 2-Euler and Lucas PRP";
        fi
    fi
done
*/

Edit: latest code has a little trial division to speed up testing.

Edit2: fixed the trial division (albeit not very good) where "r" in the loop got clobbered and so was meaningless on finishing the loop. Now "r" remains intact and I use "d" instead in the loop