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

- Mersenne: ECM Question... Eric Hahn
- Re: Mersenne: ECM Question... Alexander Kruppa
- Re: Mersenne: ECM Question... Steve Phipps
- Re: Mersenne: ECM Question... Alexander Kruppa
- Re: Mersenne: ECM Question... Alexander Kruppa