Mersenne Digest Sunday, October 3 1999 Volume 01 : Number 636 ---------------------------------------------------------------------- Date: Thu, 30 Sep 1999 23:16:27 -0700 From: Mike Bandsmer <[EMAIL PROTECTED]> Subject: Mersenne: Possible idea for increasing GIMPS throughput Here is an idea that may be useful in increasing the throughput of GIMPS. In the June 1999 issue of the IEEE Signal Processing Letters, Shay Moshe and David Hertz present the article "On Computing DFT of Real N-Point Vector and IDFT of DFT-Transformed Real N-Point Vector via Single DFT". Basically, the article gives a simple method of computing an n-point DFT and an n-point IDFT using only a single complex n-point DFT (and minor additional computations of complexity O(n)). I was thinking that this might be useful for GIMPS, in the following scenario: Suppose a user has two exponents, p and q, both of which use the same FFT size for the squaring operations of the Lucas-Lehmer calculation. Let {L(i)} be the Lucas-Lehmer sequence for exponent p, and let {L'(i)} be the Lucas-Lehmer sequence for exponent q. Then both exponents could be tested in parallel, using the above algorithm, as follows: Exponent p Exponent q - ----------- ----------- L(1) = 4 L'(1) = 4 perform FFT square elements perform IFFT perform FFT <--- perform in parallel subtract 2 square elements to get L(2) perform FFT perform IFFT <--- perform in parallel square elements subtact 2 to get L'(2) perform IFFT perform FFT <--- perform in parallel subtract 2 square elements to get L(3) perform FFT perform IFFT <--- perform in parallel ... ... When one of the two exponents is finished, a third exponent could be started and its Lucas-Lehmer sequence calculated in parallel with the remaining exponent, and so on. In this way, two exponents could be tested using the same number of FFT/IFFT operations as is currently being used to test 1 exponent. So if I haven't overlooked anything (a big "if"), this could nearly double the throughput of GIMPS. (I have assumed that the time for a single squaring operation in the current implementation is approximately the time for an FFT + the time for an IFFT-- correct me if I'm wrong.) Mike P.S. If there is sufficient interest, I can post the details of the simultaneous FFT/IFFT algorithm to the list for those who don't have access to the original article. _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 1 Oct 1999 09:59:01 +0200 (CEST) From: Henrik Olsen <[EMAIL PROTECTED]> Subject: Re: Mersenne: Purpose... On Fri, 1 Oct 1999, Ian L McLoughlin wrote: > Forgive me, > But, I seem to be subscibing to a project which is utilising processors > 'world-wide' for several purposes: > A) For Programmers to enhance their skills at the 'cutting edge' Yep. > B) For Web based people to increase their knowledge within a distibuted > network. Yep. > C): > I realise that a lot of what is contributed is going to be used in > encryption et.al... Nope. I think you're confusing GIMPS and the Mersenne project which are almost entirely about pure maths and efficient algorithms, and the Bovine project which is about solving cryptographic challenges to show the strength/ weakness of the different encryption schemes. Some of the algorithms developed for the Mersenne and similar projects, have applications for cryptography, but it's mainly in the field of breaking the codes, so it may have the effect of forcing the US government to change their ways. > Since I am based in Europe, and denied certain facilities from the web as to > U.S. encryption bit encoding ( U.S. and Canada keeping it for > themselves..?!)... Canada has no choice in the matter, it's the US export restrictions that dictate how software from the US can be reexported. I'm in Europe too, and the EU is almost as bad, with Wassenaar putting about as strong a grip on crypto as the US, though they put in a loophole, so nonprofit software isn't covered:) There are non-US implementations of most crypto protocols, so you should definitely be able to stay safe if you think you need it. > Is their an auterior motive behind this...??????? World domination of course, when has anyone wanted anything else.:) > > Just a thought..... > Ian McLoughlin, Chematek U.K. > > Tel/Fax : +44(0)1904 679906 > Mobile : +44(0)7801 823421 > Website: www.chematekuk.co.uk - -- Henrik Olsen, Dawn Solutions I/S URL=http://www.iaeste.dk/~henrik/ `Can you count, Banjo?' He looked smug. `Yes, miss. On m'fingers, miss.' `So you can count up to ...?' Susan prompted. `Thirteen, miss,' said Banjo proudly. Terry Pratchett, Hogfather _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 01 Oct 1999 10:21:38 -0600 From: Aaron Blosser <[EMAIL PROTECTED]> Subject: RE: Mersenne: Purpose... > I realise that a lot of what is contributed is going to be used in > encryption et.al... > Since I am based in Europe, and denied certain facilities > from the web as to > U.S. encryption bit encoding ( U.S. and Canada keeping it for > themselves..?!)... > Is their an auterior motive behind this...??????? The types of primes found by GIMPS are so incredibly huge that they would have no practical purpose for encryption. Besides, with only 37 known Mersenne Primes, any key generated using even 1 Mersenne Prime would be easily decrypted since there are only 37 divisors you'd have to go through. Practical encryption uses much smaller primes, of which there are many, but still large enough that factoring the product of 2 primes would take much too long to be practical. The RC5 cracking project, on the other hand, is specifically targetted at decryption and has, IMO, been quite successful at forcing the US gov't. to open their eyes to how incredibly weak 40/56/even 64 bit encryption is, and has probably been a major catalyst in the US finally allowing certain permissions for higher bit encryption to be exported. What's really retarded about the US is that the algorithms for such encryption are very well known, programs that do high bit encryption are available all over the world, by non-US software authors, and it just seems silly to continue classifying high encryption as a munition. About as silly as those Mac G4 commercials claiming that the G4 is considered a munition because of it's processing capability, or the rumours that <whatever that new game console was> is a munition for the same reason. Totally retarded. But hey, that my never humble opinion. :-) Aaron _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 1 Oct 1999 15:27:15 EDT From: [EMAIL PROTECTED] Subject: Mersenne: Re: Mlucas and MacLucasUNIX on SPARC Bill Rea <[EMAIL PROTECTED]> writes: << I tried the Mlucas_2.7x compiled with Sun's f90 version 2 and compared this against MacLucasUNIX v6.20. On the two ranges of exponents I tried Mlucas was about 15% slower than MacLucasUNIX, using 256k and 512K FFTs. Currently I'm double checking some exponents around 4,100,000 and doing LL testing on some around 8,300,000. One advantage Mlucas might have over MacLucasUNIX is that it can do FFT sizes other than 2^n, but even using the 224K and 448K FFTs for these exponent sizes, it was slower than MacLucasUNIX by about 8%. >> Hi, Bill, and thanks for the timings. Note that there's an updated beta, v2.7y available now. It has better cache behavior and some minor bugfixes. I get about a 10% speedup on my MIPS R10Ks (more at power-of-2 runlengths, and especially at really big N) over v2.7x. << The compiler options I used were:- -fast -libmil -xlibmopt -xarch=v9 >> Alex Krupa says he got the best timings using -fast -libmil -xlibmopt -fns=yes -xarch=v9, but I don't know if the -fns=yes flag makes a difference. I'm also told that Solaris 6 users should use -xarch=v8plus, as S6 doesn't support -xarch=v9. You might also try using -xinline=all and -xdepend. (I have no SPARC to play with, so don't know if those will help.) One final optimization you can try is to do runtime profiling at a desired FFT length to improve performance. Rob Vassar <[EMAIL PROTECTED]> writes (about some timings he did using v2.7x): << Some preliminary results for M110503: flags: "-fast -xarch=v9 -xchip=ultra2i -xcache=16/32/1:512/64/1 - -libmil -xlibmopt -fns=yes" ~0.00443 per iteration flags: "-fast -xO5 -xarch=v9 -xchip=ultra2i -xcache=16/32/1:512/64/1 - -libmil -xlibmopt -fns=yes" ~0.00412 per iteration [Next Rob added runtime profiling - compile as below, but using - -xprofile=collect, then do a 100-iteration timing test at a desired runlength, then recompile using] flags: "-fast -xO5 -xarch=v9 -xchip=ultra2i -xcache=16/32/1:512/64/1 - -libmil -xlibmopt -fns=yes -xprofile=use" ~0.00372 per iteration! So, it would appear that profiling does offer some gain on M110503. I'm going to try a few larger FFT sizes and see if the profile gain remains, or is limited to one FFT size. Before I forget... The binary I generated is tuned specifically to the Ultra-IIi CPU in my Ultra 10. Compiling for the Ultra 2 w/300Mhz CPU('s) would change the chip and cache flags as follows "-xchip=ultra2 -xcache=16/32/1:2048/64/1". Since the binary is "-xarch=v9" it will only run on an Ultra class machine, not SS20's, SS5's, or SS2's. >> Note however that profiling as above appears to only improve performance AT THE PARTICULAR FFT LENGTH USED to collect profile data. It may actually hurt performance at other lengths. If it gives a nice speedup at the particular N, you might consider compiling a couple versions - you wouldn't need more than (say) two at any one time, e.g. at the moment you'd need ones for 384K and 448K. Best regards, Ernst _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Thu, 30 Sep 1999 16:47:50 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: New roundoff record? After overclocking my poor 400 MHz PII to 496 MHz (and upping the voltage from 2.00V to 2.30V), I figured out I should perhaps do a torture test for a few days, before throwing it at my real exponents :-) After 10 seconds, I got: Test 1 of 15, 400 Lucas-Lehmer iterations of M19922945 using 1024K FFT length. ERROR: ROUND OFF (5.283699122e+13) > 0.40 Possible hardware failure, consult the readme file. Has anybody experienced any _bigger_ roundoff errors than this? (The same machine is rock stable at 448 MHz, BTW. The multiplier is locked at 4x, though, so I can't overclock it any other way.) /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 1 Oct 1999 23:06:41 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Possible idea for increasing GIMPS throughput On Thu, Sep 30, 1999 at 11:16:27PM -0700, Mike Bandsmer wrote: >Basically, the article gives a simple method of computing an n-point DFT >and an n-point IDFT using only a single complex n-point DFT (and minor >additional computations of complexity O(n)). [...] >In this way, two exponents could be tested using the same number of >FFT/IFFT operations as is currently being used to test 1 exponent. Unless _I'm_ the one mixing up things here (very likely...), a possible error might be that you're mixing DFT and FFT? Aren't those two different algorithms? /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 1 Oct 1999 23:08:23 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Purpose... On Fri, Oct 01, 1999 at 10:21:38AM -0600, Aaron Blosser wrote: >The types of primes found by GIMPS are so incredibly huge that they would >have no practical purpose for encryption. Nope, there is a crypto system using the Mersennes. Look for a link to it at www.mersenne.org. (It is also mentioned in one of the Mxx press releases from George... or at least in an article ;-) ) /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 1 Oct 1999 14:51:16 -0700 (PDT) From: Mike Bandsmer <[EMAIL PROTECTED]> Subject: Re: Mersenne: Re: Possible idea for increasing GIMPS throughput On Fri, 1 Oct 1999, Steinar H. Gunderson wrote: > >In this way, two exponents could be tested using the same number of > >FFT/IFFT operations as is currently being used to test 1 exponent. > > Unless _I'm_ the one mixing up things here (very likely...), a possible > error might be that you're mixing DFT and FFT? Aren't those two different > algorithms? The FFT (Fast Fourier Transform) algorithm is simply a fast way of computing the DFT (Discrete Fourier Transform), so the two terms are interchangeable as far as I know. Sorry about the confusion. Mike _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 01 Oct 1999 16:15:27 -0600 From: Aaron Blosser <[EMAIL PROTECTED]> Subject: RE: Mersenne: Re: Purpose... > >The types of primes found by GIMPS are so incredibly huge > that they would > >have no practical purpose for encryption. > > Nope, there is a crypto system using the Mersennes. Look for > a link to it > at www.mersenne.org. (It is also mentioned in one of the Mxx > press releases > from George... or at least in an article ;-) ) Hmm...no kidding. Now, correct me if I'm wrong (I probably am) but aren't those types of encryption schemes based on multiplying large primes together to generate the "key", and the fact that it would take a VERY long time to factor the product means it's relatively secure? So...how would it be helpful to use certain types of primes during the key generation? That takes away a huge chunk of the security, especially since with Mersenne primes being one of the number multiplied, you only need try 38 (not 37...doh!) numbers to try and factor with in order to find the pair. And of those 38, alot are small enough to be worthless for encryption anyway. I know that certain of the algorithms we have available, such as ECM, do make it faster to hunt for factors, meaning that factoring an unknown pair can be done faster, but I didn't think that Mersenne primes in particular are useful for cryptography at all. Aaron _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 01 Oct 1999 20:13:13 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: Mersenne cryptography (was: Purpose...) Hi, At 04:15 PM 10/1/99 -0600, Aaron Blosser wrote: >Hmm...no kidding. Now, correct me if I'm wrong (I probably am) but aren't >those types of encryption schemes based on multiplying large primes together >to generate the "key", Richard Crandall's method is not based on multiplying primes together where the message is hard to crack because factoring is difficult. Instead, his method uses eliptic curve algebra and is "safe" because finding discrete logarithms are difficult to find. The method is patented. I'm under NDA so even if I understood it at all, I can't tell you any more. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 02:17:53 +0100 From: Tony Forbes <[EMAIL PROTECTED]> Subject: Re: Mersenne: Search for a divisor of M_M_61. My previous announcement contained errors. Here it is again. You can download 'MFAC' from http://www.ltkz.demon.co.uk/ar2/mfac225.zip and e-mail me for a range. MFAC searches for divisors of double-Mersenne numbers M_M_e = 2^(2^e-1) - - 1 for not-too-large exponents e. MFAC runs on any PC from a 486 upwards and on any system that supports MSDOS. You can even run it entirely from a bootable diskette. Memory usage is small and the files require less than a megabyte of disk space. The program is easily stopped and restarted. I have volunteered to coordinate a search for factors of M_M_61. Let d be a divisor of M_M_61. Then we know that d = N*(2^61 - 1) + 1. The parameters I intend to send out will set up MFAC to look for divisors of M_M_61 with N's in ranges of 204,204,000,000 To give some idea about timing, an AMD K6/2/400 will do a range in about 4 days. I intend to out ranges from N = 10^14 approx. to avoid clashing with work currently in progress by Sturle Sunde. - -- Tony _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Fri, 01 Oct 1999 20:19:13 -0700 From: "Terry S. Arnold" <[EMAIL PROTECTED]> Subject: RE: Mersenne: Re: Purpose... There are presently three families of public key cryptographic algorithms. Only the IF (Integer Factorization) family is based on the concept of using the product of two primes where these primes must be kept secret. The other two families DL (Discrete Logarithm) and EC (Elliptic Curve) are based on entirely different principles. The DL family uses a prime as the basis for arithmetic over the Galois field GF (p). This prime is public information. The other family, EC, uses a prime number as the basis for either GF (p) or GF(2**p). Again the prime p is public information. The significance of Mersenne primes in DL and EC cryptographic systems is that arithmetic can be sped up if p is a Mersenne prime. I believe that this is part of the trick in Crandall's scheme, although I have not looked at his patents in detail. What does this mean for GIMPS? Not a whole lot, since all of the Mersenne primes that are of practical use in cryptography are already known. IMHO the entire RC5 effort had the primary goal of making a political statement that served to line the pockets of a small number of people. This primary goal did not prove anything that was not already known. It did have the secondary product of providing and example of an effective distributed computation on PCs. That was a worthwhile goal in its own right. At 03:15 PM 10/1/1999 , Aaron Blosser wrote in flowing prose: > > >The types of primes found by GIMPS are so incredibly huge > > that they would > > >have no practical purpose for encryption. > > > > Nope, there is a crypto system using the Mersennes. Look for > > a link to it > > at www.mersenne.org. (It is also mentioned in one of the Mxx > > press releases > > from George... or at least in an article ;-) ) > >Hmm...no kidding. Now, correct me if I'm wrong (I probably am) but aren't >those types of encryption schemes based on multiplying large primes together >to generate the "key", and the fact that it would take a VERY long time to >factor the product means it's relatively secure? > >So...how would it be helpful to use certain types of primes during the key >generation? That takes away a huge chunk of the security, especially since >with Mersenne primes being one of the number multiplied, you only need try >38 (not 37...doh!) numbers to try and factor with in order to find the pair. >And of those 38, alot are small enough to be worthless for encryption >anyway. > >I know that certain of the algorithms we have available, such as ECM, do >make it faster to hunt for factors, meaning that factoring an unknown pair >can be done faster, but I didn't think that Mersenne primes in particular >are useful for cryptography at all. > >Aaron > >_________________________________________________________________ >Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm >Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers Terry S. Arnold 2975 B Street San Diego, CA 92102 USA [EMAIL PROTECTED] (619) 235-8181 (voice) (619) 235-0016 (fax) _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 02 Oct 1999 13:10:47 -0700 From: MilesDaniel <[EMAIL PROTECTED]> Subject: 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,3000000,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 ------------------------------ Date: Sat, 02 Oct 1999 14:46:22 -0400 From: George Woltman <[EMAIL PROTECTED]> Subject: Mersenne: Factoring data Hi all, At several users request I've uploaded factoring data for all exponents below 79,300,000. You'll need a special decompression program I wrote. See http://www.mersenne.org/status.htm for details. Regards, George _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 15:45:05 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: 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 ------------------------------ Date: Sat, 02 Oct 1999 16:06:34 -0500 From: Ken Kriesel <[EMAIL PROTECTED]> Subject: Re: Mersenne: New roundoff record? Not quite the same thing, but my personal high, in 4001 exponents tested, is FATAL ERROR: SUM(INPUTS) != SUM(OUTPUTS), 4.637189956e+013 != 1.744531645e+022 Roundoff is normally bounded by 0.5 even when the calculation of residue goes hugely awry. Ken At 04:47 PM 1999/09/30 +0200, Steinar Gunderson wrote: >After overclocking my poor 400 MHz PII to 496 MHz (and upping >the voltage from 2.00V to 2.30V), I figured out I should perhaps >do a torture test for a few days, before throwing it at my real >exponents :-) After 10 seconds, I got: > >Test 1 of 15, 400 Lucas-Lehmer iterations of M19922945 using 1024K FFT length. >ERROR: ROUND OFF (5.283699122e+13) > 0.40 >Possible hardware failure, consult the readme file. > >Has anybody experienced any _bigger_ roundoff errors than this? _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 23:11:34 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Re: Purpose... On Fri, Oct 01, 1999 at 04:15:27PM -0600, Aaron Blosser wrote: >Hmm...no kidding. Now, correct me if I'm wrong (I probably am) but aren't >those types of encryption schemes based on multiplying large primes together >to generate the "key", and the fact that it would take a VERY long time to >factor the product means it's relatively secure? That is only RSA, as far as I remember. Other, such as Diffie-Hellman (ElGamal) uses a prime modulo, for instance. /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 23:20:43 +0200 From: "Steinar H. Gunderson" <[EMAIL PROTECTED]> Subject: Mersenne: Re: Re: Purpose... On Fri, Oct 01, 1999 at 04:15:27PM -0600, Aaron Blosser wrote: >with Mersenne primes being one of the number multiplied, you only need try >38 (not 37...doh!) numbers to try and factor with in order to find the pair. Yeah, but what if you use some more times than others? Numbers can be _combined_, you know. Even using them only once each, you get a keystrength of 38 bits. And that's only _once_ per Mersenne... /* Steinar */ - -- Homepage: http://members.xoom.com/sneeze/ _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 19:35:35 -0400 (EDT) From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]> Subject: 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,3000000,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 ------------------------------ Date: Sun, 3 Oct 1999 04:17:05 +0100 From: "Ian L McLoughlin" <[EMAIL PROTECTED]> Subject: Mersenne: Why test to (completion?) Sorry But. Why do primality tests run to the full value of the integer....For any iteration surely if an exponent is found within the test it should be reported and the program aborted?.....Not being a maths buff... Perhaps I should not be on this list... p.s. The Proth prime site was even more confusing, did not tell me what a Proth prime is, but totally confused me with Cunninghams, Sophie Primes et al...( I have heard of her, though 18/19th Century geezer...Not in the same league as Galois though.... I am beginning to think that maths people talk to deep or...to simply, where is the middle ? Sorry! Keep it simple stupid for us mere mortals! Ian McLoughlin, Chematek U.K. Tel/Fax : +44(0)1904 679906 Mobile : +44(0)7801 823421 Website: www.chematekuk.co.uk _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ Date: Sat, 2 Oct 1999 21:08:34 -0700 From: "Joth Tupper" <[EMAIL PROTECTED]> Subject: Re: Mersenne: Why test to (completion?) Some things are tough to follow whether in the math or in the computer science. Your question is quite vague, unfortunately, so one can only guess that you are asking why we cannot stop in the "middle" of a Lucas-Lehmer test. The essential answer is that we know a property of particular terms in the sequence 4, 14, 192... given recursively by squaring and subtracting 2. That propery is that Q=(2^p)-1 is prime iff the p-1 term is divisible by Q. We have no other information -- so we cannot stop in the middle. Does this help at all? Joth - ----- Original Message ----- From: Ian L McLoughlin <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Saturday, October 02, 1999 8:17 PM Subject: Mersenne: Why test to (completion?) > Sorry > But. > Why do primality tests run to the full value of the integer....For any > iteration surely if an exponent is found within the test it should be > reported and the program aborted?.....Not being a maths buff... > Perhaps I should not be on this list... > p.s. The Proth prime site was even more confusing, did not tell me what a > Proth prime is, but totally confused me with Cunninghams, Sophie Primes et > al...( I have heard of her, though 18/19th Century geezer...Not in the same > league as Galois though.... > I am beginning to think that maths people talk to deep or...to simply, where > is the middle ? > Sorry! > Keep it simple stupid for us mere mortals! > Ian McLoughlin, Chematek U.K. > > Tel/Fax : +44(0)1904 679906 > Mobile : +44(0)7801 823421 > Website: www.chematekuk.co.uk > > _________________________________________________________________ > 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 ------------------------------ Date: Sun, 3 Oct 1999 01:58:28 -0400 (EDT) From: Lucas Wiman <[EMAIL PROTECTED]> Subject: 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 ------------------------------ Date: Sun, 3 Oct 1999 10:35:59 +0100 From: "Brian J. Beesley" <[EMAIL PROTECTED]> Subject: Mersenne: Mersenne data repository Hi everyone, Anyone who has data which they wish to make publicly available may wish to take advantage of my FTP server. Downloads from the server are already available by anonymous FTP (ftp://lettuce.edsc.ulst.ac.uk/gimps), I keep copies of many Mersenne- related programs and also George's database files. I am afraid I cannot allow anonymous upload. If you wish to upload data, please mail me & I will supply you with a username and password which you may use to upload data to your personal filestore. I would appreciate it if you could indicate what data you are uploading, and the approximate space requirement. Notes: Accounts are provided at my personal discretion. There is no appeal procedure. I regret that I am unable to provide support for a large number of users. All data uploaded will be immediately available for public download. Mersenne number related data ONLY! (If you're in doubt, _ask me_). Accounts are provided for personal use only, and provided for ftp access - upload to the user's personal filestore, and download from public areas - only. System access will be logged. Any misuse will result in immediate withdrawal of the account, and removal of any data associated with the account. Users agree that they are legally responsible for the content of data uploaded to their filestore - under UK law, in addition to laws in force at the user's point of access to the network. This system is not secure, so keep a secure local copy of your data! At present there is 500 MBytes of filestore available. I may be able to provide more, if reasonable need becomes apparent. I may also be able to provide a "mirror" service - where the system would fetch a predetermined list of files from a remote system at a fixed time, not more frequently than weekly. Regards Brian Beesley _________________________________________________________________ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers ------------------------------ End of Mersenne Digest V1 #636 ******************************