Faking factors with Complex Multiplication

[ATH]

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.

[alpertron]

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:

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!

[akruppa]

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

[akruppa]

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

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

[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.

[akruppa]

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

[R.D. Silverman]

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.

[alpertron]

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.

[R.D. Silverman]

Originally Posted by alpertron

... using only one computer. That's a real challenge.

And that's a real understatement!!!!

[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?

[bdodson]

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)