Re: Mersenne: Worth it?
Heya Lucas > P-1 factoring is based upon Fermat's little theorem which states that > with gcd(a,p)=1, p prime, a^(p-1)==1 mod p > What if we use 2 as a base? Well, for mersenne numbers, this might be to > our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn. Unfortunately we're in a circular argument at this point. The factors of 2^p-1 are of the form 2kp+1 - also, even for n composite, the 'new' (primitive) factors of 2^n-1 are of the form kn+1. So any prime factor q has q-1 divisible by n, and we already have 2^n=1 mod Mn and hence mod q... Alternatively, think of the values 2^0, 2^1, 2^2... 2^(n-1), which would be ALL the values 2^q mod Mn can possibly take. So if this method found a factor, it would be a common factor of 2^q-1 and 2^n-1, in other words, just one of the known algebraic factors 2^gcd(q,n)-1. P-1 is good up to a point... the prime factors P it finds will by definition either have ALL factors of P-1 very small, or your initial base is already a high power (which is very unlikely). It's good to find the 'smooth' P-1's - put it another way, the factors the P-1 algorithm finds are themselves very easy to prove prime or composite. While the vast majority of primes (and thus potential factors) certainly do not always have small factors in P-1. It will catch a few several digit factors - after that, you've pretty well exhausted the lowest cherries off the tree. Chris _ 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
Re: Mersenne: Worth it?
Here's something interesting, it *might* allow us to almost eliminate the x squarings in p-1 factoring. P-1 factoring is based upon Fermat's little theorem which states that with gcd(a,p)=1, p prime, a^(p-1)==1 mod p. Now, say we are factoring the number n, and p|n. We assume that (p-1)|q (hence q needs to have small factors), therefore a^q==1 mod p. Then we find (a^q-1) mod n, and then find gcd((a^q-1) mod n,n). If it is not equal to 0,1, or n then you have found a non-trivial factor (note, a result of zero would occur when (m-1)|q, and m was a base a Fermat prob. prime). (Now none of the variables in the previous paragraph carry over into the next :) What if we use 2 as a base? Well, for mersenne numbers, this might be to our advantage. Note that 2^n==1 mod Mn, hence 2^q==2^(q mod n) mod Mn. This would bring us down to (at most) log_2(n) squarings, which is insignificant. The possible problem (other than the required gcd) is this: Take 2^(a#)-1 has the factor (the product from 1 to a, p prime, of 2^p-1) Where # is the primorial function. Now, as I understand it, each prime number is "assigned" to a certain Mersenne, and this may or may not cause problems, I don't know. (Note that even after the removal of the trivial factors, there is still a very large number remaining). This would allow us to have huge, and I mean fricking huge B1 values, for no extra cost. Maybe even as high as 2^32. Using a linear approximation of my pseudo-primorial function in my previous posting, I get this number would have around 6.18*10^9 bits (627 megabytes), though it could be calculated indirectly (1.9*10^8 multiplications mod n). If this pans out, then P-1 would have decided advantages over trial factoring (past a certain point), even at lower exponent ranges. -Lucas _ 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
Re: Mersenne: Worth it?
>> 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. My numbers are quite suspect. I just did the primorial of _10,000_ not of 100,000 (though, the prime number theorem tells us that the primorial function should approach e^x , hence the number of bits would be linear). I also did not take into account that (for example) it is more likely that a number (p-1 in this case) will be divisible by 4, rather than 5. That is to say, instead of taking the strict primorial, I should have found the product of p^floor(log_p(B1)), p prime, from 1 to B1 (note that p^floor(log_p(B1)) is the largest power of p not greater than B1, because if it was bigger than B1, getting a bigger B1 value would make more sense). (whew!) Well, after all that, I found out that David's misinterpretation of my original estimate is very close (shows the power of S.W.A.G.) The number of bits for B1=100,000 is 144,330. (plus the bits of the exponent, obviously) (Off topic, when I computed that value in Landon's Calc program, my computer PII/233 started making a weird humming noise. The noise stopped when the calculation finished. Very strange indeed...) > 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? Yes, there is no point in finding a 32-bit factor with something that might take weeks, when it would take ~1/5,000th of a second to find it with Brian's factor95 program. I suppose the estimate is based upon the probability that one number would divide another, based on the factors of the numerator. I'll get back to you. > 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. As I mentioned earlier. However, we do have loads of factoring data, plenty enough to test conjectures with... (well, probably enough, anyway) Besides, who knows, maybe the factors of Mersenne numbers with small factors of P-1, follow a very strict rule, while they get less predictable when the factors of P-1 get large. > 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. Same is true of trial factoring. What might be useful is if someone were to factor a large number of the k in 2kn+1 (n is the exponent) and see if any patterns emerge (i.e. find out if the p-1 usually takes special factors, other than the usual ones). This would further increase the "deterministic gap," even though it might increase the number of factors found. Man, the p in P-1 and the usual p in Mp are easy to get confused! > 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! 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. -Lucas Wiman _ 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?
Disclaimer: All my commentary is based on recollections of what I did a few years ago. I believe that there are comments in an archive somewhere by Peter Montgomery and George Woltman conatining much more accurate info. Lucas Wiman wrote: > > Sorry if this is sending out twice, I wasn't sure that it got sent the > first time... > That was my fault. I cc'd my response to base.org and the DNS got confused. > >> 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) > 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. 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. > >> 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. > 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). 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 imagine that from what you are saying, it gets more cost-effective > the higher the exponent. How does it look at around 33219281? 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. > > -Lucas > _ > 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: 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
Re: Mersenne: Worth it?
> 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) ? 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. 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. 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). 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. -Lucas _ 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
