mersenneforum.org Faking factors with Complex Multiplication
 Register FAQ Search Today's Posts Mark Forums Read

2006-11-30, 12:01   #1
ATH
Einyen

Dec 2003
Denmark

19·181 Posts

Quote:
 Since we don't know which sigma values are going to be lucky in finding factors (because we don't know what the factors are!), implementations of ECM select the sigma value at random.
If a factor is known can the sigma be calculated that will produce that factor? Not much use, I'm just curious if that is how it works.

2006-11-30, 12:29   #2
alpertron

Aug 2002
Buenos Aires, Argentina

149710 Posts

Quote:
 Originally Posted by ATH If a factor is known can the sigma be calculated that will produce that factor? Not much use, I'm just curious if that is how it works.
I read that it is possible. But if you can also select the number to factor, you can make ECM find huge factors. Quoting from Richard Brent's Web site:

Quote:
 Originally Posted by http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt I reserve the right to exclude factorizations that were possibly obtained by "artificial" means. See for example Research Problem 7.27 of the book "Prime Numbers: a Computational Perspective" by Crandall and Pomerance. David Broadhurst has shown that this enables us to concoct examples where ECM finds factors of over 30,000 decimal digits!

Last fiddled with by alpertron on 2006-11-30 at 12:30

 2006-11-30, 12:34 #3 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts For a given prime p, you can construct a curve of any order in the Hasse interval around p by a technique called Complex Multiplication. That is, I think to construct any valid order you may need to define the curve over an algebraic closure of GF(p), I'm not sure. Afaik, "usually" it works over GP(p) as well. This will give you the curve parameters, i.e. for a curve in Weierstraß form, the a and b parameters. Curves in Montgomery parameterisation are a subset of the curves in Weierstraß form, so not every curve generated by Complex Multiplicaion may be suitable for converting to Montgomery form. Furthermore, generating a curve in Montgomery form from the sigma value is not a bijective function either, so even for a valid curve in Montgomery form there may not be a suitable sigma value. If there is, the sigma value will be very large, more or less a random value (mod p). I think David Broadhurst did some experimenting with producing "fake" ECM sucesses by constructing curves with Complex Multiplication. Iirc, he managed to make ECM "find" factors >1000 digits that way, but usually the size of the sigma value gave them away, as the random number generator we use in GMP-ECM chooses sigma <2^32. Alex
2006-11-30, 12:50   #4
akruppa

"Nancy"
Aug 2002
Alexandria

46438 Posts

Here is a posting of David Broadhurst to the NMBRTHRY mailing list on the subject:

Quote:
 Originally Posted by David Broadhurst on NMBRTHRY Richard Brent asked me if I could contrive to make GMP-ECM extract a large prime factor, for example p > 1074, with a much smaller seed, for example sigma < 232. Construction [CM with squares in order]: Let f(x) = (8*(x-5)4 + (x-1)2*(x-25)2)/211 g(x) = (x-1)2*(8*(x-9)2 + (x-25)2)/211 If sigma is odd and p = f(sigma2) is prime, then the curve of Crandall and Pomerance Theorem 7.4.3 has complex multiplication with discriminant D = -8 and order #E(F_p) = g(sigma2). GMP-ECM, when run with limits B1 and B2, will factorize a composite input divisible by p if #E(F_p) is of the form C*q where no prime power in C exceeds B1 and q is an outlying prime that does not exceed B2. Amusingly, extraction of p > 1074, with sigma < 232, can now be accomplished when the order contains both B12 and B22: http://lists.fousse.info/pipermail/e...er/000388.html Note that the construction allows us to "forge" a GMP-ECM factorization that appears to be a "champ" (as defined by Richard Brent) but is in fact a "chimp" (a term coined by Bouk de Water) that may be found by demanding smoothness of 8*(sigma2-32)2 + (sigma2-52)2 \approx 96*sqrt(2*p) and primality of p = f(sigma2). For example, the seed sigma = 4278674929 will factorize c175 = p75*p101 = f(sigma2)*(2333+285) in 5 seconds: Using B1=128657, B2=53194859, polynomial x2, sigma=4278674929 Step 1 took 3000ms Step 2 took 1720ms Found probable prime factor of 75 digits: 493613348917766417426006591803225943649556875046256846631045789294232301761 For extraction of a p74 without a large square in the order, see http://lists.fousse.info/pipermail/e...er/000380.html which exploits complex multiplication with D = -3 for a prime p dividing the numerator of 3*(u3+u)2 - (3*u2-1)2, with u = (sigma2-5)/(4*sigma) and sigma = 9344229. The Cornacchia-Smith algorithm then gives #E(F_p) = 26*33*37*397*601*787*25183*68881*1257463*2020663*113756239 *176982499*496654231*33145894274179 and GMP-ECM factors p74*p89 in 8 hours. Of course, these games pale into insignificance when compared with the amazing true "champs" in http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt I thank Richard Brent, Alex Kruppa, Bouk de Water and Paul Zimmermann for their encouragement. David Broadhurst
Alex

