Mersenne Digest              Friday, 1 May 1998         Volume 01 : Number 354


----------------------------------------------------------------------

From: "Tim Charron" <tcharron@ctfinance.com>
Date: Thu, 30 Apr 1998 16:29:16 -0400
Subject: Re: Mersenne: Another test other than Lucas-Lehmer

> In <URL:news:local.mersenne> on Mon 27 Apr, Charles F. Kerchner III wrote:
> 
> Its probably quicker to calculate 3^(2^(n-1)) and check for the result
> being +/-3  at the end
> 
>   x = 3;
>   for (i = 0; i < p; i++)
>   {
>       x = (x * x) mod Mn;
>   }
>   if (x == 3 || x == p - 3)
>   {
>       /* its a probable prime... */
>   }
> 
> I tried this test on the n=1...1000 and it was 100% accurate.

First, shouldn't that limit be "i < p-1"?

This looks a lot like an algorithm for applying Fermat's little 
theorem. (if q is prime and a is a positive integer with q not 
dividing a, then a^(q-1)=1 mod q).  Note that the extension 
of Fermat's little theorem (a^q=a mod q for all a if q is prime)
implies that there is no restrictions on the choice of a.

The last 'x' calculated in the loop above is 3^2^(p-1).  Consider the
extension of Fermat's little theorem with a=3, q=Mn=2^p-1.  Then we
have 3^(2^p-1)=3 mod Mn.  Multiply both sides by 3 to get 3^2^p=9 mod
Mn.  Add another iteration to the loop above (which now makes the stop
condition "i<p") and we have a test based solely on Fermat's little
theorem.  ie: Mn=2^p-1 is a probable prime if 3^2^p=9 mod Mn.

Fermat's little theorem holds for any prime q, but if it holds, 
there's no implication that q is prime.  So, this is only a probable
prime test, not a prime test.  Please correct me if this is wrong.

> I can't see a way of making this significantly faster than the LL
> test though!

This algorithm has p multiplacations mod Mn.
LL uses p multiplacations mod Mn and p subtractions mod Mn.

Relatively insignificant improvement.  Especially if it's only a
probable prime test.

- -- Tim
Tim Charron
timc@distributed.net
tcharron@ctfinance.com
http://www.interlog.com/~tcharron/

An idle computer is a terrible thing!  http://www.distributed.net/

------------------------------

From: "Clark B. Wierda" <cbw@io.com>
Date: Thu, 30 Apr 1998 16:35:56 -0500 (CDT)
Subject: Mersenne: Swap Thrashing

This is actually quite common on Win95 systems.  The problem is that Win95
is constantly resizing you swap space based on remaining free space on
your disk drive.

The solution is to define a fixed swap file size (usually recommended as 2
1/2 times the physical memory).

Clark B. Wierda    URL: http://www.io.com/~cbw/    cbw@io.com


------------------------------

From: STL137 <STL137@aol.com>
Date: Thu, 30 Apr 1998 19:41:55 EDT
Subject: Mersenne: Moo

