RE: Mersenne: LL question
- From: "Hoogendoorn, Sander" [EMAIL PROTECTED] - But what if the mod M comes out to 1 on one of - the intermediate steps? Then 1^2 - 2 = -1 - Then what? spike -Then you will be stuck in a loop, same thing happens when the outcome is - -2, -1, 0 and 2 This case never occurs. If M = 2^p - 1 where p is prime and p 2, then M == 7 (mod 12). By quadratic reciprocity, the Jacobi symbol (3 over M) is -1, so 3 is not a square modulo M. Therefore x^2 - 2 == 1 (mod M) has no solution. _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: LL question
Oops, I meant mod M(-1) which is M-1... Steve I don't believe that can ever happen, but if it did then the next step would just use mod(-1) which is p-1. The mod function never returns a negative number. Steve Harris -Original Message- From: Spike Jones [EMAIL PROTECTED] To: [EMAIL PROTECTED] [EMAIL PROTECTED] Date: Wednesday, March 28, 2001 1:47 AM Subject: Mersenne: LL question OK I understand how you start with 4, then square and subtract 2, then take the mod M, then repeat P times. If the remainder is 0, then M is prime. But what if the mod M comes out to 1 on one of the intermediate steps? Then 1^2 - 2 = -1 Then what? spike _ 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 _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Notification for RE: Mersenne: LL question
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
