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
Re: Mersenne: Worth it?
On 19 Jul 99, at 22:21, David M Einstein wrote: You will want to do P-1 in addition to, and after seiving. It would be foolish to use p-1 to discover a 30 bit factor. Not half - trial factoring with numbers that small, and _very_ heavily constrained, is _extremely_ fast. I tested 159,975 exponents (the prime numbers between 33219278 and 3600) for factors up to 2^32 in less than 20 seconds on a PII-350. If you are doing stage 1 only I believe that I had looked at a b1 of at least 100K which would translate to about 140K (I'm trusting your numbers) squarings. I think that that is still less than 5% of the number of squarings for a current LL test, and would reap factors for about 5% of the numbers so would at least break even. Interesting ... There is obviously a breakeven point between trial factoring (which will _definitely_ find any factors up to the limit specified) and P-1 (which might not). So, are we in any sort of position to estimate where that breakeven point might be, for exponents say around 10 million? What about smaller exponents, say around 5 million, which have (mostly) already been LL tested but haven't been double checked yet? (Finding a factor saves running the double check) The fact that we would still be running trial factoring up to some limit (though maybe a little lower than we are at present) would to some extent remove the objection that an exhaustive search of at least part of the range of possible factors is useful. There is going to be another breakeven point between P-1 factoring and LL testing - if we run a LL test, then (barring accidents) we get a definitive result in a predictable time, whereas we could run P-1 "for ever" on even quite a small exponent without arriving at a definite result. Not exactly. With a reasonable B1 I doubt that it would be the most time consuming part, but a straight euclidean or lehmer algorithm would be quite slow. A divide and conquer algorithm would be much faster, but extremely memory hungry (Violating GIMPS's unstated (but very positive) invisibility constraint (No noticable effect on the host systems operation). Can we speculate on approximately how much memory would be needed, as a design exercise? In any case, it needn't rule the scheme out altogether if we find that some systems aren't able to contribute usefully by reason of limited memory. After all, not all systems can contribute usefully to some other tasks, e.g. it's a bit pointless to try to run a LL test on a 7 million range exponent on a 486, though the program _will_ try, if you ask it to! I believe that one of the reasons that the next version of prime95 will contain a straight FFT multiply is to support a divide and conquer GCD, but that is supposition on my part. I thought maybe it was something to do with making more efficient use of the L2 cache by keeping FFT data size reasonable using a recursive method to break large numbers down into small operations that would "fit". Implementing this would require a general m * n bit multiprecision multiplication function. I think that a P-1 would probably be neccessary. There may be enough room for ECM to have overcome P-1's free factor of P, but I dont think so. ECM actually has a moderate memory load even for small exponents, you need to keep _lots_ of n bit work vectors lying about. Though you don't need to access all of them all that often, so it doesn't hurt _too_ badly if some of them are forced out to a paging file. c.f. LL test becomes _impossibly_ slow if you run out of physical memory the system starts paging on you. I wonder if we already have the data we need to make some of the estimates I've indicated above, or whether someone will have to go try to make them - , if so, whether we actually need to code anything, or whether it would be possible to use George's existing P-1 factoring program to make them. Regards Brian Beesley _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Worth it?
FAQ author Lucas Wiman [EMAIL PROTECTED] writes Well, this might not be a problem. If P-1 tries more than one base, all that is required (per Mn) is *one* gcd. We just multiply the remainders from the bases mod Mn, and then take the gcd on the final remainders. We could have the program prompt the user for the time when the computer is on but not being used when they ask for a P-1 assignment. Or, we could have it run so that the program stops functioning when the computer is being used. It could just save the intermediate files to disk, to free up memory for the user who (graciously) gives us their CPU cycles. You might rerun P-1 with larger limits, but don't bother rerunning using a new base. If q is a prime factor of Mp, and r is the largest prime factor of q-1, then a fraction 1 - 1/r of all possible bases will require us to include exponent r in step 1 or step 2 of P-1. If r 10, this is 99.999% of all potential bases. The base change can be useful if P-1 finds a composite GCD. For example 2717 = 11*13*19. If we start with base b = 7, using exponents 4 and 3, then b^4 = 2401 == -316 (mod 2717) (b^4)^3 == -31554496 == 742 (mod 2717) Here GCD(b^12 - 1, 2717) = 247 is composite (13*19). This is because 13-1 divides the exponent 4*3 and because our choice b = 7 is a cube (also a square) mod 19, with (19-1)/3 dividing 4*3. Choosing a b which is not a cube modulo 19 lets P-1 factor 247. Peter Montgomery _ 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: Worth it?
Sorry if this is sending out twice, I wasn't sure that it got sent the first time... As I understand the Pollard P-1 algorithm, the time required for 1 bit of the exponent would be equal to 1 iteration of the LL test (one squaring mod Mp), so values wouldn't be that hard to create. (timing values, for comparison with regular factoring) The main problem is that to get a bound of any reasonable size, and try multiple bases, you are looking at a time comperable to the LL test. (I suppose that on further investigation, with a bound value for factors of the exponent at 10,000 we are looking at about 14,000 squarings mod Mp, which is really not all that many) Also, one of the keen things about GIMPS is that in its search for primes, it came up with loads of factoring data for Mersennes. However, the P-1 algorithm would make any factor distribution data a lot less usable (as it would not include P with P-1 having a large prime factor). (That is to say, if the P-1 algorithm was used, it still couldn't find all the factors 2^64, unless we are talking about incredibly high bound values) On the other hand, the P-1 algorithm can take advantage of the special form of Mersenne factors. We know that P-1 must be divisable by the Mersenne exponent, and that in 1/2 of the cases, it is divisable by 8. (we know that the factors must be of the form 2*k*p+1, hence the factor-1 must be divisable by 2*p, or in the form 8*n+/-1, hence the factor-1 must be divisable by 2 or 8) I'm not sure that I understand what you are saying, but the following are a few observations that I made when I looked at the problem a few years ago. The major stumbling block for an efficient P-1 is the implementation of a time and memory efficient GCD. If one has a good GCD algorithm then a stage 1 only implementation becomes cost effective for exponents around 3 million. However, the cost savings is tiny, probably less than a percent overall. The major benifit is that one does not need to double check the exponent. Yup, silly me. You are quite correct, of course, that the GCD is the most time consuming part. I imagine that from what you are saying, it gets more cost-effective the higher the exponent. How does it look at around 33219281? -Lucas _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