Hello all.
<<What is so special about prime numbers? What is their mystery?
I'm not talking about the fact, that their only divisors are 1 and
themselves. I'm interested in the philosophical impact on prime numbers.>>
Okey dokey.
<<In his book 'contact' Carl Sagan e.g. wrote, that the aliens would use
prime numbers to get in contact with planet earth because their origin
could not only be not natural, but would also require a certain level of
intelligence to either send or detect them.>>
Yes, that is a commonly proposed way for interplanetary messages to start, one
that I agree with. Prime numbers are fascinating to us hairless primates, and
we don't know why. Human brains love to find order, and the primes are best
for this: really random, but with smidges of order here and there to tantalize
us.
<<During my surfing sessions I also came across some articles which dealt
with the connection between prime numbers and nucleotid bases, and I would
also be very interested in that subject, too.>>
That, I believe, is human brains trying TOO HARD to see order and connections.
<<1. If primes are the foundation of all integers, are they the
foundation of all (numeric) logic, too? Without primes, were we more
limited? Or is a world without primes completely beyond imagination?>>
Yeah. Can't imagine a world w/o primes.  Prime numbers are built into the
logic of our universe.
<<2. If primes are getting harder to find (the bigger they get?), could
there be a final prime?>>
No, this question is millenia old, and it was solved millenia ago. There are
infinitely many prime numbers, and a simple 6th grader proof (that is never
taught in public schools anyway).
<< And is there a connection between this
question and the aspect of physics dealing with endless time and
space?>>
No.
<<3. Is there a scheme to be found in the spaces between one prime
number and their follow-up? If the spaces get bigger, is that
happening on a regular basis?>>
Again, as before:
It is unpredictable on a small scale, but not on a large. You can say approx
what it will be, but not exactly. Like a coin. You can say 50% heads, 50%
tails, but as for any one flip....?
<<4. Talking about Cryptology: in Carl Sagan's novel 'contact' it is
said, that prime numbers are something very artificial, something that
a galaxy, or a pulsar, e.g. could not send.>>
Yes. Simple, but no method other than intelligence can produce them. You don't
see prime numbers in radio waves naturally.
<<Well, I hope I don't get too far in this case, but IF prime numbers are
artificial, what does that indicate? Artificialty must be created, so does
their mere
existance indicate a creator?>>
No, absolutely not. Prime numbers are NATURAL. But they need intelligence to
be transmitted as radio waves. (Prime numbers do exist in nature, in a few
places). If we heard prime radio waves, we'd know *something* intelligent is
out there.
5. Do You know anything about Twin Primes? Did anyone come up with a
theory so far? 
A little bit, but again, little is known.
<<Dear all  Many students in high school  ask me 1 and 2 is prime number.
Answer please.>>
1 is not. 2 is.
STL137
Obsessed Fanatic

------------------------------

From: "Scott Kurowski" <kurowski@entropia.com>
Date: Thu, 30 Apr 1998 21:03:13 -0700
Subject: Mersenne: RE: Mersenne Digest V1 #353

Hi,

> I'm a film student from Germany and currently I am
> doing some research for a novel which deals with some
> aspects of physics concerning the philosophical side
> of natural sciences in general and prime numbers in
> particular, and probably even their impact on
> every-day-life.

> 1. If primes are the foundation of all integers, are
> they the foundation of all (numeric) logic, too?

Godel's undecidability theorems use prime powers of primes as the
mapping mechanism between mathematics and unique sentences in formal
logic systems.  There's plenty of readable philosophy surrounding
implications of this work.

There's also some interesting connections between the spectra of quantum
system states and the Riemann Zeta function, which has roots directly
related to the prime numbers.  They apparently share distribution
statistics (AAAS Science, around May 1997).



> 4. Talking about Cryptology: in Carl Sagan's novel 'contact' it is
> said, that prime numbers are something very artificial, something that
> a galaxy, or a pulsar, e.g. could not send. Well, I hope I don't get
> too far in this case, but IF prime numbers are artificial, what does
> that indicate? Artificialty must be created, so does their mere
> existance indicate a creator?

Some thoughts:

A series of prime numbers is virtually impossible to generate in
'normal' natural systems, which operate according to so-called laws of
thermodynamics.  The action of factoring numbers into primes is related
to the concept of undoing entropy.  These laws describe how natural
systems always increase entropy on the largest scales.  Let me explain
this crazy idea:

Very loosely, entropy is how likely a system is random or homegeneous.
To know a number is prime requires a decidable logic system test (a
finite number of steps with a terminating algorithm); obvious examples
are factor sieves and Lucas-Lehmer.  Driving the steps of the test
requires a real energy flow (work) to produce the intermediate and final
results.  As such, to determine that a number is prime is a kind of
undoing the local entropy of the test system. (Local because entropy
must increase elsewhere as a tradeoff - heat flows from your computer,
increasing global entropy.)

In the end, you have a prime/not prime decision, a fact, or piece of
information, derived most unnaturally, or at least very improbably by
natural means.  A naturally derived prime result becomes more unlikely
as the prime gets larger, because the number of steps to decide its
primality cost more and more energy - and nature doesn't work that way
(those laws again).

