Mersenne: Combining Prime95 and gmp-ecm
Hi, gmp-ecm version 5 can read ECM residues written by Prime95 to perform stage 2 on them. Stage 2 is asymptotically faster in gmp-ecm, but Prime95 has a much faster multiplication for large numbers, so this feature is mostly interesting for relatively small numbers (i.e. of a few thousand bits) that are to be factored with a large stage 2 limit. Another feature is that the B2 value in gmp-ecm is not limited to 2^32, so you may take stage 2 limit to much higher values than Prime95 currently supports. In order to be able to resume ECM residues from Prime95 (version 22.9 or later), you will first have to set the GmpEcmHook option (described in undoc.txt) in prime.ini. Simply add the line GmpEcmHook=1 This will cause Prime95 to write the residues from the end of stage 1 to results.txt if no stage 2 is performed. These residues in results.txt can be read into gmp-ecm with the -resume option to do stage 2. Example: Richard Brent's factorization of F10 (remeber to put the smaller factors 45592577 and 6487031809 into lowp.txt if you want to try this example yourself) workdodo.ini : ECM=1024,314263,1,1,0,14152267,1,20 This computes the lucky curve with sigma=14152267 and a stage 1 bound of 314263. Note that B2 is set to 1, so that Prime95 will not do a stage 2 but will write the residue instead. Running Prime95 (or mprime) now outputs Mersenne number primality test program version 22.12 ECM on P1024: curve #1 with s=14152267, B1=314263, B2=314263 Stage 1 complete. 8133791 transforms, 1 modular inverses. Time: 13.603 sec. Stage 1 GCD complete. Time: 0.000 sec. There are no more exponents to test. Please send the results.txt file to [EMAIL PROTECTED] Contact the PrimeNet server for more exponents. The results.txt file contains [Wed Feb 26 19:15:13 2003] N=0x3E(... deleted ...)001; QX=0x275(...deleted...)802; SIGMA=14152267 UID: akruppa, P1024 completed 1 ECM curves, B1=314263, B2=314263 The stage 2 for this residue can be computed with gmp-ecm 5 by running ecm -resume results.txt 1 314263-1000 which outputs GMP-ECM 5.0 [powered by GMP 4.1] [ECM] Save file line has no equal sign after: [Wed Feb 26 19: Resuming ECM residue saved with Prime95 Input number is 607(... deleted ...)569 (291 digits) Using B1=1, B2=314263-1000, polynomial x^1, sigma=14152267 Step 1 took 0ms Step 2 took 2450ms ** Factor found in step 2: 4659775785220018543264560743076778192897 Found probable prime factor of 40 digits: 4659775785220018543264560743076778192897 Probable prime cofactor 130(... deleted ...)577 has 252 digits Save file line has no equal sign after: UID: akruppa, P The factor is being found. (Gmp-ecm complains about the lines in results.txt it does not understand, but the residues should be processed correctly) The parameters to gmp-ecm are: -resume filename Which file to read the residues from 1 The stage 1 limit, which we set to 1 because we have already done the stage 1 computations with Prime95 314263-1000 The stage 2 range. Prime95 did stage 1 with B1=314263, so we tell gmp-ecm to do stage 2 from that point on, up to 1000. The lower limit of the stage 2 range should always be set to the B1 value Prime95 used, the upper limit is the effective B2 value for the ECM curve. If you would like to do, say, 100 curves on F12 with B1=4400, you should have in worktodo.ini ECM=4096,4400,1,100,0,0,1 After Prime95 has completed the stage 1 for the 100 curves, you can resume the residues in results.txt with ecm -resume results.txt 1 4400-184367799127 Note: 184367799127 is the default value for gmp-ecm with B1=44M. You may want to lower it so that the time spent in Prime95 and gmp-ecm per curve is roughly the same. Note 2: remember to remove or rename results.txt after running it through gmp-ecm, or the next time around it will process the same residues again. Happy factoring, and good luck! Alex _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring 2^n+1 and 2^n-1
Hi, Ernst Mayer once mentioned to me that Prime95 needs twice the FFT size for 2^n+1 numbers (compared to 2^n+1 numbers). Does that mean that George is using the identity 2^(2n)-1 = (2^n+1)(2^n-1) ? I was wondering why ECM on 2^n+1 numbers took much longer than on 2^n-1 of the same size.. That would mean that I can do ECM on, for example, P773 and M773 at the same time by doing ECM on M1546, and it will take just as long as ECM on only P773, right? When I find a factor, I'll just have see which number it divides. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
Lucas Wiman wrote: P-1 factoring is based upon Fermat's little theorem which states that [...] What if we use 2 as a base? Well, for mersenne numbers, this might be to The problem is that 2 is not a primitive root (mod Mp). From a computers point of view, the mod Mp operation is a rotate and add, so if you start with a single bit set (2d = 10b), that bit will rotate around the p possible positions like mad but you´ll only ever get values of 2^n, 2^E == 2^n (mod Mp). So you could only find factors of the form 2^n-1. Ciao, Alex. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Worth it?
Hi, from stuff I saw on the list earlier I put together this estimate: The chance for Mp being prime if it has no factor below 2^q is 2q/p (if q is reasonably big, at i.e. 2^q much bigger than 2p+1). If we test the Mersennes in the 10M-digits range for factors to, say, 2^80, the chance for, say, M33219281, to be a prime is 1/207620. So the average money you´ll earn for a test in this range is a little less than 50c. George has estimated that a test will take about 1 year with current hardware. We should try to increase this probability before starting any full LL test, perhaps by using better factoring algorithms. Will v19 have P-1 code that works with numbers of this size? But even with P-1, we might not be able to factor that much further. The time consuming part of P-1 are multiplications mod Mp just as in the LL test, so the crossover point between raising the factoring limit and starting the LL test will be a function of p (the number of interations in the LL test) and less than linear, that is, we might not get very far. Do we have estimates already what the optimal bound values will be for trying P-1 on a given Mp, to minimize the (time of P-1 test) + (time of LL test * chance of not finding any factor) ? What would REALLY help here is a transform that allows multiplying without loss of accuracy (mod Mp), even if you can´t add/sub in the transformed data. P-1 only exponentiates, you if could exponentiate every transformed element and then transform back... talk about bound values! I don´t know of any such transform, if you do, please say. 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
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
Mersenne: Distribution of factors among congruence classes
Hi all, I wrote a little program to show the distribution of factors among congruence classes, especially (mod 8) and (mod 120) (all others were as uninteresting as you would expect). What surprised me was that the distribution is not smooth at all, some congruence classes contain a lot more factors than others. Is there a nice mathematical explanation for this? Maybe in the factoring code of Prime95, the sixteen congruence classes (mod 120) should be arranged so that the luckier classes get tested first, because if a factor is found, the following classes need to be checked only up to that factor to find a smaller factor. Finding the factor early will save a little time. The factors were from lowM.txt, but only from prime exponent mersennes. Ciao, Alex. P.S. I have no idea what the factor 55 (mod 120) is doing there. I'll add something to my program to print out offending factors when I have time. 1 7 8 : 16517 21290 1 7 17 23 31 41 47 49 55 71 73 79 89 97 103 113 119 120 : 16752627234030092015192830341985*1 2387 2049258122271996267423172962 Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
