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
******************************