Keep in mind that natural systems randomly 'generate' numbers depending
on how we measure something, so getting a single prime value as a
measured dimension is, by itself, meaningless.  If, however, you
measured a series of consecutive primes, the odds of that being natural
in origin (naturally undone entropy) are for all practical purposes
zero.


Regards,

- -scott






------------------------------

From: Rjpresser <Rjpresser@aol.com>
Date: Thu, 30 Apr 1998 23:59:00 EDT
Subject: Re: Mersenne: Moo

In a message dated 4/30/98 8:09:58 PM Eastern Daylight Time, STL137@aol.com
writes:

> <<Well, I hope I don't get too far in this case, but IF prime numbers are
>  artificial, what does that indicate? Artificialty must be created, so does
>  their mere
>  existance indicate a creator?>>
>  No, absolutely not. Prime numbers are NATURAL. But they need intelligence
to
>  be transmitted as radio waves. (Prime numbers do exist in nature, in a few
>  places). If we heard prime radio waves, we'd know *something* intelligent
is
>  out there.
>  

Hmm.  I remember playing with Conway's game of Life a while back, and seeing
someone's pattern which produced a Sieve of Eratosthenes.  If you know
anything about the game of Life, very briefly it emitted a stream of gliders
and glider-eaters simultaneously, with the 1st glider eater eating every 2nd
glider, the 2nd eating every 3rd, the 3rd eating every 4th, etc .... so that
gliders corresponding to composite numbers were always eaten, and only primes
got through.

The reason I bring this up is that if it can be simulated in a cellular
automaton, are we 100% certain that it could never occur in nature?  Evidence
of a controlled nuclear fission chain reaction (damped by natural rock
formations) has been found, why not cellular automatons?  OK, I'm just
dreaming ....
- --
Ross Presser

------------------------------

From: George Woltman <woltman@magicnet.net>
Date: Thu, 30 Apr 1998 23:19:13 -0400
Subject: Mersenne: Prime95 version 16

Hi all,

A beta of version 16 of prime95 is now available.  You can
download it from http://www.magicnet.net/~woltman/prime95.zip
The URL is not listed anywhere else, so do not delete this email
if you intend to try the new version.

These are the new features:

1)  Prime95 can now test exponents up to 20.5 million.
2)  Prime95 can now find factors up to 2^64.
3)  The program now reports to the PrimeNet server new completion dates
    every 28 days (actually user adjustable from 1 to 60 days).  This will
    improve the reclaiming of exponents that are not being actively tested.
4)  The program now reports the current iteration number to the server
    for more informative status reports.
5)  Intermediate files are now less likely to fail.  If an error occurs
    during the writing of an intermediate file, the program continues on
    trying to write the intermediate file every 10 minutes.
6)  A bug in the rolling average code has been fixed.  Prime95 now modifies
    the rolling average when factoring too.
7)  The prime.log file is now limited in size to 256K bytes.
8)  The user information dialog box now has a checkbox to tell the server
    not to send email.
9)  Setting LockUserInfo=1 in prime.ini will make the user information
    dialog box inaccessible.
10) Trying to run a second copy of prime95 will now start the already
    running copy of prime95.  This makes the Hide Icon feature a bit more
    useful.

Upgrading is easy, just replace your version 15 files with the new files.
Do not upgrade if you are testing an exponent below 1.35M - the 64K FFT code
has been deleted.

Warning:  I do not recommend using prime95 to test exponents above 
10 million.  Reason #1:  I think the cache usage is not optimal for exponents
above 10 million.  Reason #2:  Assuming it is possible to write 65-bit
factoring code that is only twice as slow as 64-bit factoring code, then
exponents above 13 million should be factored to 2^65.  However, if you
insist on testing the really big exponents send me some email and I'll
send you some exponents (use the Advanced/Time menu choice to see how
long these big exponents will take on your computer).

If no major problems are reported with this beta over the next few weeks,
then I will make it available from the free software web page.

Best regards,
George


------------------------------

From: "William H. Geiger III" <whgiii@invweb.net>
Date: Fri, 01 May 98 03:10:36 -0500
Subject: Re: Mersenne: Moo

