Can we begin PRP using part of the results of P-1 stage 1?

[Zhangrc]

Originally Posted by JuanTutors

Perhaps 18.4 prime factors for each value of k is enough to make it matter? Or would the GCD stage take too long?

Only 18.4? You need tens of thousands, if not millions.

[JuanTutors]

Originally Posted by Zhangrc

Only 18.4? You need tens of thousands, if not millions.

I was making a suggestion for stage 2, where just one additional prime at a time is being tested (as far as I understand it). In fact a value of B1=10^6 has approximately 72000 prime factors, so 18.4 prime factors would not be bad. I think the problem might be more that the 2^m+k is usually quite large.

[JuanTutors]

I think there may be a worthwhile modification of my suggestion merging Zhangrc's suggestion and mine. After posting a [BADLY FLAWED] suggestion above is perhaps fixable?

First, a random number with 10^8 digits has on average distinct prime factors, which is why I was suggesting waiting until near the end to perform a third P-1 test. However, even a smaller integer with 10^6 digits has on average distinct prime factors.

Also, please correct me if I am wrong, but is it not be the case that Mp is as likely to be a probable prime base 3 as it is to be a probable prime base 3^(2pE)?

If this is the case, then my suggestion is that we perform the PRP test base 3^(2pE). Then when the test is 1% of the way done on iteration m ≈ Mp/100 ≈ 10^6, less than a week into the PRP test in many cases, we pause the PRP test and do a stage 2 (stage 3?) PRP test with 3^(2pE*(2^m+k)) for adequately chosen values of k. This would test approximately 14.65 distinct prime factors on each iteration.

[JuanTutors]

Originally Posted by LaurV

Then you take the GCD step, and... what?

(from another thread)

Please see my above post where I modified my suggestion. As you see above I suggested performing the PRP test with 3^(2pE) instead of with 3, and then stopping at the m = millionth or so iteration and taking GCDs of 3^(2pE(2^m+k)) for various well-chosen values of k.

There are alternate variations of this, but to answer your question, which was, take the GCD and then ... what? If the GCD is not 1, we know that a factor exists from the test, and therefore Mp is not prime. Yes, its' true that we will not know the factor of Mp, because we will not know the factors of 2^m+k, but we will know that Mp is not prime, which has always been the goal of the PRP test. We could, in the future if motivated, factor 2^m+k for as long as it takes to find that factor of Mp, or not.

[Viliam Furik]

Originally Posted by JuanTutors

(from another thread)

Please see my above post where I modified my suggestion. As you see above I suggested performing the PRP test with 3^(2pE) instead of with 3, and then stopping at the m = millionth or so iteration and taking GCDs of 3^(2pE(2^m+k)) for various well-chosen values of k.

There are alternate variations of this, but to answer your question, which was, take the GCD and then ... what? If the GCD is not 1, we know that a factor exists from the test, and therefore Mp is not prime. Yes, its' true that we will not know the factor of Mp, because we will not know the factors of 2^m+k, but we will know that Mp is not prime, which has always been the goal of the PRP test. We could, in the future if motivated, factor 2^m+k for as long as it takes to find that factor of Mp, or not.

Do we need to factor the 2^m+k? It's my understanding of GCD that if for any number, in this case, some power of 3, we do GCD of it (minus 1) and the Mersenne number, and we get result other than 1, the result will directly be a factor of Mersenne number, per definition of GCD. If the factor isn't the Mersenne number itself, we are good.

It sounds like a reasonable feature if it works as promised.

