PRP-1

[kriesel]

(via https://www.alpertron.com.ar/ECM.HTM)

The low powers of small primes (including zero power) are very persistent.
2⁴⁵-1:
7 × 31 × 73 × 151 × 631 × 23311

2⁹⁰-1:
3³ × 7 × 11 × 19 × 31 × 73 × 151 × 331 × 631 × 23311 × 18 837001

2¹⁸⁰-1:
3³ × 5² × 7 × 11 × 13 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 181 × 331 × 631 × 1321 × 23311 × 54001 × 18 837001 × 29 247661

2³⁶⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 181 × 241 × 331 × 433 × 631 × 1321 × 23311 × 38737 × 54001 × 61681 × 18 837001 × 29 247661 × 4562 284561 × 168692 292721 × 469775 495062 434961

2⁷²⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 241 × 257 × 331 × 433 × 577 × 631 × 673 × 1321 × 23311 × 38737 × 54001 × 61681 × 8 369281 × 18 837001 × 29 247661 × 394 783681 × 4278 255361 × 4562 284561 × 46908 728641 × 168692 292721 × 487824 887233 × 469775 495062 434961 × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits)

2¹⁴⁴⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 193 × 241 × 257 × 331 × 433 × 577 × 631 × 673 × 1153 × 1321 × 6337 × 23041 × 23311 × 37441 × 38737 × 54001 × 61681 × 65537 × 414721 × 8 369281 × 18 837001 × 22 253377 × 29 247661 × 170 251201 × 394 783681 × 4278 255361 × 4562 284561 × 38941 695937 × 46908 728641 × 168692 292721 × 278452 876033 × 487824 887233 × 44 479210 368001 × 469775 495062 434961 × 322029 272318 997936 286081 × 14768 784307 009061 644318 236958 041601 (35 digits) × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits) × 19 194878 188585 855612 908061 936944 281464 039294 965346 491767 953330 250249 208842 371201 (80 digits)

2²⁸⁸⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 193 × 241 × 257 × 331 × 433 × 577 × 631 × 641 × 673 × 1153 × 1321 × 3457 × 6337 × 23041 × 23311 × 26881 × 37441 × 38737 × 54001 × 61681 × 65537 × 414721 × 816769 × 3 602561 × 4 855681 × 6 700417 × 8 369281 × 18 837001 × 22 253377 × 29 247661 × 170 251201 × 252 581761 × 394 783681 × 610 548481 × 4278 255361 × 4562 284561 × 38941 695937 × 40056 698881 × 46908 728641 × 137603 804161 × 168692 292721 × 278452 876033 × 487824 887233 × 44 479210 368001 × 469775 495062 434961 × 18 446744 069414 584321 × 1562 985901 350085 709953 × 35884 034243 486024 947201 × 322029 272318 997936 286081 × 1422 346738 975853 644793 916289 × 94 455684 953484 563055 991838 558081 (32 digits) × 14768 784307 009061 644318 236958 041601 (35 digits) × 10559 241583 796365 631935 764162 530238 561452 234881 (47 digits) × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits) × 19 194878 188585 855612 908061 936944 281464 039294 965346 491767 953330 250249 208842 371201 (80 digits) × 4276 202518 377048 758710 155342 353333 706768 924554 871702 146065 458722 945361 455046 432284 334859 214206 464193 849093 546239 246569 628374 820370 315723 445533 006062 273968 836272 127051 941159 287286 772618 435201 (190 digits)
(the factoring for 2880 took 25.7 minutes, while for 1440 ~1.8 minutes, for 720 ~0.1 second)

[preda]

Originally Posted by preda

But, this initial cost is exactly the same as the cost of first stage P-1 to the same bound B1. The setup of "base" is indeed a P-1 first stage. So it can and should replace a separate P-1 first-stage being done before starting the PRP.

A different way to see things is:

- do the normal P-1 before the PRP, but skip the second-stage (do first stage only). Do it with any software BUT save the 3^P that is computed during the normal P-1.

- the PRP-1 reads the 3^P=Base, and uses it.

Of course this would be more practical if different people involved could easily exchange the bits of 3^P between tests. (one person does the "classic" P-1 with B2=B1, and exports Base to the person doing PRP-1).

[preda]

Originally Posted by kriesel