- -----BEGIN PGP SIGNED MESSAGE-----

In <bfddde1.35494885@aol.com>, on 04/30/98 
   at 11:59 PM, Rjpresser <Rjpresser@aol.com> said:

>Hmm.  I remember playing with Conway's game of Life a while back, and
>seeing someone's pattern which produced a Sieve of Eratosthenes.  If you
>know anything about the game of Life, very briefly it emitted a stream of
>gliders and glider-eaters simultaneously, with the 1st glider eater
>eating every 2nd glider, the 2nd eating every 3rd, the 3rd eating every
>4th, etc .... so that gliders corresponding to composite numbers were
>always eaten, and only primes got through.

>The reason I bring this up is that if it can be simulated in a cellular
>automaton, are we 100% certain that it could never occur in nature? 
>Evidence of a controlled nuclear fission chain reaction (damped by
>natural rock formations) has been found, why not cellular automatons? 
>OK, I'm just dreaming ....

Intresting that you bring this up. One of the first programs I ever wrote
was a computerized game of Life on a Comadore Pet back in '79. Hmmmm I
should see if I still have the code around somewhere and update it for my
Pentium.

 *
  *
***

Anyone know what the longest r-Pentomino has ever been alowed to run? Does
it ever reach a steady-state?



- - -- 
- - ---------------------------------------------------------------
William H. Geiger III  http://users.invweb.net/~whgiii
Geiger Consulting    Cooking With Warp 4.0

Author of E-Secure - PGP Front End for MR/2 Ice
PGP & MR/2 the only way for secure e-mail.
OS/2 PGP 5.0 at: http://users.invweb.net/~whgiii/pgp.html
- - ---------------------------------------------------------------
 
Tag-O-Matic: Speed Kills - Use Windows!

- -----BEGIN PGP SIGNATURE-----
Version: 2.6.3a-sha1
Charset: cp850
Comment: Registered_User_E-Secure_v1.1b1_ES000000

iQCVAwUBNUmHCY9Co1n+aLhhAQG9AgQAnAi0+JHbquFngXShjIzekXg+D4/4Xv11
SgBCXCeeN5IJ3CxKM3Va1MtOsQ2eEsTZ0JJXo+qo9wXfiYnqGjgVGy30YwcHKCwz
/ABNMTPARs9qTeky/rMEOeKnXYzClHJKXPxqTCBSTyMAqhJp58ztMJUURSK1fVvp
2WWqw1Th02c=
=j64l
- -----END PGP SIGNATURE-----


------------------------------

From: Paul Leyland <pleyland@microsoft.com>
Date: Fri, 1 May 1998 01:24:17 -0700 
Subject: RE: Mersenne: Moo

This is getting really far from the proper subject matter of the list but
here goes anyway.

> From: Rjpresser [mailto:Rjpresser@aol.com]

> Hmm.  I remember playing with Conway's game of Life a while 
> back, and seeing
> someone's pattern which produced a Sieve of Eratosthenes.  If you know
> anything about the game of Life, very briefly it emitted a 
> stream of gliders
> and glider-eaters simultaneously, with the 1st glider eater 
> eating every 2nd
> glider, the 2nd eating every 3rd, the 3rd eating every 4th, 
> etc .... so that
> gliders corresponding to composite numbers were always eaten, 
> and only primes
> got through.
> 
> The reason I bring this up is that if it can be simulated in 
> a cellular
> automaton, are we 100% certain that it could never occur in 
> nature?  Evidence
> of a controlled nuclear fission chain reaction (damped by natural rock
> formations) has been found, why not cellular automatons?  OK, I'm just
> dreaming ....

It's relatively straightforward to show that Life is capable of emulating a
Turing Machine, and so can perform any computation which may be performed by
a TM.  It's widely believed that a TM captures the essence of any real
computer, so it's not surprising that a Life colony can calculate primes.
Many other cellular automata, some much simpler than Life, have also been
shown to be capable of emulating a TM.

There are those that believe the universe *is* a cellular automaton.  Think
about quantized space-time, and see if you can reproduce their reasoning...


Paul

------------------------------

