Mersenne Digest Thursday, 28 January 1999 Volume 01 : Number 501
----------------------------------------------------------------------
From: "Ernst W. Mayer" <[EMAIL PROTECTED]>
Date: Tue, 26 Jan 1999 14:10:27 -0500
Subject: Mersenne: Meganet's alleged fast primality prover
Some folks at an outfit called Meganet Corporation claim to have
developed a rigorous primality prover that runs as fast a pseudoprime test.
See their ballyhooing at http://www.meganet.com/primality.htm.
An excerpt:
MAJOR WORLDWIDE MATHEMATICAL
BREAKTHROUGH MEGANET CORPORATION
DEVELOPED FAST 100% DETERMINISTIC PRIME
NUMBER TESTING. IT IS THE ONLY
DETERMINISTIC ALGORITHM IN THE WORLD
TO WORK IN POLYNOMIAL TIME.
Meganet Corporation have announced the result of 13
years of Research & Development in the prime number
testing area the world's first and only POLYNOMIAL
TIME, 100% DETERMINISTIC PRIMALITY
TESTING. It is NOT a probabilistic test like the other
algorithms in the market, but 100% deterministic. The
algorithm is in POLYNOMIAL TIME, therefore much
faster than even the probabilistic algorithms. Meganet
Corporation have implemented the algorithm in an
ANSI C application running on a single CPU 450 MHz
PC Computer. Some sample results:
1,000 bits primality test {timing obscured}
{snip}
7,000 bits primality test 1:01min
10,000 bits primality test 1:58min
Those results are unheard of. The 1,000 bits test on a
Sparc II workstation takes 5 Minutes and it is still only
PROBABALISTIC. The gap in time is much greater for
larger bit sizes.
The major breakthrough is solving a 400 year old
mathematical problem how to positively identify a
prime number without spending exponential time in
dividing the number by all the primes up to its root. The
solution Meganet Corporation have developed is based
on a newly designed Mathematical Sequence called the
T-Sequence. Once a number is transformed to the
T-Sequence, its quadratic residue has definitive
characteristics if it's a prime number that can be easily
determined in polynomial time by performing a binary
decomposition.
Meganet Corporation would like to emphasize that there
is a 100% mathematical proof behind their T-Sequence,
and further, it is a complete working product tested
successfully on over 1.3 million numbers without a single
mistake.
Of course they won't give out any details about the maths behind the method,
assuring us that a licensed practical mathematician is evaluating their claims,
which seems to fall a tad short of normal peer review. As Paul Jobling noted
in a posting to Chris Caldwell's Primes-List:
>I sent a mail to Meganet regarding their primality proving claims and
>received the following reply:
>>Hi,The Meganet Primality Test is currently being evaluated by a reputable
>>mathematician - when he'll finish his evaluation and endorse it (in about 2
>>weeks) we'll make it public.
>>We'll notify you by email and publish it on the web site.
>>Thank you for your interest in Meganet.
To which Mark Coffey replied:
>Three things about this statement by Meganet strike me as intersting:
>1) They did not see fit to name the "reputable mathematician"
>2) They already know that he will finish testing in two weeks
>3) They already know that he will endorse the test
>
>Oh and I guess a fourth would be the horrendous grammar in their reply.
I also note that near the bottom of the page, they make a statement that
seems to indicate theirs is in fact a probable-prime test (issues of
grammar aside):
Meganet Corporation is seeking for companies
interested in this algorithm which generates large
industrial grade prime numbers at record speeds, and
would be glad to demonstrate the technology to any
interested party on request.
Does anyone know more about the "400-year-old problem" they mention,
which would allow us to better judge the likelihood that their method
is rigorous? (I have my doubts.)
- -Ernst
------------------------------
From: Jefferson M Wolski <[EMAIL PROTECTED]>
Date: Tue, 26 Jan 1999 14:23:18 -0800
Subject: Mersenne: SuperComputer
Someone had posted info on building a supercomputer for under $10,000.
Could someone send that to me again please.
Thanks
Jeff Wolski
------------------------------
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Date: Tue, 26 Jan 1999 16:24:55 -0600
Subject: RE: Mersenne: Meganet's alleged fast primality prover
> Does anyone know more about the "400-year-old problem" they mention,
> which would allow us to better judge the likelihood that their method
> is rigorous? (I have my doubts.)
>
> -Ernst
I also have suspicions after reading this.
Regarding the 400-year-old problem, this sounds almost EXACTLY like the
oft-used phrase in all the newspaper articles about me. It has to do with
the fact that Marin Mersenne was born just over 400 years ago.
Why the papers decided it was a 400-year-old problem is beyond me.
But since these wonderfully gifted mathemeticians have come up with this
wonderful theorem and yet still refer to prime hunting as a 400-year-old
problem, well something's wrong with this picture.
Aaron
------------------------------
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Date: Tue, 26 Jan 1999 16:27:52 -0600
Subject: Mersenne: Rewards for prime stuff??
Fellow prime number hunters,
I was wondering...Primenet offers a reward for the next Mersenne prime
found, but are there any other interesting things we could offer rewards
for?
Perhaps for the smallest factor of some Mersenne number or something?
Reason I ask is that I may be interested in fronting some money for such an
endeavor, in order to spur some more interest.
I had considered pooling some money with what Primenet offers, but I wanted
to see if there was some other direction to go that would be just as
interesting but not necessarily involves finding the next prime.
I think this idea was discussed previously but I don't remember for sure.
Aaron
------------------------------
From: "Ethan Hansen" <[EMAIL PROTECTED]>
Date: Tue, 26 Jan 1999 19:01:37 -0800
Subject: RE: Mersenne: Meganet's alleged fast primality prover
Ernst Mayer wrote:
>
> Some folks at an outfit called Meganet Corporation claim to have
> developed a rigorous primality prover that runs as fast a
> pseudoprime test.
[Lots of ad copy deleted]
> See their ballyhooing at http://www.meganet.com/primality.htm.
> I also note that near the bottom of the page, they make a statement that
> seems to indicate theirs is in fact a probable-prime test (issues of
> grammar aside):
>
> Meganet Corporation is seeking for companies
> interested in this algorithm which generates large
> industrial grade prime numbers at record speeds, and
> would be glad to demonstrate the technology to any
> interested party on request.
>
> Does anyone know more about the "400-year-old problem" they mention,
> which would allow us to better judge the likelihood that their method
> is rigorous? (I have my doubts.)
>
These folks have offered an interesting sounding cryptography program for
the last couple of years. The algorithm appears to be based on a single
very large prime (1E6 bits -- shared among all users???), and one or more
2048 bit numbers. They claim their algorithm is "unbreakable by design."
Doubtful. Computationally difficult is likely a better description.
Read http://www.meganet.com/intro.htm for some more wonderful items. I
never knew encryption was so sensual. They make a distinction between "a
computer used to send a secure massage and a computer used to receive a
secure massage." I think our cyber revolution has gone one step too far...
- -Ethan
------------------------------
From: brandon j whitehead <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 00:16:03 -0600
Subject: Re: Mersenne: Meganet's alleged fast primality prover
>
> The major breakthrough is solving a 400 year old
> mathematical problem how to positively identify a
> prime number without spending exponential time in
> dividing the number by all the primes up to its root.
hmm it seems to me that they're getting ahead of themselves. if they're
talking about the 'prime number problem' in general, it's been around
since at least 200 BC or so. should we trust someone who thinks that
just 400 years ago it was200 BC?
DriverDown
___________________________________________________________________
You don't need to buy Internet access to use free Internet e-mail.
Get completely free e-mail from Juno at http://www.juno.com/getjuno.html
or call Juno at (800) 654-JUNO [654-5866]
------------------------------
From: Paul Leyland <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 02:32:57 -0800
Subject: RE: Mersenne: Rewards for prime stuff??
> I was wondering...Primenet offers a reward for the next Mersenne prime
> found, but are there any other interesting things we could
> offer rewards
> for?
>
> Perhaps for the smallest factor of some Mersenne number or something?
How about the *largest* factor found by the Elliptic Curve method?
Trial division peters out somewhere below 70 bits, which is still only
20-something digits. Conrad Curry has found a 53-digit factor of M677, so
offer an award for the first person to find a larger factor. Conrad's
record is by far the largest factor reported to have been found by ECM.
Paul
------------------------------
From: "Brian J Beesley" <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 11:10:43 GMT
Subject: Re: Mersenne: Meganet's alleged fast primality prover
> Some folks at an outfit called Meganet Corporation claim to have
> developed a rigorous primality prover that runs as fast a pseudoprime test.
> See their ballyhooing at http://www.meganet.com/primality.htm.
I am extremely sceptical of this claim for several reasons, but open-
minded enough not to reject such a claim completely out-of-hand.
Long ago I "invented" a technique which seemed to be reasonable,
involving a transform from the natural number field onto a subset,
the intention being to effectively carry out sieving to isolate primes
without actually having to carry out the whole operation.
Unfortunately I couldn't get it to work, and eventually learned
enough math to realise why. However, a clever application of a
similar concept just might work.
> [... snip ...]
> I also note that near the bottom of the page, they make a
>statement that
> seems to indicate theirs is in fact a probable-prime test
Now that seems to make more sense. Psuedo-prime testing can
deliver "industrial grade" pseudoprimes, i.e. numbers which are not
neccessarily prime but are very hard to factor.
I wonder what their "rigorous primality prover" would make of a
Carmichael number? (A Carmichael number is a composite number
which is nevertheless pseudoprime to every base. They are rather
rare.) Do we know any Carmichael numbers which are of any
appreciable size, i.e. long enough not to be easily factored by
standard methods?
> Does anyone know more about the "400-year-old problem" they
> mention,
> which would allow us to better judge the likelihood that their > >
method
> is rigorous? (I have my doubts.)
I have my doubts, too. But, does the conjecture that there are an
infinite number of Mersenne primes date back to Mersenne himself?
To the best of my knowledge, this conjecture remains unproved.
Though what it has to do with industrial-grade pseudoprimes useful
for cryptography defeats my imagination.
Regards
Brian Beesley
------------------------------
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 08:35:29 -0600
Subject: RE: Mersenne: Rewards for prime stuff??
> > Perhaps for the smallest factor of some Mersenne number or something?
>
> 3 is a factor of M(4) = 15, I claim the prize, since no-one will ever
> find a smaller prime factor of any Mersenne number ;-)
You got me there. :-) I hadn't worded that so carefully eh?
> Yes, some time ago (?October?) I suggested a prize to encourage
> people to run ECM. What I had in mind was an annual prize for the
> largest prime factor of any Mersenne number discovered using
> Prime95 (or one of its derivatives) during the calendar year. Now
> that the program can factor 2^n+1 as well as 2^n-1, I suppose we
> have to generalize a bit.
That seems to be the idea that was most frequently given in the past 24
hours. Perhaps Scott Kurowski is reading this...maybe he'd like to input
some thoughts since we would probably rely on the Primenet server to find
the winner...
> Also you need to be very careful in the wording of the competition
> rules, to prevent people making silly claims (like mine above!)
Agreed.
> I may be able to contribute some cash as well, at least something
> of the order of $500.
That's about what I was shooting for as well.
So, essentially, we might be talking about something like: a prize to the
person who finds the largest factor using ECM at the end of calendar year
1999? A Y2K prize?
Aaron
------------------------------
From: Michel Lacoursiere <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 12:19:58 -0500
Subject: Mersenne: Rewards for prime stuff??
> 3 is a factor of M(4) = 15, I claim the prize, since no-one will
ever
> find a smaller prime factor of any Mersenne number ;-)
What about 1 ? Isn't it a factor?
Michel Lacoursière
[EMAIL PROTECTED]
------------------------------
From: "Steve" <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 12:33:08 -0500
Subject: Mersenne: Now here's a good idea...
This is a multi-part message in MIME format.
- ------=_NextPart_000_00F2_01BE49F1.3223B720
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Decided to try and hack my kid's Furby after it started talking en =
francais. I found this page which was helpful =
http://www.afu.com/fur.html run by a fellow who has issued a $250 =
challenge to program one of the little buggers.
One particular paragraph caught my eye namely:=20
Once Furby has been hacked, my goal is to give it a Java API allowing =
the device to become a general Java engine. Perhaps it will use the Java =
Speech API. Perhaps it will use the Java Media Framework. Perhaps the =
hacked Furby will become a processor for running Java software that =
looks for Mersenne primes and belches as it finds new ones.=20
Now these things may only have the CPU of an Apple II (true) but there =
are over 2 million of them (so far) and most of the time they sit idle =
when they're not belching. Now if we could figure out how to interpret =
the IR I/O (they communicate with each other via IR), they could =
transmit results to a laptop and thence to Primenet.
Or maybe not!
=20
Steve Gardner
[EMAIL PROTECTED]
www.pcavenue.com
THE On-Line Computer Store
- ------=_NextPart_000_00F2_01BE49F1.3223B720
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD W3 HTML//EN">
<HTML>
<HEAD>
<META content=3Dtext/html;charset=3Diso-8859-1 =
http-equiv=3DContent-Type>
<META content=3D'"MSHTML 4.72.3110.7"' name=3DGENERATOR>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT color=3D#000000 size=3D2>Decided to try and hack my kid's =
Furby after it=20
started talking en francais. I found this page which was helpful =
<A=20
href=3D"http://www.afu.com/fur.html">http://www.afu.com/fur.html</A> run =
by a=20
fellow who has issued a $250 challenge to program one of the little=20
buggers.</FONT></DIV>
<DIV><FONT color=3D#000000 size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>One particular paragraph caught my eye namely: =
</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2><STRONG>Once Furby has been hacked, my goal is to =
give it a=20
Java API allowing the device to become a general Java engine. Perhaps it =
will=20
use the Java Speech API. Perhaps it will use the Java Media Framework. =
Perhaps=20
the hacked Furby will become a processor for running Java software that =
looks=20
for Mersenne primes and belches as it finds new ones. =
</STRONG></FONT></DIV>
<DIV> </DIV>
<DIV><FONT color=3D#000000 size=3D2>Now these things may only have the =
CPU of an=20
Apple II (true) but there are over 2 million of them (so far) and most =
of the=20
time they sit idle when they're not belching. Now if we could =
figure out=20
how to interpret the IR I/O (they communicate with each other via =
IR), =20
they could transmit results to a laptop and thence to =
Primenet.</FONT></DIV>
<DIV><FONT color=3D#000000 size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>Or maybe not!</FONT></DIV>
<DIV><FONT color=3D#000000 size=3D2> </FONT><FONT color=3D#000000=20
size=3D2><BR> =
Steve=20
Gardner<BR> <A=20
href=3D"mailto:[EMAIL PROTECTED]">[EMAIL PROTECTED]</A></FONT></DIV>
<DIV> </DIV>
<DIV><FONT color=3D#000000 size=3D2> =
<A=20
href=3D"http://www.pcavenue.com">www.pcavenue.com</A><BR> THE =
On-Line=20
Computer Store<BR></FONT></DIV></BODY></HTML>
- ------=_NextPart_000_00F2_01BE49F1.3223B720--
------------------------------
From: Henk Stokhorst <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 22:23:30 +0100
Subject: Mersenne: VME
L.S.,
I wrote the following email to VME, and got the response underneath it.
What would be a nice simple test for them, they could run on their
machine?
YotN,
Henk Stokhorst.
- ---
L.S.,
Nice claim, but if it were true you of course would not object to join
GIMPS (www.mersenne.com) and proof your claims...
YotN,
Henk Stokhorst.
- ---
Hi,
We'd love to, but there are 2 things we need to do first:
file for a patent (we're in the process).
make sure nobody will use it unauthorized - we're a commercial company
opting to make money, not just looking for fame.
Please send me more details about joining GIMPS.
Thanks,
Saul.
- ---
------------------------------
From: Paul Victor Novarese <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 16:11:04 -0600 (CST)
Subject: Mersenne: Problems with ATI graphics
Has anyone experienced probelems with ATI graphics cards?
I've been running prime95 on some evaluation machines here and the display
gets fuzzy when prime is running.
- ----------------------------------------------
PGP Fingerprint
413D 8BEE 88B3 087B 630D 30A4 951A A435 3D01 AFF4
[EMAIL PROTECTED]
------------------------------
From: brandon j whitehead <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 16:17:52 -0600
Subject: Mersenne: old prime source code?
i didn't know exactly where to send this, so i sent it here.
i'm new to this prime number scene, and i was wondering if there was some
old c++ source code lying around anywhere that anyone knew of that you
wouldn't mind tossing my way. i've been writing a simple math program,
for experience, fun, and to aid my sisters, and i thought i'd put in a
prime number function. i know (or at least my understanding is) that to
find all the primes less than a number you get rid of all the multiples
of the sq rt of that number. then you're left with primes. well i've
been racking my brains and i can't think of exactly how to do that in
c++. i'm a first-yr programmer, (17 & still in hs), and it's not
surprising to me that i can't figure it out. right now. that's why i
was wondering if there was some code around. i don't want to copy it. i
want to learn from it. DriverDown......Brandon Whitehead
[EMAIL PROTECTED]
ps my version of juno doesn't support attatchments, so please don't send
one or i won't get the message. thanks
___________________________________________________________________
You don't need to buy Internet access to use free Internet e-mail.
Get completely free e-mail from Juno at http://www.juno.com/getjuno.html
or call Juno at (800) 654-JUNO [654-5866]
------------------------------
From: Conrad Curry <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 17:34:46 -0600 (EST)
Subject: Re: Mersenne: Rewards for prime stuff??
>
> Fellow prime number hunters,
>
> I was wondering...Primenet offers a reward for the next Mersenne prime
> found, but are there any other interesting things we could offer rewards
> for?
In a few months, hopefully, M601 will be factored with NFS. We could
have another factor length contest. This would allow everyone a chance to
win and not just those with the most CPU power.
Other contests could be based on complete factorizations (with ECPP
primality certificate), finding factors of 2^p-1 for p<1200, finding 40+
decimal digit factors with ECM, finding factors of M(M(p)), etc.
Of course the pool for the next Mersenne prime could always be
increased. $10,000 for decrypting a message and only $1,500 for a new
Mersenne prime just doesn't right to me :), but then I'm sure most of us
are not in it for the money anyway.
------------------------------
From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]>
Date: Wed, 27 Jan 1999 23:33:20 -0500 (EST)
Subject: Mersenne: Rankings
What is up with http://project.vobis.de/gimps/
I just get
faliled to open configuration file: "/usr/local/Counter/conf/count.cfg"
(where faliled is failed, I presume)
------------------------------
End of Mersenne Digest V1 #501
******************************