Last fiddled with by akruppa on 2006-11-30 at 12:53 Reason: Moved to separate thread, CM isn't a beginners question at all!

 2006-11-30, 23:10 #5 retina Undefined     "The unspeakable one" Jun 2006 My evil lair 668610 Posts I see no reason why this can't also be a challenge for people to "make" the largest factors using a small sigma. As long a people don't try to misrepresent the result as "real" factors then it could be fun to try generating huge factors. We might even learn something of mathematically interesting in the process.
 2006-12-01, 15:44 #6 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts I don't see much of a challenge here... David showed that it is possible to fake record ECM factors that are indistinguishable from the real thing. What would even larger fakes prove? CM is greatly refined and studied in detail for Elliptic Curve Primality Proving, and imho that's where it makes sense to invest the effort. Alex
2006-12-01, 16:02   #7
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

165248 Posts

Quote:
 Originally Posted by retina I see no reason why this can't also be a challenge for people to "make" the largest factors using a small sigma. As long a people don't try to misrepresent the result as "real" factors then it could be fun to try generating huge factors. We might even learn something of mathematically interesting in the process.
I doubt it. Here is (IMO) a better challenge:

Be the first to find a 70 digit factor of a Cunningham number via ECM.

2006-12-01, 19:58   #8
alpertron

Aug 2002
Buenos Aires, Argentina

27318 Posts

Quote:
 Originally Posted by R.D. Silverman I doubt it. Here is (IMO) a better challenge: Be the first to find a 70 digit factor of a Cunningham number via ECM.
... using only one computer. That's a real challenge.

2006-12-01, 20:11   #9
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

22×1,877 Posts

Quote:
 Originally Posted by alpertron ... using only one computer. That's a real challenge.

And that's a real understatement!!!!

 2006-12-01, 20:15 #10 alpertron     Aug 2002 Buenos Aires, Argentina 101110110012 Posts If I instruct one thousand computers with multiple cores to run random curves in all remaining Cunningham numbers, one of them will eventually find the 70-digit or larger factor. Where is the merit?
2006-12-02, 06:33   #11
bdodson

Jun 2005
lehigh.edu

210 Posts
wondering, too

Quote:
 Originally Posted by alpertron If I instruct one thousand computers with multiple cores to run random curves in all remaining Cunningham numbers, one of them will eventually find the 70-digit or larger factor. Where is the merit?
Uhm, let's count. C. 750 fast xps, 110 Opterons, 90 old P3's comes to
950, but that's including dual cpus, counted as 2; 50 short and no
multiple cores. Not counting 30 xeons and macs running NFSNET. For
one thing, the scheduling software running the xps --- U Wisc's condor --
clearly isn't quite up to the task yet; we're hoping the new core due
over the semester break is more robust. I can assure you that it isn't
a case of submitting the number of expected curves and waiting!

For one, the gmp-ecm-6.1 README doesn't even go up to 70; stops
at 65-digits. Same for Alex's -v. The old gmp-ecm-5.0 gives the optimal
b1 = 2,700,000,000 for p70 (with 850M for p65), and (with a smaller
default b2 than 6.1 would use), 120,000 curves. So the first problem
you'll have is that these type of commodity chips don't come with enough
memory to run even 850M, much less 2700M. I have 250Mb on the P3s
and c. 300 of the xps; 500Mb on the other 450 xp; 1Gb/cpu on the
Opterons. That gets me to 250-digits with b1 = 260M (p60-optimal) on
the Opterons; and b1=43M on the xps and P3s. Our expensive machine
has 128Gb for 32 Itanium2's, so just 4Gb/cpu --- I tried 850M there for
a while, with step1 on the (faster) Opterons, to best use the expensive
memory in step 2's. Just on c175-c185 to get more curves. Too labor
intensive. Looks like 15K curves, all told.

So that's probably a second point; you'd do better dropping the c251-c366's
anyway, something like 1/3 of the 850 on the current list. If you're going to
find a p70, you'd want to have it meet Brent's restriction, so that means
droping numbers under c150, or so (hardly any of them anyway, headed
towards 2*t50 soon). But it's worse than that, if you found a p70 in
a c170, someone would likely point out that you'd have done better using
gnfs; so probably you'd do better staying in the range c200-c250. Uhm,
well, I'm just finishing a run on c195-c233, something like 230 numbers out
of the 850. No p7x's yet. Looks like 300K curves with b1=260M (p60
optimal). Supposed to be enough for a p65; found a p67.

Next problem is that -- if you're spending this amount of cputime -- you
most likely would want to make sure to get something for the effort.
Grinding on the above 230-numbers might make best sense for an ecm
p7x, but there are still p4x's left in c250-c366 --- Brent's claim was/is
that one might justify at most 10% of an ecm effort on looking for
champion factors (viz his p40 from F10). I found myself rather annoyed
that people were running snfs and finding p47; and am somewhat happier
that small factors these days have been p52-p54, instead of p4x's. So
that argues for time on numbers that aren't in what I'd consider best
p7x range.

bdodson (ecm records: p57, p59, p66 and p67, so far)

 Similar Threads Thread Thread Starter Forum Replies Last Post bhelmes Math 0 2018-03-04 18:50 Nick Number Theory Discussion Group 8 2016-12-07 01:16 wildrabbitt Math 3 2016-08-16 08:38 halcion Software 6 2004-12-16 20:10 dave_0273 Math 3 2004-11-08 17:15

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

Tue Feb 7 22:21:29 UTC 2023 up 173 days, 19:50, 1 user, load averages: 1.26, 1.23, 1.19