From: Paul Leyland <pleyland@microsoft.com>
Date: Fri, 1 May 1998 01:29:29 -0700 
Subject: RE: Mersenne: RE: Mersenne Digest V1 #353

> In the end, you have a prime/not prime decision, a fact, or piece of
> information, derived most unnaturally, or at least very improbably by
> natural means.  A naturally derived prime result becomes more unlikely
> as the prime gets larger, because the number of steps to decide its
> primality cost more and more energy - and nature doesn't work that way
> (those laws again).

Ha!  This old fallacy refuses to die.

While your argument is correct if your computer uses irreversible steps in
its computation, energy is *not* required if reversible processes are used.
In principle, we know how to build reversible computers.

This fallacy most often appears in discussions of cryptographic key
searching, where it is mistakenly argued that the minimum energy to search a
suitably large key space is larger than the rest mass of the observable
universe.


Paul

------------------------------

From: "Scott Kurowski" <kurowski@entropia.com>
Date: Fri, 1 May 1998 01:47:34 -0700
Subject: RE: Mersenne: RE: Mersenne Digest V1 #353

Hi Paul,

> > (those laws again).
>
> Ha!  This old fallacy refuses to die.
>
> While your argument is correct if your computer uses
> irreversible steps in
> its computation, energy is *not* required if reversible
> processes are used.
> In principle, we know how to build reversible computers.

A Carnot cycle CPU?

What are the chances of one forming naturally?


> This fallacy most often appears in discussions of cryptographic key
> searching, where it is mistakenly argued that the minimum
> energy to search a
> suitably large key space is larger than the rest mass of the
> observable
> universe.
>
>
> Paul


So much for armchair thoughts.
Thank goodness for reviewers.  :-)

Regards,

- -scott




------------------------------

From: "Scott Kurowski" <kurowski@entropia.com>
Date: Fri, 1 May 1998 01:47:34 -0700
Subject: RE: Mersenne: RE: Mersenne Digest V1 #353

Hi Paul,

> > (those laws again).
>
> Ha!  This old fallacy refuses to die.
>
> While your argument is correct if your computer uses
> irreversible steps in
> its computation, energy is *not* required if reversible
> processes are used.
> In principle, we know how to build reversible computers.

A Carnot cycle CPU?

What are the chances of one forming naturally?


> This fallacy most often appears in discussions of cryptographic key
> searching, where it is mistakenly argued that the minimum
> energy to search a
> suitably large key space is larger than the rest mass of the
> observable
> universe.
>
>
> Paul


So much for armchair thoughts.
Thank goodness for reviewers.  :-)

Regards,

- -scott




------------------------------

From: Paul Leyland <pleyland@microsoft.com>
Date: Fri, 1 May 1998 01:50:23 -0700 
Subject: RE: Mersenne: Moo

>  *
>   *
> ***
> 
> Anyone know what the longest r-Pentomino has ever been alowed 
> to run? Does
> it ever reach a steady-state?

After 1105 generations it reduces to a few gliders (four I think, but it's
almost 15 years since I last ran it) and a bunch of blocks, blinkers and the
like.

If you get a Life, try a line of 41.  It gives a nice end result.

That's a sign of a mis-spent youth --- being able to say what an initial
life colony evolves into, even after 15 years.


Paul

------------------------------

From: Nick Craig-Wood <ncw1@axis.demon.co.uk>
Date: Fri, 1 May 1998 09:46:50 +0100 (BST)
Subject: Re: Mersenne: Another test other than Lucas-Lehmer

Tim Charron wrote:

> Nick Craig-Wood wrote:
> > 
> > Its probably quicker to calculate 3^(2^(n-1)) and check for the result
> > being +/-3  at the end
> > 
> >   x = 3;
> >   for (i = 0; i < p; i++)
> >   {
> >       x = (x * x) mod Mn;
> >   }
> >   if (x == 3 || x == p - 3)
> >   {
> >       /* its a probable prime... */
> >   }
> > 
> > I tried this test on the n=1...1000 and it was 100% accurate.
> 
> First, shouldn't that limit be "i < p-1"?

Yes it should!

