Saving tons of PRP-C and (hypotetical) LL-C tests, a new method

R. Gerbicz · 2018-06-22, 20:59

PRP-C refers to (weak) Fermat test for (2^p-1)/d.
And LL-C refers to a LL type test for (2^p-1)/d, see http://mersenneforum.org/showthread....732#post471732
ofcourse currently the main issue with LL/LL-C is that we have no strong error check for these LL (type) tests.

But first concentrating on PRP-C tests.

You can see such lines when you can check out the recent results page:
https://www.mersenne.org/report_expo...1344943&full=1
https://www.mersenne.org/report_expo...2389403&full=1
https://www.mersenne.org/report_expo...2462281&full=1
https://www.mersenne.org/report_expo...3009703&full=1
https://www.mersenne.org/report_expo...4373911&full=1

What happens here? We do a PRP-C test on (2^p-1)/d1, but when a new
prime divisor appears, then we redo this, because the full residue is not available.
Ofcourse there is a folklore solution: store the full residue. But that takes lots of storage and bandwidth.
I can do much better here, and this is the trick.

Let p>3 prime and mp=2^p-1.
Compute

Code:

[1]: 3^mp==res mod mp, independently from d.

[in practice we compute 3^(mp+1), because then mp+1 is a power of two; and the end we use an easy division by 3].
If mp/d is prime, then using Fermat's theorem we know that:
3^(mp/d)==3 mod (mp/d), so

Code:

[2]: 3^mp==3^d mod (mp/d) also holds (note that here we're already weaker than 
Fermat, but not much weaker).

From [1] and [2]:
3^mp==res==3^d mod (mp/d)
let s=3^d mod (mp/d), then

Code:

[3]: res=s+w*(mp/d), for some w integer, where 0<=w<d. Multiply by d, we get
d*(res-s)=w*mp, see this equation mod 2^t, where t<p, then

d*(res-s)==-w mod 2^t, so
w==d*(s-res) mod 2^t, but if 2^t>d, then we have a unique candidate for w:

Code:

[4]: w=(d*(s-res) mod 2^t)

but if this is w>=d, then mp/d is composite!!! (because we had 0<=w<d)
(not forget the only conditions: t<p and d<2^t)

It was a quite general idea, works for all numbers, just go back to [3],
suppose N is odd, and d is a non-trivial divisor of N.
[3]': res=s+w*(N/d), see this mod 2^t
w==(res-s)*inv mod 2^t, where (N/d)*inv==1 mod 2^t, here inv exists, because N/d is also odd.
and if d<2^t and d<=w then N/d is composite.
[ where w=((res-s)*inv) mod 2^t) ]. Not get confused, but in Mersenne number case it was inv=-d for p>t !

A little quick and dirty test, just get the small q prime divisors for mp where q<10000*p
, and test mp/d, where d is the product of all found prime divisors of mp.

Code:

prp(n)=return(Mod(3,n)^n==Mod(3,n))

prpc(maxp)={t=512;num_large_d=0;forprime(p=t,maxp,
d=1;mp=2^p-1;forstep(q=2*p+1,10000*p,2*p,if(isprime(q)&&lift(Mod(2,q)^p)==1,d*=q));
if(d>1&&d<mp,res=lift((Mod(3,mp)^mp));s=lift(Mod(3,mp)^d)%(mp/d);
w=(d*(s-res))%(2^t);
if(d>2^t,num_large_d+=1);
if(prp(mp/d),print(["Found prp ",p,d]));
if(w<d&&2^t>d,print(["Candidate! ",p,d]))));
print("Number of large divisors=",num_large_d);}
prpc(10000)

The LLT variant is similar to the above test,
only s has a slightly complicated formula.

Code:

prp(n)=return(Mod(3,n)^n==Mod(3,n))

fmult(u,v,p)=return([(u[1]*v[1]+3*u[2]*v[2])%(2^p-1),(u[1]*v[2]+u[2]*v[1])%(2^p-1)])

fpowmod(v,e,p)={
ret=[1,0];h=v;
while(e,
if(e%2,ret=fmult(ret,h,p));
h=fmult(h,h,p);e>>=1);
return(ret)}

LLT(n,x0,it)={mp=2^n-1;x=Mod(x0,mp);for(i=1,it,x=x^2-2);return(lift(x))}

llc(maxp)={t=512;forprime(p=t,maxp,
d=1;mp=2^p-1;forstep(q=2*p+1,10000*p,2*p,if(isprime(q)&&lift(Mod(2,q)^p)==1,d*=q));
if(d>1&&d<mp,
res=LLT(p,4,p);
s=(2*(fpowmod([2,1],d+kronecker(3,mp/d),p)[1]))%(mp/d);
w=(d*(s-res))%(2^t);
if(d>2^t,num_large_d+=1);
if(prp(mp/d),print(["Found prp ",p,d]));
if(w<d&&2^t>d,print(["Candidate! ",p,d]))));
print("Number of large divisors=",num_large_d);}
llc(10000)

the output in both case:

Code:

["Found prp ", 881, 26431]
["Candidate! ", 881, 26431]
["Found prp ", 1459, 1362463807]
["Candidate! ", 1459, 1362463807]
["Found prp ", 3041, 135391639199]
["Candidate! ", 3041, 135391639199]
["Found prp ", 3359, 6719]
["Candidate! ", 3359, 6719]
["Found prp ", 4127, 154517628583]
["Candidate! ", 4127, 154517628583]
["Found prp ", 4243, 101833]
["Candidate! ", 4243, 101833]
["Found prp ", 7673, 2563193011919]
["Candidate! ", 7673, 2563193011919]
Number of large divisors=0

so found all prp, and there was no false hit.

ps.
say if 2^t>d>2^(t-1) then you'll have a good chance that w<d, but this doesn't mean that you have found a prime,
because with more than 50% chance w<d will be true.
Note that for almost all known smallish p value (p<10^9 or so) it is true that d<2^512.
So you'd only need additional PRP-C tests for those d>2^512 and for those that survived this new test.
For this we'd need to store RES512, if we'd choose t=512.

And not forget that with this mod 2^t shrink we are (still) weaker than a standard Fermat test, but not much weaker as
you can see from the example runs.

kriesel · 2018-06-23, 16:30

Excellent. While this does not seem to impact the primality-unknown PRP or LL, as I incompletely understand it, it should really help the PRP-C and LL-C progress. Like your previous insights, it will take a while to understand, implement, roll out, and yield advantages. And that long process starts when you introduce such things, so keep them coming!

So now some questions,

A) step one is the PRP test if no factors are found yet. Always save res512 from that?

B) does the first cofactor run generate the res512 and send it to the (enhanced to accept it) PrimeNet server?

C) what's the language of your code sections for PRP-c and ll-c?

D) For confidence in accurate transmission of res512 values, do we use some agreed standard like CRC32 from the start?

E) Is addition of res512 storage practical on the server? A question for Madpoo et al

F) What's inv there? Inverse element in some group?

"Not get confused" (Too late...;)

R. Gerbicz · 2018-06-23, 19:22