mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-07-17, 14:23   #1
ECMFreak
 
Jul 2007

68 Posts
Post Usage of GMP-ECM

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
ECMFreak is offline   Reply With Quote
Old 2007-07-17, 14:50   #2
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-07-17, 15:20   #3
ECMFreak
 
Jul 2007

2×3 Posts
Default

Thanks, I will first compile the new version!
ECMFreak is offline   Reply With Quote
Old 2007-07-17, 16:12   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

186416 Posts
Default

You might also want to consider ECMNet, even if it is only one number (or a small set of numbers).
rogue is offline   Reply With Quote
Old 2007-07-18, 15:33   #5
ECMFreak
 
Jul 2007

2×3 Posts
Default

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
ECMFreak is offline   Reply With Quote
Old 2007-07-18, 15:59   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2007-07-18, 16:04   #7
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

164448 Posts
Default

Quote:
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.

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.
R.D. Silverman is offline   Reply With Quote
Old 2007-07-18, 16:52   #8
ECMFreak
 
Jul 2007

2×3 Posts
Default

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

Last fiddled with by ECMFreak on 2007-07-18 at 16:54
ECMFreak is offline   Reply With Quote
Old 2007-07-18, 17:19   #9
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22·11·47 Posts
Default

Quote:
Originally Posted by ECMFreak View Post
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.

Last fiddled with by frmky on 2007-07-18 at 17:29
frmky is offline   Reply With Quote
Old 2007-07-18, 17:45   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
akruppa is offline   Reply With Quote
Old 2007-07-19, 13:38   #11
ECMFreak
 
Jul 2007

2×3 Posts
Default

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
ECMFreak is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Low CPU/GPU usage? GeoffreyY Msieve 23 2017-02-17 18:01
GPU Usage Brain GPU Computing 9 2011-04-12 22:25
GMP-ECM resource usage lavalamp Software 0 2010-10-11 20:46
High CPU usage Primix Hardware 2 2008-07-20 23:44
CPU usage Unregistered Software 6 2003-11-19 07:05

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

Mon Mar 1 05:11:07 UTC 2021 up 88 days, 1:22, 0 users, load averages: 2.92, 2.54, 2.12

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