Re: Mersenne: ECM
On Saturday 01 February 2003 07:53, Eric Hahn wrote: Let's say you've done 700 curves with B1=25,000 to find a factor up to 30-digits... and you've been unsuccessful... :-( Now you've decided to try 1800 curves with B1=1,000,000 to try and find a factor up to 35-digits. Do you have to start from scratch... or can you somehow use the information from attempting to find a factor up to 30-digits... to save some time and energy... and speed up the search process at the same time??? Effectively every curve is starting from scratch. The only way I can think of using information from previous unsuccessful curves is that it's probably a Bad Idea to use the same s-value (well, it's a complete waste of time if the limits are not increased). The point here is that the chance of picking a previously-used s-value is infinitesimal, providing the random number generator on the system is reasonably behaved. Regards Brian Beesley _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: ECM
Not knowing a whole lot about ECM... I thought I'd ask this question... and maybe put out a new topic to discuss... ;-) Let's say you've done 700 curves with B1=25,000 to find a factor up to 30-digits... and you've been unsuccessful... :-( Now you've decided to try 1800 curves with B1=1,000,000 to try and find a factor up to 35-digits. Do you have to start from scratch... or can you somehow use the information from attempting to find a factor up to 30-digits... to save some time and energy... and speed up the search process at the same time??? Eric... (finder of over 150,000 factors (and climbing)) _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: ECM on Fermat factoring
Hello, everyone! I sent a letter to this list about a month ago indicating that Fermat number factoring by the Elliptic Curve Method could be done more efficiently by running curves on numbers of the form 2^(2^n) - 1 (M-numbers) instead of running on the Fermat numbers themselves of the form 2^(2^n) + 1 (P-numbers). I was finding increases in efficiency of 3% to 15% on Athlon and Pentium III computers, mainly because of a wider choice of FFT sizes available to Prime95 on M-numbers than on P-numbers. George Woltman has pointed out that the increase in efficiency on Pentium IV computers is even more dramatic, largely because the FFT code for M-numbers incorporates use of the Pentium-IV specific SSE2 instructions, whereas the code for P-numbers does not use this feature. As an example, I ran curves to B1=44,000,000 on several exponents on a 1900 MHz Pentium IV and came up with the following timings: P4096 (Fermat-12) : 3 hours, 39 minutes P8192 (Fermat-13): 6 hours, 58 minutes P16384 (Fermat-14): 16 hours, 51 minutes total time for these three curves: 27 hours, 28 minutes Then I ran a single curve on M32768 = 2^32768 - 1. This number is the product of all the Fermat numbers from F0 to F14, and I included all known factors 60 digits of these Fermat numbers in the lowm.txt file. (Of course F0 through F11 are already completely factored.) The result: M32768: 10 hours, 16 minutes Quite a dramatic increase in speed! George has now added the factors of these M-numbers to the lowm.txt file, and has included a note about their use on: http://www.mersenne.org/ecmf.htm The combination of a fast Pentium IV with this SSE2 code makes this 1900 MHz Pentium approximately 10 times as fast as the 400 MHz Pentium II's I was using a year-and-a-half ago! Good luck, anyone who wants to try this. Phil Moore _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: ECM
I think I know the answer to this... but want to double-check to be sure... While doing factoring... using ECM... factors up to: 15 digits is the equivalent of ~2^50... 20 digits is the equivalent of ~2^67... 25 digits is the equivalent of ~2^83... 30 digits is the equivalent of ~2^100... If trial-factoring has been done up to 2^68... is it possible to skip testing ECM curves for factors up to 15 and/or 20 digits... and go straight to testing ECM curves for digits up to 25 digits??? Makes sense to me, as long as you realise that the estimates for ECM factoring are just that, only estimates. Sometimes you get lucky and find a big factor with a small number of curves at a small B1 and sometimes you get unlucky and miss a small factor after a lot of effort. Personally, I would go straight in at the 25+ digits level. Paul _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: ECM
If trial-factoring has been done up to 2^68... is it possible to skip testing ECM curves for factors up to 15 and/or 20 digits... and go straight to testing ECM curves for digits up to 25 digits??? Personally, I would go straight in at the 25+ digits level. OTOH, if trial factoring has been done to 2^68 on a Mersenne number then the number is probably quite big (IIRC) so it will take a long time to run just a single curve with a big B1. Sander _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: ECM
If trial-factoring has been done up to 2^68... is it possible to skip testing ECM curves for factors up to 15 and/or 20 digits... and go straight to testing ECM curves for digits up to 25 digits??? Personally, I would go straight in at the 25+ digits level. OTOH, if trial factoring has been done to 2^68 on a Mersenne number then the number is probably quite big (IIRC) so it will take a long time to run just a single curve with a big B1. Sure, but which would you rather do: run a 10-hour program once with a 1/1000 chance of finding a factor, or run a 1-hour program 10 times which has a total 1/1100 chance of finding a factor? Don't take the figures literally, but they are illustrative of the sorts of choices that have to be made. In the end you place your bets and you take your chance. Paul _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: ECM
OK... I think I know the answer to this... but want to double-check to be sure... While doing factoring... using ECM... factors up to: 15 digits is the equivalent of ~2^50... 20 digits is the equivalent of ~2^67... 25 digits is the equivalent of ~2^83... 30 digits is the equivalent of ~2^100... If trial-factoring has been done up to 2^68... is it possible to skip testing ECM curves for factors up to 15 and/or 20 digits... and go straight to testing ECM curves for digits up to 25 digits??? Eric _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
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 memory usage
I've been carrying out ECM for some time now on small exponents (under 40,000) and I'm curious about the amount of memory that it uses. According to readme.txt, the minimum memory required is 192 times the FFT size. For the exponents I'm looking at, I suspect that the FFT size is of order a kilobyte (BTW, can I look the FFT sizes and breakpoints up somewhere?) and so the minimum memory required is less than 1MB. However, I use mprime with the available memory set to 24MB and I've noticed that ECM uses almost all of this. I'd like to know why ECM is using so much memory - does it enable it to run faster? And how much memory would ECM 'like' to use if it was available? Regards, Steve _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM memory usage
Hi, At 10:08 AM 3/29/2001 +1000, Steve Phipps wrote: For the exponents I'm looking at, I suspect that the FFT size is of order a kilobyte (BTW, can I look the FFT sizes and breakpoints up somewhere?) and so the minimum memory required is less than 1MB. A size 1024 FFT can handle exponents up to 22599. For rough estimating purposes, divide the exponent by 21 and round up to the next FFT size. However, I use mprime with the available memory set to 24MB and I've noticed that ECM uses almost all of this. I'd like to know why ECM is using so much memory - does it enable it to run faster? Yes, more memory can be used to save some operations. And how much memory would ECM 'like' to use if it was available? I've never studied this. I suspect you quickly reach the point of diminishing returns. Try mprime with 8MB and I'll bet you'll notice little difference. Regards, George _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: ECM update -- M727 finished up to 50 digits
The last machine that I had working on M727 has finished its 1000 curves at B1=44M. This is enough to finish the recommended number of curves at that bound. Thus there are probably no factors below 10^50, and it won't be practical to find the factors with ECM. Have any other numbers received as much ECM effort as this? I'm betting that there aren't many. David A. Miller [EMAIL PROTECTED] _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: ECM better than O(sqrt(f)) ?
I've read on the list some time ago that ECM takes, like Pollard-Rho or P-1, O(sqrt(f)) operations mod N to find a factor f. But looking at the factors found so far I find that hard to believe; according to that formula, finding a 50-digit factor should be 10^15 times harder than finding a 20-digit factor. Even if a 20-digit could be found in 1 sec. average, the 50-digit would take some 30 million years - I dont believe this much time has been spent on ECM worldwide already. Is ECM better than O(sqrt(f)) ? Are there any more accurate lower bounds, or even a \Theta(g(f)) ? Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
RE: Mersenne: ECM better than O(sqrt(f)) ?
I've read on the list some time ago that ECM takes, like Pollard-Rho or P-1, O(sqrt(f)) operations mod N to find a factor f. But looking at the factors found so far I find that hard to believe; according to that And quite right too. It's just plain wrong. ECM runs in sub-exponential time. formula, finding a 50-digit factor should be 10^15 times harder than finding a 20-digit factor. Even if a 20-digit could be found in 1 sec. average, the 50-digit would take some 30 million years - I dont believe this much time has been spent on ECM worldwide already. Is ECM better than O(sqrt(f)) ? Are there any more accurate lower bounds, or even a \Theta(g(f)) ? The expected number of arithmetic operations taken to find a prime factor p is asymptotic to exp(sqrt(log p log log p)) and so is, in some handwaving manner, halfway between polynomial and exponential. Of course, as N gets larger the cost of each operation gets larger, but at a strictly polynomial rate for any sane implementation of multiple precision arithmetic. Paul p.s. I found a 50-digit factor by ECM recently 8-) _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.exu.ilstu.edu/mersenne/faq-mers.txt
Mersenne: ECM time needed?
How long will each ECM curve on M727 take? I'd like to run a few in May, when I'm done with my current work, but don't know how many to set up. To put it another way, how many curves will take about a week on a p3-600 running 16/7? I checked the various FAQs, but couldn't find this information anywhere. Thanks, Nathan Russell, unofficial GIMPS pet newbie :-) __ Get Your Private, Free Email at http://www.hotmail.com _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: ECM Factoring
Hi, I need some help. I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. You can also edit the worktodo.ini file directly. For example: ECM=751,300,0,100,0,0,0,24 The first value is the exponent. The second value is bound #1. The third value is bound #2 - leave it as zero. The fourth value is the number of curves to test. The fifth value is the number of curves completed. The sixth value is the specific curve to test - it is only used in debugging. The seventh value is 0 for 2^N-1 factoring, 1 for 2^N+1 factoring. The eighth value is the MB of memory the program should use. I don't understand how to set the ECM= paramaters to accomplish my goal. It is my understanding that one can use ECM or 2^p-1 factoring with V19. Any help would be appreciated. Thanks Dan _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. For this targeted a test, you might want to use trial factoring simply edit to worktodo.ini file adding the following line Factor=a,b Where a is the mersenne exponent, and 2^b is the limit trial factored to. you can override the default trial factoring depth with the line FactorOveride=n where n is the power of 2 that you want it to stop at. (I think that is how it is spelled, see undoc.txt) (a rather ironic title in my opinion) I don't understand how to set the ECM= paramaters to accomplish my goal. It is my understanding that one can use ECM or 2^p-1 factoring with V19. (I think you mean P-1 factoring). Yes, but ECM wouldn't be best for such a targeted search (as I understand it). -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM Factoring
When this is cleared up, it will make a good FAQ. Who maintains the FAQ list? Do you agree the answer here is a good FAQ? At 01:10 PM 10/2/99 -0700, you wrote: Hi, I need some help. I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. You can also edit the worktodo.ini file directly. For example: ECM=751,300,0,100,0,0,0,24 The first value is the exponent. The second value is bound #1. The third value is bound #2 - leave it as zero. The fourth value is the number of curves to test. The fifth value is the number of curves completed. The sixth value is the specific curve to test - it is only used in debugging. The seventh value is 0 for 2^N-1 factoring, 1 for 2^N+1 factoring. The eighth value is the MB of memory the program should use. I don't understand how to set the ECM= paramaters to accomplish my goal. It is my understanding that one can use ECM or 2^p-1 factoring with V19. Any help would be appreciated. Thanks Dan _ 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
Re: Mersenne: ECM Factoring
When this is cleared up, it will make a good FAQ. Who maintains the FAQ list? Do you agree the answer here is a good FAQ? I would like to look for a factor of a mersenne prime in a specific area. For example, for a mersenne exponent of say 40,000,000. I want to use the Prime95b program, (v19 I guess), to search for a factor in a specific range from, say, 2^40 to 2^50. I do not understand the ECM factoring instuctions included with Prime95. I maintain the FAQ (well, one of three anyway). There is my FAQ which deals mostly with the math involved with Mersenne numbers. There is Scott's FAQ which deals with primenet, and there is George's FAQ which deals with Prime95. I have gotten questions involving all three (and at least 2 letters which assert mine as the "best"). I like the current separation for a number of reasons: (1) It makes sense (2) I know next to nothing about Prime95, and even less about primenet (3) I don't really care enough about the other two to put forth much effort. (Note that I *do* apreciate Prime95 and primenet, I just don't care much about specific issues with them). Now the last one might sound bad, but with school, I hardly have time to add anything I care about to the FAQ (there is a section on P-1 factoring, Q3.10 BTW). Hopefully this should explain things a bit. I will (eventually, once I read more on it) add a section to the FAQ about ECM, but Prime95 specific issues I know little about, and George would be much better suited to writing about this. Sorry if my rambling makes no sense... Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: ECM on P773
"David A. Miller" wrote: In response to a recent suggestion by Paul Leyland, I've been focusing my ECM work on P773. I checked George's ECM status page tonight, and it lists an astonishing 7210 completed curves at B1=11E6. Is this an error, or has someone been putting a ton of machines to work on this task? I have. I´ve got 12 PII-300 and 26 PII-400 at the Technical University of Munich I may use (big hug for the admins!) but I can only do ECM and NFS as they are running Solaris. I´m also after M727, M751 and P608. Ciao, Alex. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
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
Mersenne: ECM Factoring
Glenn Brown writes: The computer has found TWO factors of 2^647+1. It's still searching! WHY Good question. Most likely, because what's left is still composite. But since I don't know what program you're using nor what factors it has found, I can't help you more without more information. From the current lowM.txt file, which presently includes all the data that I have on incompletely factored Mersenne numbers with exponents up to 200,000: M( 1294 )C: 4570409 M( 1294 )C: 9021769 M( 1294 )C: 932184694939 ... since: (2^647 + 1)*(2^647 - 1) = (2^647)^2 - 1^2 = 2^1294 - 1 = M(1294) ... factors of 2^647 + 1 will be listed under M(1294) in lowM.txt. Factors of M(1294) that are also factors of M(647) are only listed under M(647). Data for completely factored Mersenne numbers is moved from lowM.txt to factoredM.txt. LowM.txt - factors, cofactors' primality, etc. - is verified by the ecm3 program of the mers package every time I update my data, usually for all exponents up to around 15,000 (depending on how long I let it run). New data is gathered from George Woltman's ftp site, Paul Leyland's Cunningham Project ftp site, and Conrad Curry's P-1 data ftp site automatically as part of my update scripts. Will http://www.garlic.com/~wedgingt/mersdata.tgz tar'd gzip'd lowM.txt, etc. mersdata.zip DOS zip'd lowM.txt, etc. mersfmt.txtdescription of format mersenne.html descriptions and links