Using the PRP test as a free booster to speed up the ride is a great idea, IMO. If we start the test with a modular residue of 3^(2*p*E), where E is computed using B1=1,000,000, and we compute the entire PRP test with this value, what we get in the end is 3^(2*p*E*(2^p-1)), which can still give us a factor, and has the added benefit of determining PRP, because if Mp is prime, then the residue of 3^(k*(2^p-1)) is still 3 (mod 2^p-1). However, in the case of a composite, residues will no longer match for different runs, i.e. with different B1 sizes, but certification should still be possible because we are still doing the same test, but with a different starting value (others should correct me on that if I am wrong because I'm not sure).

It could also be done the other way around. First, perform the PRP test. Then, use the residue in P-1, instead of 3.

As I think about it, it is quite possible it will give no benefit, one way or the other. I think that the only way it could benefit the P-1 would be when the 2^m+k would have just the right factors that are higher than B1.

What do you think?

[JuanTutors]

Originally Posted by Viliam Furik

Do we need to factor the 2^m+k?

No, you are correct, we do not need to know the exact smoothness of the factor of Mp. That was my mistake. I will edit my post to acknowledge my deletion.

Originally Posted by Viliam Furik

It sounds like a reasonable feature if it works as promised.

Agreed.

Originally Posted by Viliam Furik

Using the PRP test as a free booster to speed up the ride is a great idea, IMO.

Hopefully it's possible. GPUto72 already implements a time saver using 3^(2pE). I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor. (For some reason I have in my mind the idea that for a random number, the length of its successive distinct prime factors grows on average by multiples of 2.)

I don't know the exact details of the P-1 implementation in GIMPS, but if k can be taken as multiples of E, then it can be guaranteed that 2^n+k has no common factors with E. If not, then I guess other methods of choosing k may be more appropriate, such as choosing k to be a multiple of a smaller primorial.

From what I understand, if we start the PRP test with base 3^(2pE) instead of base 3, then calculating this modified stage 2 (stage 3?) means taking the mth step, which is 3^(2pE(2^m)) and multiplying that by a large array 3^(2pEk) for with k replaced with 1K, 2K, 3K, ..., nK for K a primorial (and if K can be replaced with E, even better), and then getting the GCD.

//EDIT: Looking more deeply at the P-1 Stage 2 algorithm, if letting K = E is possible, then storing 3^(2pE*E*2), 3^(2pE*E*4), 3^(2pE*E*6), 3^(2pE*E*8), ... allows us to then use the same bounds B1 and B2 to calculate 3^(2pE*(2^m+qE)) for all primes q such that B1<q<=B2, ensuring that each individual (2^m+qE) in (B1,B2] is neither divisible by a factor of E nor by q, making this a true stage 3.

[Viliam Furik]

Originally Posted by JuanTutors

I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor.

I don't know about such a theorem, but I do know there is an unproven conjecture called "abc conjecture", which says something about factors of sums. However, I don't it's useful in this case.

[Dr Sardonicus]

Originally Posted by JuanTutors

<snip>
I was trying to find the theorem about the length of the distinct prime factors of a randomly chosen large integer, but I could not find it to estimate the probability of finding a factor. (For some reason I have in my mind the idea that for a random number, the length of its successive distinct prime factors grows on average by multiples of 2.)
<snip>

Not quite what you're asking, but possibly related:

Hardy-Ramanujan Theorem

Erdős-Kac Theorem

Golomb-Dickman Constant

Mersenne numbers have a number of well known properties which mark them as special, e.g. if p > 2 is prime, and q divides 2^p - 1, then q = 2*p*k + 1 for some positive integer k.

I don't have statistics for the number of factors, or the size of the smallest factor of 2^p - 1, but I imagine someone does. I have, from time to time, gone through factor tables for small exponents looking for smallest factors q for which log(q)/(p*log(2)) is largest. The "nightmare" case is that 2^p - 1 is a P2 with log(q) > p*log(2)/3.

It is a humbling thought that 2^1277 - 1 is known to be composite, a C385, but has yet to be factored. It is known to have no factors less than 2^68. AFAIK it could be a P2 with smallest factor > 2^425.

[JuanTutors]

Not quite the theorems I was after, but my last statement makes me realize that if we can delay stage 2 until PRP has run through its first 10^6 iterations or so, and again assuming that we can perform the PRP test with 3^2pE instead of with 3, then without too much difficulty and just double the time for stage 2, plus waiting until iteration m = 10⁶, we can perform this modified stage 2 with a tremendous number more factors. In fact, letting m be the iteration number of the PRP test, so m = 10⁶ or so:

(3^{2pE*2^m})*(3^2pEq)*(3^2pEq-1) = (3^{2pE(2^m+q)})*(3^2pEq-1)

On the left, the second and third factor differ just by 1, so they can be calculated simultaneously. The only two costs of this modified stage 2 are then actually getting to iteration m=10^6 and also multiplying by both of those factors 3^2pEq and 3^2pEq-1 mod Mp. So for double the multiplication and waiting for iteration m = 10^6, we get about 13.6 possible prime factors per iteration of stage 2.

As a modification of this -- and I don't know whether this is possible or even helpful based on the increased cost -- If we cut the array containing 3^2pE*2, 3^2pE*4, 3^2pE*6, ... in half (by cutting out the later half of the list) so that we can then store a second array of the same half-length containing 3^2pE*2pE*2, 3^2pE*2pE*4, 3^2pE*2pE*6, ... then we can modify the above test to calculate

(3^{2pE*2^m})*(3^2pE*2pEq)*(3^2pEq-1) = (3^{2pE(2^m+2pEq)})*(3^2pEq-1)

This guarantees that on the right, this new product has some number of prime factors which are distinct from factors of E and q.

[JuanTutors]

I think the following alternate Stage 2 algorithms are well thought out. I wrote this and sat with it for a few days before posting because I wanted to make sure I understood the Pm1 algorithms so that I do not accidentally mix Stage 1 and 2. These two modifications are what I would like to present. My apologies if they are flawed, and please tell me if you see a flaw. I currently do not see one.

Let Mp be the Mersenne number to be tested.

Let B1 and B2 be chosen as usual. Assume B2 > B1 as when a great deal of ram is used.

Let E be the exponent calculated in Stage 1 of Pm1.

Suppose that Pm1 found no factors in stage 1.

Let H = 3^2pE as usual.

Modification 1:

Suppose we are willing to perform the PRP test base H instead of base 3.

Let m = the iteration number for the PRP test. We can presuppose m = 10^6.

Before Stage 2 of Pm1, we perform the first m iterations of the PRP test using base H.

Let M = H^{2^m} = 3^{2pE*2^m} = value of the m^th iteration of the PRP test mod Mp with base H instead of base 3.

Modification 1 of Stage 2 calculates the following:

Π (M*H^q-1)*(H^q-1) mod Mp = Π (3^{2pE*(2^m+q)}-1)*(3^2pEq-1) mod Mp, where this product is taken over all q such that B1<q<=B2.

The time cost of this Modification 1 of Stage 2 algorithm are 50% larger, plus the cost of arriving at iteration m = 10^6 based on this procedure, which according to my computer's speed adds about 25% more time depending on the length of Mp. Thus, in total, including Stage 1, this Pm1 test is about 38% more time expensive:

1. Calculate M. (First 1% of the PRP test.)
2. Calculate H^q. (First multiplication, from an array, and part of the original Stage 2 algorithm)
3. Multiply M by H^q and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.)
4. Multiply by H^q-1. (Third multiplication, and part of the original stage 2 algorithm)

