mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Reply
 
Thread Tools
Old 2019-02-02, 16:41   #12
chris2be8
 
chris2be8's Avatar
 
Sep 2009

33·5·13 Posts
Default

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
chris2be8 is offline   Reply With Quote
Old 2019-02-03, 01:23   #13
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·29·101 Posts
Default

Quote:
Originally Posted by mathPuzzles View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2019-02-10, 10:04   #14
mathPuzzles
 
Mar 2017

2·3·5 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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!
mathPuzzles is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49
Magnitude 5.6 Earthquake in Silicon Valley ewmayer Science & Technology 66 2008-07-31 15:30
P-1 factoring != "Mersenne numbers to factor"? James Heinrich Marin's Mersenne-aries 8 2004-05-17 11:09
Shortest time to complete a 2^67 trial factor (no factor) dsouza123 Software 12 2003-08-21 18:38
Factoring from the factor-1 jocelynl Math 12 2003-06-27 01:24

All times are UTC. The time now is 21:35.

Thu Apr 9 21:35:47 UTC 2020 up 15 days, 19:08, 0 users, load averages: 1.50, 1.64, 1.80

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.