 mersenneforum.org > Math Can we begin PRP using part of the results of P-1 stage 1?
 Register FAQ Search Today's Posts Mark Forums Read  2021-06-23, 23:00   #23
JuanTutors

"Juan Tutors"
Mar 2004

10608 Posts Quote:
 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).

Quote:
 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?

Quote:
 ... 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.   2021-06-24, 03:25   #24
axn

Jun 2003

24·7·47 Posts Quote:
 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.

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

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

Last fiddled with by axn on 2021-06-24 at 03:30 Reason: space   2021-07-06, 17:27 #25 preda   "Mihai Preda" Apr 2015 101010111112 Posts Maybe related, please see the thread about what I coined "PRP-1": https://www.mersenneforum.org/showthread.php?t=23628   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Ensigm Factoring 9 2020-08-24 17:32 Chuck PrimeNet 64 2014-01-06 01:22 dabaichi PrimeNet 5 2011-12-07 19:27 Unregistered Information & Answers 0 2010-11-30 23:34 davieddy Lounge 9 2009-08-25 20:01

All times are UTC. The time now is 23:30.

Mon Jan 17 23:30:54 UTC 2022 up 178 days, 17:59, 0 users, load averages: 1.24, 1.24, 1.29