The gain is all the unknown factors of each 2^m+q, which have on average 13.45 distinct prime factors each, a huge step from the single prime factor q. Note that 2^m+q may have common factors with E. However, since 2^m+q has over 3*10⁵ digits, that does not prevent us from gaining many prime factors.

Modification 2 of Stage 2 calculates the following:

Suppose we do not want to perform the PRP test base H and we insist on performing the PRP test base 3.

Then let B3 = a (necessarily even) primorial such that B3 >> B2.

Let M = H^B3

Instead, Modification 2 of Stage 2 calculates the following:

Π (M*H^q-1)*(H^q-1) mod Mp = Π (3^2pE(B3+q)-1)*(3^2pEq-1) mod Mp, where this product is taken over all q such that B1<q<=B2.

The time cost of this Modification 2 of Stage 2 algorithm are 50% larger, plus fast calculation of M, even for B3 equaling a fairly large primorial. Thus in total, including Stage 1, this Pm1 test is about 25% more time expensive:

1. Calculate M. (Fairly fast.)
2. Calculate H^q. (First multiplication, from an array, and part of the original Stage 2 algorithm)
3. Multiply M by H^q and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.)
4. Multiply by H^q-1. (Third multiplication, and part of the original stage 2 algorithm)

The gain is all the factors of each B3+q, none of which are divisible by factors of B3 nor by q. Primorials grow quickly in length, so with very few multiplications, B3 could be much, much larger than B2. Prime95 is already equipped to handle the multiplication of all small primes below 40 million. My understanding as of now is that it is better to have B3 >> B2. If B3 can be taken as 2pE or just p*B1#, each B3+q could be guaranteed to have no factors in common with E and q. I think the smallest viable value of B3 is the smallest primorial greater than B2^1/0.2 based on a cursory understanding of the Dickman function.

I do not want to dig into any other modifications (such as combining Modifications 1 and 2 or sacrificing time and splitting any of these into the usual Stage 2 and a true Stage 3) until we discuss above. At the risk of perhaps missing a basic mistake, I think these two modifications work and are beneficial.

[axn]

Originally Posted by JuanTutors

Modification 1 of Stage 2 calculates the following:
1. Calculate M. (First 1% of the PRP test.)
2. Calculate H^q. (First multiplication, from an array, and part of the original Stage 2 algorithm)
3. Multiply M by H^q and subtract 1. (Second multiplication, and the only new multiplication. The subtraction is essentially free.)
4. Multiply by H^q-1. (Third multiplication, and part of the original stage 2 algorithm)

Current P-1 stage 2 uses 1 multiplication to handle two q's. In your new scheme, it will take 4 multiplications to handled 1 q (Hq, M*Hq, (Hq-1) * (M*Hq-1), and Π).

Originally Posted by JuanTutors

The time cost of this Modification 1 of Stage 2 algorithm are 50% larger, plus the cost of arriving at iteration m = 10^6 based on this procedure, which according to my computer's speed adds about 25% more time depending on the length of Mp. Thus, in total, including Stage 1, this Pm1 test is about 38% more time expensive:

That makes it roughly 8x costlier stage 2. Since stage 2 is already longer than stage 1, overall this will be about 5x more time than regular P-1.

Originally Posted by JuanTutors

The gain is all the unknown factors of each 2^m+q, which have on average 13.45 distinct prime factors each, a huge step from the single prime factor q. Note that 2^m+q may have common factors with E. However, since 2^m+q has over 3*10⁵ digits, that does not prevent us from gaining many prime factors.

Sadly, most of the 13.45 factors are completely useless. A factor q will divide a p-1 with probability 1/q (well, technically 1/(q-1)). Which means, for example, a 10-digit q is only 1% as good as an 8-digit q. A 20-digit q is 1/10 billion as good as a 10-digit q. So, while we gain a lot of factors, there is not a chance in our life time to ever see one appear in a found factor's P-1 decomposition. You're better off to just increase the B2 bound in traditional stage 2.