PRP-1

[preda]

Having to re-do the P-1 first-stage for double checking is a hit. (Note that the PRP-1 could be double-checked without redoing the P-1 by saving the Base bits, and starting the double check from there. Even if Base is "wrong" or "random" (e.g. there was an error, undetected, in the P-1-first-stage), the PRP(Base) is still valid and can be double checked).

[preda]

Originally Posted by preda

Your analysis disregards the fact that the PRP-1 *stops* as soon as it detects a factor. So in the lucky situation that a factor is found, the test takes [much] less time then one LL. This is guaranteed through the way the Ks are selected for testing (an overview of the "K selection algorithm" is here: https://mersenneforum.org/showpost.p...4&postcount=43 and source is here: https://github.com/preda/gpuowl/blob...ct/kselect.cpp ) -- that algorithm explicitly favors early Ks that produce big cutoffs when a factor is found.

(PRP-1 does multiple GCDs as it moves along, not a single one at the end).

I'll try to quantify the cost next, but it's more involved.

OK, in my analysis, even considering the early stop of the PRP-1 when a factor is found, based on the probabilities coming from the B1/B2 bounds, PRP-1 is not better than P-1 followed by PRP, with double checks. This is mainly because of the 1.6% supplementary cost for computing the base at the beginning of the double-check. (If that cost is ignored, PRP-1 becomes a bit faster than P-1 + PRP). OTOH the difference between the two is tiny, less than 1% of a single round of PRP.

In my analysis I took the cost of one MUL (general multiplication) as being 2x the cost of a Squring. (because on the GPU, in my implementation, the MUL is that slow). (I approximated the cost of one GCD with 2000 Squarings).

I still think doing some PRP-1 may be worth, at least to explore the empiric performance (i.e. what factors it finds, and frequencies). I also don't know the probabilities for finding factors, so I use lower bounds coming from P-1(B1, B2).

I don't have experience with implementing second-stage of P-1. Could somebody enlighten me WRT the cost of second-stage, as a function of B2?

[axn]

Originally Posted by preda

I don't have experience with implementing second-stage of P-1. Could somebody enlighten me WRT the cost of second-stage, as a function of B2?

Excluding some setup costs, it is one subtraction and one multiplication per pair of primes. Sometimes a given prime cannot be paired; in that case, one subtraction/multiplication for a single prime. (No idea what % of primes can be paired). This of for all primes B1 < p <= B2.

[preda]

Originally Posted by axn

Excluding some setup costs, it is one subtraction and one multiplication per pair of primes. Sometimes a given prime cannot be paired; in that case, one subtraction/multiplication for a single prime. (No idea what % of primes can be paired). This of for all primes B1 < p <= B2.

OK, thanks! and how expensive is the initial setup? is the setup so cheap that it can be disregarded? is the setup cost growing with B2?

[bsquared]

Originally Posted by preda

OK, thanks! and how expensive is the initial setup? is the setup so cheap that it can be disregarded? is the setup cost growing with B2?

Yes it is pretty cheap, and no it is a constant cost. The setup involves choosing a constant D and precomputing powers x^b, for all b relatively prime to D. Then it is a baby-step, giant-step type iteration through the primes from B1 to B2, where the giant step moves up by D and the baby steps accumulate the precomputed small powers. Crandall and Pomerance's book provides more details.

Originally Posted by axn

Excluding some setup costs, it is one subtraction and one multiplication per pair of primes. Sometimes a given prime cannot be paired; in that case, one subtraction/multiplication for a single prime. (No idea what % of primes can be paired). This of for all primes B1 < p <= B2.

In my ECM implementation (P-1 will be similar), about 20% are typically paired. (It's probably possible to do better with more effort.)

[preda]

OK. So comparing the number of multiplication,
in PRP-1 one multiplication in average covers about 2.5 "useful" primes and 2 more "large" primes. So from this aspect PRP-1 looks more efficient than second-stage P-1. OTOH, PRP-1 also does interleaving PRP steps that are not needed (wasted) if a factor is found. It's true that if a factor is found, chances are it's found early in the PRP-1 so there's not so much wastage.

Other small advantages of PRP-1: low memory usage, and much simpler to implement (compared to second-stage P-1). Also the iteration values that are accumulated towards the GCD are error-checked with the GEC (but not the multiplication itself). Thus a bit better error-resistance.

Originally Posted by bsquared

Yes it is pretty cheap, and no it is a constant cost. The setup involves choosing a constant D and precomputing powers x^b, for all b relatively prime to D. Then it is a baby-step, giant-step type iteration through the primes from B1 to B2, where the giant step moves up by D and the baby steps accumulate the precomputed small powers. Crandall and Pomerance's book provides more details.



In my ECM implementation (P-1 will be similar), about 20% are typically paired. (It's probably possible to do better with more effort.)

[preda]

I realize I have only a small understanding of the prime factors of 2^k - 1:

1. (a sufficient condition): if z(p) | k, then p | (2^k - 1)
2. in general, 2^k - 1 has "many factors, thus mostly small factors".

But the condition 1 above is not necessary, meaning there are p such that p|(2^k - 1), yet z(p) does-not-divide k.

For example, I wonder what is the factor coverage of 2^k - 1, for k=0..N.
Let's say, given N, what is the smallest prime p that is not a factor of any 2^k - 1, for k in [0, N]. (maybe a probabilistic argument would help here).

Another way to put it, what's the smallest p that does not divide product(2^k - 1, for k =0..N)

And how does such "smallest p" grow with N?

PS: sure, I mean "odd prime" p. (excluding 2, which is never a factor of 2^k - 1)

[science_man_88]

Originally Posted by preda

I realize I have only a small understanding of the prime factors of 2^k-1

is k composite, or prime?

[preda]

Originally Posted by science_man_88

is k composite, or prime?

Either. Take every value in the interval [0, N].

[axn]

Originally Posted by preda

I realize I have only a small understanding of the prime factors of 2^k - 1:

1. (a sufficient condition): if z(p) | k, then p | (2^k - 1)
2. in general, 2^k - 1 has "many factors, thus mostly small factors".

But the condition 1 above is not necessary, meaning there are p such that p|(2^k - 1), yet z(p) does-not-divide k.

What is z(p)? Also, can you give an example of p|(2^k-1) and z(p) does not divide k ?

EDIT:- Ok, from up thread

For any prime "p", let's call z(p) the multiplicative order of 2 modulo p

[preda]

for p == 1583 423452 213582 178911 805893 942695 192421,
I imagine z(p) does not divide 1620,
yet p divides 2^1620 - 1

Originally Posted by preda

For fun here's the factorization of 2^1620 - 1:
(done with the nice applet https://www.alpertron.com.ar/ECM.HTM )

Tiny factors:
3^5 × 5^2 × 7 × 11 × 13 × 19 × 31 × 37 × 41 × 61 × 73 × 109 × 151 × 163 × 181 × 271 × 331 × 541 × 631 × 811

Average factors, < 3M (e.g. could be covered in first-stage P-1)
1321 × 1621 × 2593 × 6481 × 9721 × 15121 × 23311 × 30241 × 49681 × 54001 × 71119 × 87211 × 135433 × 246241 × 262657 × 279073 × 348031 × 537841

Large factors [3M, 4B] (could be covered in second-stage P-1)
3 618757 × 6 876901 × 18 837001 × 29 247661 × 74 967931 × 97 685839 × 106 979941 × 168 410989 × 272 010961 × 1511 474581 × 2437 880491 × 2458 695061 × 3934 029061

Larger factors, > 4B:

         4977 454861
       448217 524891
     9 893662 806061
    10 360573 664851
    49 971617 830801
   165 041853 060421
   385 838642 647891
  1969 543281 137041
 11096 527935 003481
166242 935471 754241

Huge factors:
1583 423452 213582 178911 805893 942695 192421 (40 digits)
4343 952637 722706 853771 280086 533392 805261 (40 digits)
17 645665 556213 400107 370602 081155 737281 406841 (44 digits)

PS: and when you think that the expected number of factors for a number of that magnitude, given by log(log(x)), is 7.