> This looks a lot like an algorithm for applying Fermat's little 
> theorem. 

Yes, I noticed that too.

> (if q is prime and a is a positive integer with q not  dividing a, then
> a^(q-1)=1 mod q).  Note that the extension  of Fermat's little theorem
> (a^q=a mod q for all a if q is prime) implies that there is no
> restrictions on the choice of a.
> 
> The last 'x' calculated in the loop above is 3^2^(p-1).  Consider the
> extension of Fermat's little theorem with a=3, q=Mn=2^p-1.  Then we
> have 3^(2^p-1)=3 mod Mn.  Multiply both sides by 3 to get 3^2^p=9 mod
> Mn.  Add another iteration to the loop above (which now makes the stop
> condition "i<p") and we have a test based solely on Fermat's little
> theorem.  ie: Mn=2^p-1 is a probable prime if 3^2^p=9 mod Mn.
> 
> Fermat's little theorem holds for any prime q, but if it holds, 
> there's no implication that q is prime.  So, this is only a probable
> prime test, not a prime test.  Please correct me if this is wrong.

No that's correct, and that was the original point - the above is what the
Rabin probabalistic prime test degenerates to in the case of Mersenne
numbers.

However I suspect that someone who is better at number theory than me could
prove that a composite Mersenne number could never be a psuedo prime to base
3.

> > I can't see a way of making this significantly faster than the LL
> > test though!
> 
> This algorithm has p multiplacations mod Mn.
> LL uses p multiplacations mod Mn and p subtractions mod Mn.
> 
> Relatively insignificant improvement.  Especially if it's only a
> probable prime test.

Yes I'd agree.

There is one idea that shows some promise though.

You can calculate 3^(2^n) in base 3 immediately, then 'all' you need is a
method of reducing this (monstrous number) mod 2^n-1.

I had a rather amusing idea that you would use base 2 in the test and
calculate 2^(2^n-1) mod 2^n-1.  This is very easy to reduce because 2^m mod
2^n-1 = 2^(m mod n) so 2^(2^n-1) mod 2^n-1 = 2^(2^n-1 mod n).  This must be
2 = 2^1 for the test to pass, so 2^n-1 mod n = 1 if Mn is a prime.

Oooh, terribly exciting I thought, this is what I've been after a quick
probabilistic test for Mersenne primes.  However a bit of thought convinced
me that 2^n-1 mod n = 1 is true whenever n is a prime or pseudo prime to
base 2.  2^n-1 mod n = 1 => 2^n mod n = 2 which is Fermats test to base 2
for n!

- -- 
Nick Craig-Wood
ncw1@axis.demon.co.uk
http://www.axis.demon.co.uk/


------------------------------

From: "Tim Charron" <tcharron@ctfinance.com>
Date: Fri, 1 May 1998 11:06:25 -0400
Subject: Re: Mersenne: Another test other than Lucas-Lehmer

> > This looks a lot like an algorithm for applying Fermat's little 
> > theorem. 
> 
> Yes, I noticed that too.
> 
> > (if q is prime and a is a positive integer with q not  dividing a, then
> > a^(q-1)=1 mod q).  Note that the extension  of Fermat's little theorem
> > (a^q=a mod q for all a if q is prime) implies that there is no
> > restrictions on the choice of a.
> > 
> > The last 'x' calculated in the loop above is 3^2^(p-1).  Consider the
> > extension of Fermat's little theorem with a=3, q=Mn=2^p-1.  Then we
> > have 3^(2^p-1)=3 mod Mn.  Multiply both sides by 3 to get 3^2^p=9 mod
> > Mn.  Add another iteration to the loop above (which now makes the stop
> > condition "i<p") and we have a test based solely on Fermat's little
> > theorem.  ie: Mn=2^p-1 is a probable prime if 3^2^p=9 mod Mn.
> > 
> > Fermat's little theorem holds for any prime q, but if it holds, 
> > there's no implication that q is prime.  So, this is only a probable
> > prime test, not a prime test.  Please correct me if this is wrong.
> 
> No that's correct, and that was the original point - the above is what the
> Rabin probabalistic prime test degenerates to in the case of Mersenne
> numbers.
> 
> However I suspect that someone who is better at number theory than me could
> prove that a composite Mersenne number could never be a psuedo prime to base
> 3.

