View Single Post
Old 2007-07-18, 16:04   #7
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by akruppa View Post
What do you mean by "Is there a 100% chance?"

I.e., are you asking if doing the 4590 curves with ECM is guaranteed to find a factor? In this case, the answer is no. Whether ECM finds a factor depends on hitting a lucky curve with a smooth group order, and it's perfectly possible not to hit one with however many curves you do (but if your missing prime factor isn't too large and you choose parameters sensibly, the probability of missing it will tend to zero quickly).

If you're asking "Is there a method that will factor my number with certainty, should ECM fail?" then the answer is yes: GNFS will. GGNFS and msieve should both be able to handle a c126. If your c126 is of a certain form (for example a cyclotomic number) you can use SNFS and factor it in less than a day.


A correction. GGNFS will not succeed "with certainty". If your number is,
for example, a prime power it will fail. It may fail anyway, albeit with
very very low probability. But that probability is not 0.

And ECM never succeeds with certainty either.
R.D. Silverman is offline   Reply With Quote