mersenneforum.org > Math Factoring when one factor's magnitude is known
 Register FAQ Search Today's Posts Mark Forums Read

 2019-02-02, 16:41 #12 chris2be8     Sep 2009 1,753 Posts Considering run times you would be better off running ECM. The P-1 approach would be a lot slower. But it's useful to prove the oracle wrong if a lot of ECM work hasn't found a factor (it's possible but unlikely for 20 times as much ECM as would be expected to find a factor to miss it, while P-1 with suitable limits etc would never miss unless there's a hardware error). Chris
2019-02-03, 01:23   #13
CRGreathouse

Aug 2006

2·2,927 Posts

Quote:
 Originally Posted by mathPuzzles What is Chelli's trick? I was not able to find a reference by searching the forum or Google. Edit: it's probably this deterministic ECM algorithm?
Exactly. If you had a smaller bound like 2^32 (or a sparse set of primes) you could do what Chelli did and carefully design curves which are guaranteed to find all the factors you need (or more practically, all the factors outside a small collection, which you can remove with a single GCD operation). But 2^48 would take at least 2^(48-32)*32/48 = 43,691 more effort to compute (in practice, a good bit more than that) than the 2^32 that Chelli used.

2019-02-10, 10:04   #14
mathPuzzles

Mar 2017

1E16 Posts

Quote:
 Originally Posted by CRGreathouse But 2^48 would take at least 2^(48-32)*32/48 = 43,691 more effort to compute (in practice, a good bit more than that) than the 2^32 that Chelli used.
As always there are tradeoffs. But this was a really interesting idea and the idea really is interesting and clever.. just not super practical. Still, that's how we learn. Thanks very much for the reference!

 Similar Threads Thread Thread Starter Forum Replies Last Post xx005fs GPU Computing 3 2018-10-27 14:49 ewmayer Science & Technology 66 2008-07-31 15:30 James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09 dsouza123 Software 12 2003-08-21 18:38 jocelynl Math 12 2003-06-27 01:24

All times are UTC. The time now is 11:05.

Tue Mar 31 11:05:28 UTC 2020 up 6 days, 8:38, 0 users, load averages: 1.38, 1.46, 1.32