View Single Post
Old 2021-06-24, 03:25   #24
axn
 
axn's Avatar
 
Jun 2003

5,179 Posts
Default

Quote:
Originally Posted by JuanTutors View Post
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.

Quote:
Originally Posted by JuanTutors View Post
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.

Quote:
Originally Posted by JuanTutors View Post
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.

Last fiddled with by axn on 2021-06-24 at 03:30 Reason: space
axn is offline   Reply With Quote