[extropy-chat] new mersenne prime?

[spike]

> -----Original Message-----
> From: extropy-chat-bounces at lists.extropy.org [mailto:extropy-chat-
> bounces at lists.extropy.org] On Behalf Of Samantha Atkins
> Sent: Thursday, December 22, 2005 12:10 PM
> To: ExI chat list
> Subject: Re: [extropy-chat] new mersenne prime?
> 
> Really?  Cool!  :-)
> 
> Yeah, I figured it would be nearly impossible.  I need to do some
> reading on precisely why it is easier to prove Mersenne primes.  A
> refresh on modular arithmetic would be helpful.
> 
> On the number of digits in your new candidate shouldn't
> floor( e * log(2, 10)) + 1
> where e is your exponent give it to you?
> 
> - samantha


In general the computational complexity of determining
primeness of any number n by brute force factoring 
increases as a polynomial of n.  But if n is a Mersenne 
number (of the form 2^n-1 where n is prime) then
the computational complexity to determine primeness
increases as 2*log(n).  

Currently humanity is exploring nature in the 
2^30,000,000 range.  This takes about a month with a 
typical modern desktop confuser.  But to determine
the primeness of a number of this magnitude that is
not a Mersenne number would take more time than
we have left before universal heat death, even
if every atom in the visible universe were a PC
dedicated to the task.

There are other classes of numbers that have 
computational shortcuts to determine primeness,
but the Mersenne numbers have the very best shortcut
known, the Lucas-Lehmer algorithm.  This is used by
GIMPS to exhaustively check mersenne numbers for
primeness.  This leads to the conjecture that for the
entire future of thought, the largest known prime
will always be a Mersenne prime.  We already know
of 42 Mersenne primes, with the 43rd probably
discovered on 16 December 2005.

Samantha, were you to discover a method of
determining primeness of large non-mersenne numbers,
you would not only become a math goddess of unequaled
magnitude, you would also destabilize the world's
economic security systems.  People could no longer
trust that you wouldn't also discover a means of
factoring 200 digit composites made of two 100
digit primes.  No bank account would be safe.  The 
CIA would need to have you slain to keep you from 
talking, and then have me slain in case you shared 
with me the formula before you perished.  {8^D

spike