(via https://www.alpertron.com.ar/ECM.HTM)

The low powers of small primes (including zero power) are very persistent.
2⁴⁵-1:
2⁹⁰-1:
2¹⁸⁰-1:
2³⁶⁰-1:
2⁷²⁰-1:
2¹⁴⁴⁰-1:
2²⁸⁸⁰-1:

Thank you for the analysis! Indeed, in the distribution of such factors lies the answer to how effective (or not so) is the method.

But, don't just double the power. Doing that has a tendency to preserve the same list of factors (with a few additions, as you show), simply because:
2^(2n) -1 == (2^n - 1) * (2^n + 1),
so 2^n - 1 is preserved, and 2^n + 1 is added. (but 2^n + 1 has relatively few factors).

Could you please try exponents like 360*k or 180*k instead. Or, for something different, 300 * k.

[preda]

Originally Posted by preda

Indeed, in the distribution of such factors lies the answer to how effective (or not so) is the method.

IF the distribution of factors turned out to be much better than I hope, we could use a much lower B1 in Base. At the limit, Base would be something like 3^(2 * p * 2^60) for M(p), with practically no effort in computing Base. But I'm not so optimistic.

(the large power of 2 there is because 2^k-1 doesn't produce 2s)

[kriesel]

Originally Posted by preda

The cost of the GCD can be replaced by the cost of a normal modular multiplication plus an arbitrarily low fraction of the GCD cost, with the drawback of delayed detection of factor.

In one extreme, we could [do] the GCD every 360 iterations. But if less GCD-overhead is desired, it can be done once every 360K, or every 36M iterations, and then the GCD becomes negligible, but there's instead one multiplication every 360 iteration. The overhead of the mul is similar to the overhead of the error checking used now (which does one mul every 400 iterations). Let's estimate it to 0.5%. This can be reduced, by increasing the step (from 360), with the drawback of doing a smaller number of P-1 "trials".

The error check is affected by replacing the "mul-by-3" with "mul-by-Base" in the checking step (which, by default, is now done once every 160K iterations). So, one additional mul every L^2 iterations for the check -- this is so small that it can be ignored.

The main cost is in the initial computation of Base=3^P, and this cost is log2(P) normal squaring iterations (with the "mul-by-3" being free, sunk in the squaring). Let's say this costs about 1M or 2M iterations.

But, this initial cost is exactly the same as the cost of first stage P-1 to the same bound B1. The setup of "base" is indeed a P-1 first stage. So it can and should replace a separate P-1 first-stage being done before starting the PRP.

So overall, simplifying, I would say the cost vs. unmodified PRP is about 1% (but is dependent on the B1 and exponent). This becomes lower if compared vs. (P-1 first stage + PRP).

What we gain, I estimate, is the equivalent of a "second-stage" P-1 being done for free; and I hope even more than that (i.e. "more" meaning equivalent to P-1 done to higher B1 and B2).

For comparison, see the attachment at http://www.mersenneforum.org/showpos...27&postcount=2 which shows the runtime ratio between P-1 (both stages 1 and 2) by CUDAPm1 v0.20 (for automatically determined bounds, e, etc) and primality testing by CUDALucas 2.05 or 2.06 at 1% to 2.5% as a function of exponent, with the current wavefront at about 2%. This was for a GTX480, which is limited by its 1.5GB VRAM to some somewhat restrictive bounds.

Two million iterations is 2+% currently.
It seems worth exploring further, with a quick simple prototype program to try it on some actual exponents and compare results to traditional P-1.

[kriesel]

Originally Posted by kriesel

(via https://www.alpertron.com.ar/ECM.HTM)

The low powers of small primes (including zero power) are very persistent.
2⁴⁵-1:
7 × 31 × 73 × 151 × 631 × 23311

2⁹⁰-1:
3³ × 7 × 11 × 19 × 31 × 73 × 151 × 331 × 631 × 23311 × 18 837001

2¹⁸⁰-1:
3³ × 5² × 7 × 11 × 13 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 181 × 331 × 631 × 1321 × 23311 × 54001 × 18 837001 × 29 247661

2²⁷⁰-1:
3^[B]4[/B] × 7 × 11 × 19 × 31 × 73 × 151 × 271 × 331 × 631 × 811 × 15121 × 23311 × 87211 × 262657 × 348031 × 18 837001 × 49 971617 830801 × 385 838642 647891

2³⁶⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 181 × 241 × 331 × 433 × 631 × 1321 × 23311 × 38737 × 54001 × 61681 × 18 837001 × 29 247661 × 4562 284561 × 168692 292721 × 469775 495062 434961

2⁵⁴⁰-1:
3⁴ × 5² × 7 × 11 × 13 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 181 × 271 × 331 × 541 × 631 × 811 × 1321 × 15121 × 23311 × 30241 × 49681 × 54001 × 87211 × 246241 × 262657 × 279073 × 348031 × 18 837001 × 29 247661 × 49 971617 830801 × 165 041853 060421 × 385 838642 647891 × 166242 935471 754241

2⁷²⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 241 × 257 × 331 × 433 × 577 × 631 × 673 × 1321 × 23311 × 38737 × 54001 × 61681 × 8 369281 × 18 837001 × 29 247661 × 394 783681 × 4278 255361 × 4562 284561 × 46908 728641 × 168692 292721 × 487824 887233 × 469775 495062 434961 × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits)

2¹⁴⁴⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 193 × 241 × 257 × 331 × 433 × 577 × 631 × 673 × 1153 × 1321 × 6337 × 23041 × 23311 × 37441 × 38737 × 54001 × 61681 × 65537 × 414721 × 8 369281 × 18 837001 × 22 253377 × 29 247661 × 170 251201 × 394 783681 × 4278 255361 × 4562 284561 × 38941 695937 × 46908 728641 × 168692 292721 × 278452 876033 × 487824 887233 × 44 479210 368001 × 469775 495062 434961 × 322029 272318 997936 286081 × 14768 784307 009061 644318 236958 041601 (35 digits) × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits) × 19 194878 188585 855612 908061 936944 281464 039294 965346 491767 953330 250249 208842 371201 (80 digits)

2²⁸⁸⁰-1:
3³ × 5² × 7 × 11 × 13 × 17 × 19 × 31 × 37 × 41 × 61 × 73 × 97 × 109 × 151 × 181 × 193 × 241 × 257 × 331 × 433 × 577 × 631 × 641 × 673 × 1153 × 1321 × 3457 × 6337 × 23041 × 23311 × 26881 × 37441 × 38737 × 54001 × 61681 × 65537 × 414721 × 816769 × 3 602561 × 4 855681 × 6 700417 × 8 369281 × 18 837001 × 22 253377 × 29 247661 × 170 251201 × 252 581761 × 394 783681 × 610 548481 × 4278 255361 × 4562 284561 × 38941 695937 × 40056 698881 × 46908 728641 × 137603 804161 × 168692 292721 × 278452 876033 × 487824 887233 × 44 479210 368001 × 469775 495062 434961 × 18 446744 069414 584321 × 1562 985901 350085 709953 × 35884 034243 486024 947201 × 322029 272318 997936 286081 × 1422 346738 975853 644793 916289 × 94 455684 953484 563055 991838 558081 (32 digits) × 14768 784307 009061 644318 236958 041601 (35 digits) × 10559 241583 796365 631935 764162 530238 561452 234881 (47 digits) × 750 016890 283777 055704 738227 247474 485366 338380 663681 (51 digits) × 19 194878 188585 855612 908061 936944 281464 039294 965346 491767 953330 250249 208842 371201 (80 digits) × 4276 202518 377048 758710 155342 353333 706768 924554 871702 146065 458722 945361 455046 432284 334859 214206 464193 849093 546239 246569 628374 820370 315723 445533 006062 273968 836272 127051 941159 287286 772618 435201 (190 digits)
(the factoring for 2880 took 25.7 minutes, while for 1440 ~1.8 minutes, for 720 ~0.1 second)

It's looking too sparse to me. Sort of a Monte Carlo method.

[preda]

Originally Posted by kriesel

It's looking too sparse to me. Sort of a Monte Carlo method.

Not covering all the primes in one trial, being sparse, is not necessarily a problem. The distribution is important too. By "distribution" I mean the probability of the primes of being present depending on their magnitude, and the property of different "trials" covering different primes.

Trying to show why just being sparse is not a problem, compare with second stage of P-1, where primes p with B1<p<=B2 are tried *one at a time* (simplifying).
Like this: base=powersmooth(B1) -- this number is not sparse,

for each p in [B1, B2):
x = base * p -- this is very sparse, because it has a single prime in the range [B1, B2).

Let's consider the kind of factor that is detected by P-1(B1, B2):
a number F = 2 * exp * p1 * p2 *..* pn * a + 1, where each p1, p2,..,pn < B1, and only "a" is in [B1, B2)

So the question is, what is the probability that this set of factors (p1,..,pn, a) are all present in one of the "trials".

The first question would be, how *many* factors are in the list p1,p2,..pn,a? A back of the envelope estimation shows me I would expect about 6-7 (with usual B1/B2 bounds).

So, now let's rephrase: if we take a set of 6 primes under B1, and one in [B1, B2), what is the probability of this set of being included in at least one of our trial sets of factors?

Again simplifying, but if the our trial set has a coverage of 50%, we would expect a probability of inclusion of the 7 factors of 1/(2^7), which is not too bad. (but to answer this adequately, we'd need to consider the "distribution", because small primes and large ones have different probabilities)

[preda]

Originally Posted by kriesel

It's looking too sparse to me. Sort of a Monte Carlo method.

Another interesting question is: what is the distribution of the factors of 2^k - 1 when k is on the order of 300M? Our experiments with "small" values such as 2^(360*7) - 1 may not be a good indicator for the large exponents.

[preda]

I think that choosing good powers k for the factors of 2^k-1 is not so simple.
For one, if a|b then 2^a -1 | 2^b -1. So choosing a multiple of a k already tested adds fewer fresh factors.

If k is highly composite 2^k-1 has more factors, but they are smaller. If the PRP Base is 3^powerSmooth(B1), I think what we want is to maximize the number of factors that are larger than B1, but not too far from B1.

And, the savings from finding a factor while the PRP is ongoing decrease as the PRP nears the end. While the large Ks that produce many factors are at the end of the PRP.

[preda]

I realized this interesting fact (relevant in the context):
for any odd prime p, there exists a k < p such that p | 2^k - 1.

Why?

[a1call]

Originally Posted by preda

I realized this interesting fact (relevant in the context):
for any odd prime p, there exists a k < p such that p | 2^k - 1.

Why?

Well, p-1 < p
and
for any given prime

p ! a^(p-1)-1 for all a coprime to p.

See Fermat's little Theorem which pops up here periodically.