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

[JuanTutors]

Originally Posted by axn

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 Π).

Ah I missed the step of multiplying by MH^q-1, making it 4 multiplications, not 3.

Can you lead me to an explainer that shows how one multiplication is used to handle two q's? I was under the impression that two multiplications are used to handle one q. One multiplication was used to calculate H^q and then another multiplication was used to calculate Π(H^q-1).

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)) ...

I was trying to find this theorem! Which one is it?

... 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.

So that even though MH^q-1 has I believe on average ln(2) (? or 1?) factors between B2 = 10^7 and B2^2 = 10^14, the probability that any factor we happen to come upon will help us find a factor of Mp is about 10^-10.5, which is about 10^-(10.5-6) = 10^-4.5 times the probability that any factor between B1 and B2 helps. So for whatever cost we add via this method, ignoring all potential factors larger than B^2 due to diminishing benefits, we multiply the probability of finding a factor during this modified stage 2 by about 1+ln(2)*10^-4.5. Does that sound about right? Even if it's on the same order, that's pretty weak.

[axn]

Originally Posted by JuanTutors

Can you lead me to an explainer that shows how one multiplication is used to handle two q's? I was under the impression that two multiplications are used to handle one q. One multiplication was used to calculate H^q and then another multiplication was used to calculate Π(H^q-1).

I hate to do this to you, but... you can read "SPEEDING THE POLLARD AND ELLIPTIC CURVE METHODS OF FACTORIZATION". The whole paper is worth the read, but section 4.1 (Reducing the Cost of the Standard Continuation) is what you want specifically.

Originally Posted by JuanTutors

I was trying to find this theorem! Which one is it?

I don't know any theorem as such, but it follows from the fact that a number p divides every pth term in the number line.

Originally Posted by JuanTutors

So that even though MH^q-1 has I believe on average ln(2) (? or 1?) factors between B2 = 10^7 and B2^2 = 10^14, the probability that any factor we happen to come upon will help us find a factor of Mp is about 10^-10.5, which is about 10^-(10.5-6) = 10^-4.5 times the probability that any factor between B1 and B2 helps. So for whatever cost we add via this method, ignoring all potential factors larger than B^2 due to diminishing benefits, we multiply the probability of finding a factor during this modified stage 2 by about 1+ln(2)*10^-4.5. Does that sound about right? Even if it's on the same order, that's pretty weak.

Not sure about the ln(2) factor, but your reasoning looks good. And the basic conclusion is that, you're better off increasing B2 rather than going this route. In fact, the Brent-Suyama extension is actually trying to do what you're trying to do but in a more efficient way.

[preda]

Maybe related, please see the thread about what I coined "PRP-1": https://www.mersenneforum.org/showthread.php?t=23628