mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2021-06-23, 23:00   #23
JuanTutors
 
JuanTutors's Avatar
 
"Juan Tutors"
Mar 2004

13·43 Posts
Default

Quote:
Originally Posted by axn View Post
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.
JuanTutors is offline   Reply With Quote
Old 2021-06-24, 03:25   #24
axn
 
axn's Avatar
 
Jun 2003

2·23·113 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
Old 2021-07-06, 17:27   #25
preda
 
preda's Avatar
 
"Mihai Preda"
Apr 2015

53·11 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
How to make GMP-ECM skip stage 1 when feeding the prime95 results Ensigm Factoring 9 2020-08-24 17:32
When did PrimeNet begin rubberstamping results? Chuck PrimeNet 64 2014-01-06 01:22
Only submit part of ECM results? dabaichi PrimeNet 5 2011-12-07 19:27
In which country do you suggest me to begin my act Unregistered Information & Answers 0 2010-11-30 23:34
When did Rock'n'Roll begin? davieddy Lounge 9 2009-08-25 20:01

All times are UTC. The time now is 06:49.


Mon Dec 6 06:49:04 UTC 2021 up 136 days, 1:18, 0 users, load averages: 1.77, 1.60, 1.55

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.