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

[R. Gerbicz]

Originally Posted by preda

How much work do you estimate would be saved?

Currently the wavefront of PRP-C is at p~5M (but not many people is doing this), and with this we could get
some results in the high 80M range.
We have free lunch, when an LL/PRP test done, and we discover after that test prime divisor(s) of Mp,
it wouldn't be that rare just see only the massiv effort of user TJAOI.
In the "hard" case, when there are known factors of Mp (maybe only one), and no PRP/LL test, then
we would do only one test independently from the number of future factors of Mp.
[ Unfortunately the current db is just too weak to use, it has stored LL residues at iteration of (p-2) and few bits. ]

Originally Posted by preda

If Mp/d is prime, is an additional PRP test still needed to "prove" it?

Just to correct your question:
If this method shows that mp/d could be prime (so w<d&&2^t>d), is an additional PRP test still needed to "prove" it?
Yes, you'd need it, because we have stored only the shrinked residue, for larger d values, say 2^511<d<2^512
in most of the cases mp/d would be composite! And ofcourse you still need it for d>2^512, because for that we have no information.

[GP2]

Originally Posted by R. Gerbicz

Currently the wavefront of PRP-C is at p~5M

The first-time checking wavefront is at 7.99M and the double-checking wavefront is at 5.49M

Originally Posted by R. Gerbicz

Currently the wavefront of PRP-C is at p~5M (but not many people is doing this), and with this we could get
some results in the high 80M range. ...

My manual testing assignments are in the 85M range. With gpuOwl 3.0, OpenCL Variant, FFT-length of 8152K, at 6.7ms/it on RX 580, they complete in 6 days approximately.

Originally Posted by SELROC

My manual testing assignments are in the 85M range. With gpuOwl 3.0, OpenCL Variant, FFT-length of 8152K, at 6.7ms/it on RX 580, they complete in 6 days approximately.

I think I made a typo: The FFT-length is 8192K.

[ktpn2011]

I was just thinking, 'why are we starting every LL test from 1st iteration? we sure can reuse some first squarings, they are same, until are below the number'

[preda]

Originally Posted by ktpn2011

I was just thinking, 'why are we starting every LL test from 1st iteration? we sure can reuse some first squarings, they are same, until are below the number'

(I asked myself the same question some time ago. Here's my answer)

Let's see what would be the saving. Let's say we want to start with a precomputed 128bit initial residue. How many iterations do we save?

At each iteration, we basically double the number of bits. So to fit the starting value in 128bits, we save 7 iterations.

Now, if in total we want to do let's say 80M iterations, we save 7 out of 80Million.
Or, if let's say every iteration takes 5ms, we save 35ms in total.

So, the benefit is so small that it's not worth to worry about it.

[ktpn2011]

quickly agree :
for integer-code it takes many time..

[kriesel]

Let's look at that. There are a relatively few code authors and several thousand participants active in any given year, running many more cpu cores and also in some cases gpus, running a relative handful of programs.

s0=4
s1=14
s2=194
s3=37634
s4=1,416,317,954

A rough estimate for the effect of easily saving 3 iterations is as follows:

First time testing advances about 8 million in exponent value annually in GIMPS, or about 400,000 prime exponents, with perhaps 100,000 surviving factoring attempts. The next year's assignments are of order 84,000,000 exponent value.
84,000,000 / 100,000 / 3 = 280 years per exponent saved (which would lengthen as exponents increase)

Double checking advances about 3 million in exponent value annually in GIMPS, or about 150,000 prime exponents, with perhaps 40,000 that survived factoring attempts. The next year's assignments are of order 50,000,000 exponent value.
50,000,000 / 40,000 / 3 = 417 years per exponent saved (which would lengthen as exponents increase)

Ignoring triple and higher checking, and combining, 1/ ( 1/280 + 1/417) = 167 years.

It is a very easy quick simple change, with a very very small distant payoff.
It's a nano-optimization: 3/84000000 =~ 36 ppb; 3/50000000 = 60 ppb.
It's understandable if code authors choose not to bother with it.
Others, and I, chose not to bother, even when exponents of main interest were much smaller, decades ago.

A similar argument can be made for adjusting the number of words of precision used per iteration, or once near the beginning, as operand size changes in the initial iterations. With fft lengths, that might even be a de-optimization.

[kriesel]

Originally Posted by GP2

The first-time checking wavefront is at 7.99M and the double-checking wavefront is at 5.49M

https://www.mersenne.org/primenet/ work distribution map shows today,
double checking assignments (>100 per 1E6 span) at 44.E6 to 54.E6
first-time primality assignments (>100 per 1E6 span) at 80.E6 to 87.E6
P-1 factoring assignments (>100 per 1E6 span) at 87.E6 to 89.E6
TF assignments (>100 per 1E6 span) at 88.E6 to 94.E6

[GP2]

Originally Posted by R. Gerbicz

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 !

But how general is this idea?

We have the coincidence that both N = mp = 2^p − 1 and the modulo 2^t involve a power of 2... isn't that what gives a nice simple form for inv, and the simple condition p > t?

If we pick some arbitrary N instead, for instance the base-3-repunit (3^p - 1)/2 , could we still do the final steps and come up with a practical and rapid compositeness test?

[R. Gerbicz]

Originally Posted by GP2

But how general is this idea?
...
If we pick some arbitrary N instead, for instance the base-3-repunit (3^p - 1)/2 , could we still do the final steps and come up with a practical and rapid compositeness test?

You can get the modular inverse with extended Euclidean algorithm, probably gmp has a fast almost linear time implementation; here you could even use Hensel lifting, because the modulus is the pretty nice 2^t. In our case t is small, so even a slow Euclidean algorithm can easily do the job.