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: Another ECM question
Nathan Russell wrote: Is it (at least) theoretically possible that some larger factors are unfindable with ECM due to the limited number of sigma producable by George's random number generator? Nathan I dont think this is a problem. Limits in the RNG would only mean problems if it causes many sigmas to be duplicated and the chance of getting a fresh, yet untested sigma decreases substantially. The RNG in Prime95 produces up to 16-digit numbers, and if the number of curves you try stays well below the square root of the number of possible values the RNG produces, then the chance of a duplicate sigma is negligible. For Prime95, if you test less than 10^8 curves on one number, you're safe. If you have to test more than a hundred million curves, then ECM is not the proper algorithm for finding that particular factor, anyways. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Delayed startup
Hi, linux users should have no problem automatically starting mprime with a delay. Just stick sleep n in front of whatever command you use to start mprime; this will cause a delay of n seconds before mprime starts up. For Windows users (Win 9x/ME/NT/2000), I have written a small program which delays n seconds ( 0 n = 300 ) then runs an arbitary command. Download (18.6 KBytes) ftp://lettuce.edsc.ulst.ac.uk/gimps/software/DelayRun.zip unpack it move the executable to some folder mentioned in your execution path - C:\Windows\Command works on most Win 9x systems. Then change the command line (but nothing else) in the shortcut in the startup folder which causes Prime95 to run; precede the existing command with DelayRun n , (NB the quotes are not needed, but the spaces are!) where n is the number of seconds you want to elapse before Prime95 is started. DelayRun may be used to launch _any_ program after a suitable delay. It remains resident until the invoked command terminates, but will consume no resources. I'd prefer to avoid that, but the C library on my old version of Visual C++ seems to be broken the exec family of routines doesn't work as advertised. If it is invoked with a ridiculous delay interval or no command follows, DelayRun simply prints usage hints and exits. Note that the total maximum length of the command line is 127 characters. Apart from that, there should be no limitations on the use of the DelayRun program. I have placed the program in the public domain, waiving all intellectual property rights. I hope that DelayRun will be of some use to those requiring this facility pending the release of a version of Prime95 with a built-in startup delay option. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Wish: Add Time Stamps to Iteration display lines
Prime95 Wishlist: Add a time stamp to each line of Prime95's output. I've recently had a problem where another app was running away and using all the extra cycles and Prime95 didn't appear to getting ANY. Normally if things are busy the iteration time goes up; in my case since Prime wasn't getting any cycles it still showed the last iteration line but there wasn't any indication that that it was many minutes old. If the local 24 hour time stamp was also on every line I would be able to instantly see Prime wasn't running (well). Running Prime95 v20.6.1 under Win2000 on PIII 866Mhz. Cheers... Russ _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne Digest V1 #855
Mersenne Digest Monday, May 21 2001 Volume 01 : Number 855 -- Date: Sat, 19 May 2001 10:55:59 -0400 From: =?iso-8859-1?Q?Roger_Gari=E9py?= [EMAIL PROTECTED] Subject: Mersenne: Fw: numeric hazards of high performance CPU design = Pentium 4 - constant speed problem I came about this information on degrading calculations after about 10 minutes of usage. I think it can help explain stange behavour on your test of Prime 95 for P4. Don't be confuse by the web page title. - Roger Gariépy :-) - :-( [EMAIL PROTECTED] - - Original Message - From: validlab [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, May 17, 2001 5:20 PM Subject: numeric hazards of high performance CPU design http://www.inqst.com/articles/athlon4/0516main.htm _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Sat, 19 May 2001 08:38:53 -0700 From: Timothy Luders [EMAIL PROTECTED] Subject: Re: Mersenne: Different results Hello Mersenne, George woltman wrote: This suggestion is actually a high priority for the next release. The error is probably caused by some driver or program initialization that isn't saving the FPU state properly. The error is benign as you found out. I think the main advantage of this feature is it will lead to slightly faster boot times and thereby improve prime95's reputation of not interfering with your everyday work. Glad to see this. 99% of errors form my computer are at boot usually after a new program install. I try to remember to uncheck Windows95 service when installing anything but sometimes it slips by. Timothy Luders replying form the digest _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Sat, 19 May 2001 16:52:22 +0100 (BST) From: Chris Jefferson [EMAIL PROTECTED] Subject: Re: Mersenne: Fw: numeric hazards of high performance CPU design = Pentium 4 - constant speed problem I just felt I had to say, that I am very disturbed by this. The idea of my CPU simply shutting down when it overheats is a sensible idea. This is much more dodgy, espicaly as there doesn't seem to be any way of finding out, short of lots of benchmarks, if your processor is doing this... :-( It also raises problems for prime95, as it looks like running prime95 will reduce your PC's speed by half. I am going to recieve a pentium 4 shortly, and although I shall try to send it back for an AMD processor, if I can't I shall run tests with prime95. However if these figures are true then it won't be searching for primes :-( Chris - -- Chris Jefferson, Girton College, Cambridge, CB3 0JG - --- http://mrjeff.webjump.com Don't bother, it's not worth looking at. On Sat, 19 May 2001, Roger Gariépy wrote: I came about this information on degrading calculations after about 10 minutes of usage. I think it can help explain stange behavour on your test of Prime 95 for P4. Don't be confuse by the web page title. Roger Gariépy :-) - :-( [EMAIL PROTECTED] - Original Message - From: validlab [EMAIL PROTECTED] To: [EMAIL PROTECTED] Sent: Thursday, May 17, 2001 5:20 PM Subject: numeric hazards of high performance CPU design http://www.inqst.com/articles/athlon4/0516main.htm _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers -- Date: Sat, 19 May 2001 16:24:55 -0400 From: George Woltman [EMAIL PROTECTED] Subject: Re: Mersenne: Fw: numeric hazards of high performance CPU design = Pentium 4 - constant speed problem Hi, At 04:52 PM 5/19/2001 +0100, Chris Jefferson wrote: I just felt I had to say, that I am very disturbed by this. The idea of my CPU simply shutting down when it overheats is a sensible idea. This is much more dodgy, espicaly as there doesn't seem to be any way of finding out, short of lots of benchmarks, if your processor is doing this... :-( Although I've not run LL tests for extended periods of times, I have never noticed the CPU throttling down by half. Time will tell if this is a significant problem or will only be
