Usage of GMP-ECM

[ECMFreak]

Hi everybody!
I'm using GMP-ECM 6.0.1 and trying to factor a C126. How can I make ecm to do x curves (beginning from curve y) and how to choose the B1 and B2 parameters? (I used B1=11000000 until now)

Thanks, ECMFreak

[akruppa]

GMP-ECM will try n curves with the "-c n" command line option, however it will stop if it finds a factor and the cofactor is prime. With the "-one" option added, it will stop when it finds a factor, even if the cofactor is composite.

How to choose parameters depends on what factor size you are aiming for. Did you read the README file?

Btw, version 6.0.1 is a bit outdated. The current version is 6.1.2.

Alex

[ECMFreak]

Thanks, I will first compile the new version!

[rogue]

You might also want to consider ECMNet, even if it is only one number (or a small set of numbers).

[ECMFreak]

Hi, thanks, I'm using ECMNet now (with the newest ECM version), it works really good (because it sets the paramteres for you). But one question: Is there a 100 % cahnce to get a factor after the 4590 curves I have to do for my C126? (Because if ECM finds a 30 digit factor, I can factor it and the cofactor by MPQS or even by ECM)

Thanks, ECMFreak

[akruppa]

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.

Alex

[R.D. Silverman]

Originally Posted by akruppa

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.

Alex

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.

[ECMFreak]

My number is C126_122_48 of XYYXF, so 122^48+48^122. I haven't found any 4th or 5th degree polynomial yet (i think 5th degree is better for this size) and I think if i use a GNFS polynomial, it will take a very, very long time. i tried to factor some c130s with msieve-gnfs some weeks ago, but i needed around 7.2 millions of relations and msieve found only 50 per 30 minutes. I think even if you're using GGNFS you need a good polynomial. I will try ECM fist. Maybe it will find a factor.

Thanks, ECMFreak

[frmky]

Originally Posted by ECMFreak

My number is C126_122_48 of XYYXF, so 122^48+48^122. I haven't found any 4th or 5th degree polynomial yet (i think 5th degree is better for this size) and I think if i use a GNFS polynomial, it will take a very, very long time. i tried to factor some c130s with msieve-gnfs some weeks ago, but i needed around 7.2 millions of relations and msieve found only 50 per 30 minutes. I think even if you're using GGNFS you need a good polynomial. I will try ECM fist. Maybe it will find a factor.

Thanks, ECMFreak

Write the number as 2^48 61^48 + 2^48 2^440 3^122. Cancel 2^48 on each side and you're left with 61^48 + 2^440 3^122. At this point, there are many ways to get a 5th or 6th order poly. For a 5th order, multiply the entire expression by 61^2 and bring out 3^2 to get
61^50 + 61^2 3^2 2^440 3^120.

Now, this is 61^2 3^2 x^5 + 1 or 33489 x^5 + 1 where "m" = 2^88 3^24 / 61^10. Now the linear poly is x - "m". Multiply through by the denominator, 61^10, to get the linear poly 61^10 x - 2^88 3^24.

End result:
33489 x^5 + 1
61^10 x - 2^88 3^24

For 6th order, write it as 61^48 + 2^2 3^2 2^438 3^120. This gives you the 6th order poly 2^2 3^2 x^6 + 1, or
36 x^6 + 1, with linear poly
61^8 x - 2^73 3^20

Which is better to use? I dunno. The 5th order has much more balanced norms on each side, but the 6th order has a nicer algebraic polynomial. I'd probably just go with the 5th order rather than trying to find good fb limits for the 6th order, but if you use the 6th order poly, but sure to use a larger FB limit on the algebraic side than the rational side, and sieve on the algebraic side.

Greg

P.S. This is a LARGE SNFS factorization, with a difficulty of 191 digits. GNFS on a C126 will be easier than SNFS on a C191.

[akruppa]

Originally Posted by R.D. Silverman

A correction. GGNFS will not succeed "with certainty".

I know. Another possiblility if failing is that all dependencies yield trivial factorisations. Or, of course, a program bug, by far the most likely problem. I delibarately left out minute details.

Alex

[ECMFreak]

I put the 5th degree polynomial in a poly file for GGNFS, but it says:
"Evaluated polynomial value 1 is not a multiple of n"

My file:
n: 132792572098188981613964709257271592623835992300748703638238817966089759817515420905861971124060589852603298753562250830302293
c5: 33489
c4: 0
c3: 0
c2: 0
c1: 0
c0: 1
skew: 1
rlim: 800000
alim: 699999
lpbr: 25
lpba: 25
mfbr: 44
mfba: 44
rlambda: 2.2
alambda: 2.2
q0: 700000
qintsize: 50000