Re: Mersenne: ECM Question...
Alexander Kruppa wrote: gp_p(x) | go_p, and p+1-sqrt(p) = go_p = p+1+sqrt(p) . Since go_p(x) Correction: I have taken the limits above from my memory which has once again proved itself untrustworthy. The correct limits are p+1-2*sqrt(p) go_p = p+1+2*sqrt(p) , a theorem by Haase, which I found in O. Forster, Algorithmische Zahlentheorie. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Question...
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
Re: Mersenne: ECM Question...
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 If the sigma is the same, then a curve with B1=25 will find any factor that a curve with B1=5 finds. When you run 700 random curves at B1=25, you might theoretically miss a factor that someone else finds with B1=5, if he gets a lucky sigma so that the group order is very smooth. But in general, using the same number of curves, the higher bound should find all the factors that the lower bound can find. But dont be tempted into running only a few curves at very high bounds. The strength of ECM is that you can try curves with different group orders until a sufficiently smooth one comes along. So skipping bound levels is usually not a good idea unless you have reason to believe the the number unter attack has only large factors which call for a higher bound. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Question...
Eric Hahn wrote: If a person runs an ECM test using a B1 of 250,000 with 700 curves (for up to 30 digits), will they also find any factors that they would have found if they had used a B1 of 50,000 with 300 curves (for up to 25 digits) ?!? Eric If the sigma is the same, then a curve with B1=25 will find any factor that a curve with B1=5 finds. When you run 700 random curves at B1=25, you might theoretically miss a factor that someone else finds with B1=5, if he gets a lucky sigma so that the group order is very smooth. But in general, using the same number of curves, the higher bound should find all the factors that the lower bound can find. But dont be tempted into running only a few curves at very high bounds. The strength of ECM is that you can try curves with different group orders until a sufficiently smooth one comes along. So skipping bound levels is usually not a good idea unless you have reason to believe the the number unter attack has only large factors which call for a higher bound. 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...
I think I know the answer to this question, but am asking it... just to make sure... According to ECMNet, to find factors of up to 25 digits, the optimal B1 is 50,000 with 300 expected curves... and to find factors of up to 30 digits the optimal B1 is 250,000 with 700 expected curves... If a person runs an ECM test using a B1 of 250,000 with 700 curves (for up to 30 digits), will they also find any factors that they would have found if they had used a B1 of 50,000 with 300 curves (for up to 25 digits) ?!? Eric I'm presuming the answer is yes... and it works the same for each level... (1,000,000 with 1800 expected curves for up to 35 digits, etc.)... _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM question
Hi all, I have a different question concerning P-1 and ECM. Some time ago I asked which power to put small primes into when multiplying them into E ( factor = gcd(a^E-1,N) ). Paul Leyland, I believe, replied that the power for prime p should be trunc( ln(B1) / ln(p) ) ( log(B1) with base p ), where B1 is the bound up to which we put primes into E. But what if there is a stage 2 with a higher bound B2? Should it be trunc( ln(B2) / ln(p) ) then? Or still the stage 1 bound? In his Diplomarbeit about ECM ( see ftp://ftp.informatik.tu-darmstadt.de/pub/TI/reports/berger.diplom.ps.gz ), Franz-Dieter Berger mentiones on page 40f that his experience shows that it is better to use the stage 2 bound. Any opinion from the factoring gurus here on the list? Ciao, Alex. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
RE: Mersenne: ECM question
The function being minimized, namely probability of finding a 50-digit factor on one curve - time per curve is flat near its minimum. Implementation and platform differences can obviously affect the denominator (time per curve). The stage-2 strategy affects the numerator. The two optimal B1's are close enough to be considered the same. Umm. I think you want to maximize the probability. Minimizing it is easy. Paul Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
RE: Mersenne: ECM question
At Paul Zimmerman's ECM page, http://www.loria.fr/~zimmerma/records/ecmnet.html the optimal B1 value listed for finding 50-digit factors is 4300, but George's ECM factoring page uses 4400 for the same purpose. Is one of them wrong, or is there a reason for the difference? No, neither is "wrong", for at least two reasons. First, ECM is a probabalistic algorithm. Each run chooses a random elliptic curve and has a certain chance to find a factor of a particular size. When enough curves have been run, there is particular probability of finding a factor of that size, assuming that one exists. If one choose 50% as the desired probability, the number of curves required will obviously be fewer than if one chooses 60%, say. A similar choice can be made for trading off B1 value against probability, as long as the trade isn't pushed too far. Another reason is that the B1 value is only one quantity of importance. Even if the probability mentioned above is fixed, the optimal number of curves depends on the value of B2. Different implementations of ECM (or even different runs of the same implementation) are free to choose different values of B2 for a given B1. A non-reason, but still of interest, is that the maximum in the probability agains B1 curve is really rather flat, and it doesn't matter too much if parameters are chosen which are not strictly optimum. Paul Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: ECM question
At Paul Zimmerman's ECM page, http://www.loria.fr/~zimmerma/records/ecmnet.html the optimal B1 value listed for finding 50-digit factors is 4300, but George's ECM factoring page uses 4400 for the same purpose. Is one of them wrong, or is there a reason for the difference? ___ Get Free Email and Do More On The Web. Visit http://www.msn.com Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
