Mildly interesting 51-digit ECM factor
 

I guess the following was pretty lucky. Low B1 and factor found in first step.

HP[6]96 (that is, base-6 home prime of 96)

Input number is 89766675124873790501352404541149614109540609748271196339218551656401281081928576174053914349607659683071 (104 digits)
Using B1=3000000, B2=4016636513, polynomial Dickson(6), sigma=941728572
Step 1 took 23620ms **********
Factor found in step 1: 140853945410621700611366248656986006762214430713643
Found probable prime factor of 51 digits: 140853945410621700611366248656986006762214430713643
Probable prime cofactor 637303235370392019821924160023211640252124271118767997 has 54 digits

[QUOTE]I guess the following was pretty lucky.[/QUOTE]

You can say that again. I get for the probability that the group order of a curve modulo the p51 is 3e6-smooth something like 1 in 7.5 million. Play the lottery, quick!

Congrats!

Alex

[QUOTE=sean]
Found probable prime factor of 51 digits: 140853945410621700611366248656986006762214430713643[/QUOTE]

I'm not sure Paul Zimmermann keeps this list current, but it appears to be the 50th largest factor ever found by ECM, and hence eligible for listing until another one comes along. Of course a single not-yet-listed factor would push you off before you get on.

[url]http://www.loria.fr/%7Ezimmerma/records/top100.html[/url]

While we're on the topic of incredibly smooth group orders: I found this with P-1 today

251557613661918097 | 2^157429-1

The factorisation of p-1 is

2 2 2 2 3 3 13 29 31 43 71 311 157429

Since the 157429 in p-1 is known, the remaining part is 311-smooth.

Alex

And while we're still on that topic, I computed the group order of Sean's lucky curve. It's unbelievable:

2^2 3 5 137 251 317 331 7307 13339 15667 29209 137209 332933 393571 811351

alpha = log(p51)/log(811351) = 8.49

I don't think I've ever seen such a high alpha before. The p51 factor would have been found in stage 1 with B1=1M, the probability of a group order being that smooth is about 1 in 57M. Just amazing. Sean, report this to Richard Brent please!

Alex

Hello,

Would you have a source code, or a document who explains how is calculate the group order of a lucky curves?

A source code with GMP would be perfect for me.

Thank you in advance

Cordially

Alexis (Leo_01)

I don't have a stand-alone program for computing the group order, I use the Magma calculator at
[url]http://modular.fas.harvard.edu/calc/[/url]
with a program like this:

[CODE]
FindGroupOrder2 := function (p, s)
K := GF(p);
v := K ! (4*s);
u := K ! (s^2-5);
x := u^3;
b := 4*x*v;
a := (v-u)^3*(3*u+v);
A := a/b-2;
x := x/v^3;
b := x^3 + A*x^2 + x;
E := EllipticCurve([0,b*A,0,b^2,0]);
return FactoredOrder(E);
end function;

p := 140853945410621700611366248656986006762214430713643;
s := 941728572;
FindGroupOrder2(p, s);
[/CODE]

Alex

Can that be converted into Pari/GP-speak please?
Here's what Pari/GP offers w.r.t. ECs:

? ?5

elladd ellak ellan ellap
ellbil ellchangecurve ellchangepoint elleisnum
elleta ellglobalred ellheight ellheightmatrix
ellinit ellisoncurve ellj elllocalred
elllseries ellminimalmodel ellorder ellordinate
ellpointtoz ellpow ellrootno ellsigma
ellsub elltaniyama elltors ellwp
ellzeta ellztopoint

? ?ellorder
ellorder(e,p): order of the point p on the elliptic curve e over Q, 0 if
non-torsion.

? ?ellinit
ellinit(x,{flag=0}): x being the vector [a1,a2,a3,a4,a6], gives the vector:
[a1,a2,a3,a4,a6,b2,b4,b6,b8,c4,c6,delta,j,[e1,e2,e3],w1,w2,eta1,eta2,area]. If
the curve is defined over a p-adic field, the last six components are replaced
by root,u^2,u,q,w,0. If optional flag is 1, omit them altogether.

[QUOTE=fatphil, emphasis added]Can that be converted into Pari/GP-speak please?
Here's what Pari/GP offers w.r.t. ECs:


? ?ellorder
ellorder(e,p): order of the point p on the elliptic curve e [B]over Q[/B], 0 if
non-torsion.
[/QUOTE]

I think that's the problem, afaik Pari does not yet include point counting algorithms for cubics over finite fields.

Alex

[QUOTE=akruppa]I think that's the problem, afaik Pari does not yet include point counting algorithms for cubics over finite fields.[/QUOTE]

So it's a simple matter of binary chopping the 'exponent'.
And that's a SMoP. Hoorah!

Hmmmm, actaully, that raises a followup question -
Is it possible for GMP-ECM (or similar) to output the 'B2' prime factor of the point order? If it could, then would that make the actual order easier to compute? (I know that if I were to do a simple 2-stage P+/-1/ECM, then I'd be able to tell you which prime in the B2 range actually found the factor, for instance, but don't know if GMP-ECM's operation is in any way similar to my naive implementation.)

The development version outputs the largest prime factor of the point's order if the factor was found in stage 1. For factors found in stage 2 things are more tricky, due to the "polynomial multipoint evalutation" stage 2 in GMP-ECM (see Montgomery's PhD thesis). Hmm, then again, it should not be hard to go through the list of [tex](F(x)\cdot X)_x[/tex] and see which [I]x[/I] found the factor... maybe do a search of the the roots of [I]F[/I] then... we'll see.

Alex