Richard Brent asked me if I could contrive to make GMP-ECM
extract a large prime factor, for example p > 10^74,
with a much smaller seed, for example sigma < 2^32.

Construction [CM with squares in order]: Let
f(x) = (8*(x-5)^4 + (x-1)^2*(x-25)^2)/2^11
g(x) = (x-1)^2*(8*(x-9)^2 + (x-25)^2)/2^11
If sigma is odd and p = f(sigma^2) 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(sigma^2).

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 > 10^74, with sigma < 2^32, can now
be accomplished when the order contains both B1^2 and B2^2:
http://lists.fousse.info/pipermail/ecm-dev/2005-September/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*(sigma^2-3^2)^2 + (sigma^2-5^2)^2 \approx 96*sqrt(2*p)
and primality of p = f(sigma^2).

For example, the seed sigma = 4278674929 will factorize
c175 = p75*p101 = f(sigma^2)*(2^333+285) in 5 seconds:

Using B1=128657, B2=53194859, polynomial x^2, 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/ecm-dev/2005-September/000380.html
which exploits complex multiplication with D = -3 for a prime p dividing
the numerator of 3*(u^3+u)^2 - (3*u^2-1)^2, with u = (sigma^2-5)/(4*sigma)
and sigma = 9344229. The Cornacchia-Smith algorithm then gives
#E(F_p) = 2^6*3^3*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