Thread: Saving computation in ECM View Single Post
2004-06-02, 18:00   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

27D316 Posts

Quote:
 Originally Posted by dave_dm Suppose we have run 2900 curves with B1 = 3e6 and we now want to run 5500 curves with B1 = 11e6. If we continue on from the old residues then we've already done about 15% of the work. This saving is superficially significant. (15% = (3e6 * 2900) / (11e6 * 5500)). Of course, the snag here is conditional probability: since we know that 2900 curves have failed to yield a factor, continuing them to B1 = 11e6 has a lower probability of success than running 2900 'fresh' curves to B1 = 11e6. There are some good papers out there which show us how to reselect parameters after failure, but none (that I've found) suggest that we keep the residues from previous trials. Has anyone looked into working out such an algorithm? Dave
Yes, they have.

Exercise: go read up on how to drive version 5 of the GMP-ECM program written primarily by Paul Zimmermann and Alex Kruppa, with assistance from many others. There are enough keywords in the previous sentence to enable you to find the requisite course materials by using any half-way decent search engine.

As you note, whether it's worth continuing is an entirely different question, and the subject of another and rather harder exercise.

Paul