Steve Phipps wrote:
>
> While we're on the subject, can someone explain how to derive the group
> order for factors found using ECM? I've been carrying out ECM on an old PC
> for almost a year now, and I'd like to be able to derive, and factorise,
> the group orders for the factors that I've found.
>
> I've been making an effort to understand the maths, and I'm getting there
> slowly, but I've found nothing yet that explains how to derive the group
> orders. If my understanding is correct, you would need to know the
> equations used by mprime to derive the co-ordinates of the starting point
> for each curve.
>
> Anyway, if someone could explain how to derive the group order, or point
> me in the right direction, I'd be very grateful.
>
> Regards,
> Steve
I'm by no means an expert on ECM, but let me try..
There seems to be a formula to compute the order of an elliptic curve
over Z/p*Z, p prime, but that formula is afaik rather complicated to
compute.
What you can do when you want the order of a successful ECM curve is
this:
p is the factor of N that was found by the curve, go_p is the order of
the curve and go_p(x) is the order of x in that curve.
If a!=0 but a*q=0, q prime, then q is the group order of a and a factor
of the order of the group. (0 is the neutral element here).
You can run the sucessful ECM curve normally, but test for a factor
after every multiplication with a prime q and see if the factor p is now
found - if so, then q is a factor of the group order. Remember the q's
and restart the curve, but multipliying the initial point x with all the
q's to find smaller factors of the group order.
A very informal algorithm might look like this:
known_go = 1
restart:
set x to the initial point
x = x*known_go
if gcd(x_z, N) > 1 print known_go, exit
for all primes and prime powers q below bound B
x = x * q
if gcd(x_z, N) > 1 then known_go *= q, goto restart
This will reveal the order of the initial point x. But we want the order
of the group (go_p), not that of x (go_p(x)). However we know that that
gp_p(x) | go_p, and p+1-sqrt(p) <= go_p <= p+1+sqrt(p) . Since go_p(x)
is usually much larger than 2*sqrt(p), the second equation has only one
solution in integer k if you replace go_p by k*go_p(x). Find the correct
k, i.e. by trunc((p+1+sqrt(p)) / go_p(x)), and k*go_p(x) is the group
order you wanted.
I once tried this with the mprime ecm code and actually were able to
verify the known group orders of some factors, but I never really
cleaned up and debugged the code - for example, you cant stop and
restart the go run, and after the run all the internal variables are
probably not restored cleanly enough to continue with regular curves,
etc. If there is interest in this code, I'll try to clean it up enough
to make it more or less suitable for public display - provided George
has no objection to spreading a modified version of his code.
Ciao,
Alex.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