I've verified that this test "works" for all Mp where p<10000, so I 
suspect that you're right.

The other thing worth pointing out with this test is that it's more 
concise.  All you need is to calculate 3^(2^p) mod Mp.  If the 
result is 9, it's prime.  Basically, if you can find an efficient 
algorithm for modular exponentiation, then you have an efficient 
method of testing Mersenne numbers for primality.

Using FreeLip, I was able to write a mersenne test in about 9 
lines (after declarations).  This test had identical speed as my
freelip LL algorithm for exponents in the 5000-10000 range.

   zintoz(2, &Mp);
   zsexp(Mp, p, &Mp1);
   zsadd(Mp1, -1, &Mp);
   zintoz(3, &x);
   zsq(x, &asqared);
   zexpmod(x, Mp1, Mp, &temp);
   zsubmod(temp, asqared, Mp, &x);
   if ( ziszero(x)) printf("M%d is prime.\n",p);
   if (!ziszero(x)) printf("M%d is composite.\n",p);

I've seen papers discussing fast hardware modular exponentiation.  
I'm not sure if there are software algorithms that are better than 
n iterations of a fast modular multiply routine.  If there are, then 
this method offers significant potential.  Even if it's only a 
probable prime test, any benefit would be multiplied across all 
machines running the test.  If a probable was found, then two 
machines would be used to independently run the LL test.

- -- Tim
Tim Charron
tcharron@ctfinance.com
tcharron@interlog.com

------------------------------

From: Jean-Luc Cooke <jlcooke@ottawa.com>
Date: Fri, 01 May 1998 13:16:17 -0400
Subject: Re: Mersenne: Moo

This is a multi-part message in MIME format.
- --------------07B14173F4EEC05005B53E64
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

I think this topic is much needed for this mailing group.  Not that the
technical side of primes isn't interesting, but I feel that having an
open discussion at to WHY each of us are working at this is an important
thing to do.

And Paul, I don't like your email address!  :)

TTYL

JLC

Paul Leyland wrote:
> 
> This is getting really far from the proper subject matter of the list but
> here goes anyway.
> 
> > From: Rjpresser [mailto:Rjpresser@aol.com]
> 
> > Hmm.  I remember playing with Conway's game of Life a while
> > back, and seeing
> > someone's pattern which produced a Sieve of Eratosthenes.  If you know
.....
.....

- -- 
Jean-Luc Cooke
Carleton University, Electrical Engineering

There is a 90% chance that right at this moment I am doing Calculus.
God damn Newton, damn him to hell!

- ----------------------------------------------------------------------
  AOL-IM ID: JLinOTTAWA   Get one: register.netscape.oscar.aol.com
- ----------------------------------------------------------------------
         ICQ# 4474419           Get it:  www.mirabilis.com
- ----------------------------------------------------------------------
                    Email addresses
                   jlcooke@ottawa.com
jlcooke@magma.ca                   jlcooke@magmacom.com
jlcooke@engsoc.carleton.ca         jlcooke@chat.carleton.ca
- ----------------------------------------------------------------------
- --------------07B14173F4EEC05005B53E64
Content-Type: text/x-vcard; charset=us-ascii; name="vcard.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Jean-Luc Cooke
Content-Disposition: attachment; filename="vcard.vcf"

begin:          vcard
fn:             Jean-Luc Cooke
n:              Cooke;Jean-Luc
org:            Carleton University
adr:            270A Dalehurst Dr.;;;Nepean;ON;K2G 4M8;Canada
email;internet: jlcooke@ottawa.com
title:          Electrical Engineering Student
tel;work:       na
tel;fax:        na
tel;home:       na
note:           My web page address is: www.engsoc.carleton.ca/~jlcooke/
x-mozilla-cpt:  ;0
x-mozilla-html: TRUE
version:        2.1
end:            vcard


- --------------07B14173F4EEC05005B53E64--


------------------------------

End of Mersenne Digest V1 #354
******************************