Mersenne Digest Friday, February 11 2000 Volume 01 : Number 692
----------------------------------------------------------------------
Date: Thu, 10 Feb 2000 15:54:14 +0800
From: "Dave Mullen" <[EMAIL PROTECTED]>
Subject: Mersenne: Base-3 Pseudoprimes
This is a multi-part message in MIME format.
- ------=_NextPart_000_001E_01BF73DF.147B7640
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
I was wondering if base-3 pseudo-prime testing might be considerably =
faster than LL testing for Mersenne Primes ?
The base-3 pseudo-prime test is defined as :-
3 ^ P =3D=3D 3 (mod P) where P is a probable-prime (base-3 prp)
3 ^ P <> 3 (mod P) where P is composite
We know that using binary exponentiation saves having to calculate every =
power of 3, just some intermediates and the final required answer ...
e.g. For M(3) =3D 7, (111 in binary), starting with the value 3, square, =
multiply by 3, square, multiply by 3
This is effectively 4 multiplys to get our answer.
If we used this modified form of the test :-
3 ^ (P+1) =3D=3D 9 (mod P)
then we'd only need 3 multiplys i.e. starting with value 3, square, =
square, square.
This situation improves with higher exponents i.e. M(13) =3D 8191, =
(1111111111111 in binary).
Usual method takes 24 multiplys, modified method only takes 13 =
multiplys.
i.e.for a given Mersenne Exponent, usual method takes (Exp * 2) - 2 =
multiplies, modified method takes (Exp) multiplys.
Now, okay, this is still 2 more multiplys than the LL test would take. =
But I believe there must be some advantages.
1) For the LL test using FFT multiplys, we have to Transform the data, =
Multiply the matrices, Inverse Transform the data, then subtract 2. I am =
assuming that the only reason we do the Forward and Inverse Transform =
each time is so we can subtract the 2 ?=20
Please correct me here if I'm wrong !
(by the way, I would appreciate some pointers to FFTs for large integer =
multiplication for idiots - I understand the (very) basic concept, but =
how does the modulus occur automatically, why do we need to scramble the =
data, why does it all work etc.)
2) If we are doing base-3 prps, the only operation we need is multiply - =
so therefore we Transform the start value 3, then multiply the matrix by =
itself as many times as required, then finally do one Inverse Transform. =
This must save a lot of time over traditional LL testing, all those =
Transforms jumping in and out of virtual memory (a lot of us don't have =
128+ MB of RAM !!).
3) The base-3 prp does not prove primality 100%, but it does prove =
compositeness. So we might narrow down our range of potential Mersenne =
exponents more quickly. And if if turns out that when we test the =
remaining exponents, the LL test fails - what the hell, we just found a =
new Carmichael Number - might still be a new record !!
Dave
- ------=_NextPart_000_001E_01BF73DF.147B7640
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 size=3D2></FONT><FONT color=3D#000000 size=3D2>I was =
wondering if base-3=20
pseudo-prime testing might be considerably faster than LL testing for =
Mersenne=20
Primes ?</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>The base-3 pseudo-prime test is defined as =
:-</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>3 ^ P =3D=3D 3 (mod P) where P is a probable-prime =
(base-3=20
prp)</FONT></DIV>
<DIV><FONT size=3D2>3 ^ P <> 3 (mod P) where P is =
composite</FONT></DIV>
<DIV> </DIV>
<DIV><FONT size=3D2>We know that using binary exponentiation saves =
having to=20
calculate every power of 3, just some intermediates and the final =
required=20
answer ...</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>e.g. For M(3) =3D 7, (111 in binary), starting with =
the value 3,=20
square, multiply by 3, square, multiply by 3</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>This is effectively 4 multiplys to get our=20
answer.</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>If we used this modified form of the test =
:-</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>3 ^ (P+1) =3D=3D 9 (mod P)</FONT></DIV>
<DIV> </DIV>
<DIV><FONT size=3D2>then we'd only need 3 multiplys i.e. starting with =
value 3,=20
square, square, square.</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>This situation improves with higher exponents i.e. =
M(13) =3D=20
8191, (1111111111111 in binary).</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>Usual method takes 24 multiplys, modified method =
only takes 13=20
multiplys.</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>i.e.for a given Mersenne Exponent, usual method =
takes (Exp *=20
2) - 2 multiplies, modified method takes (Exp) multiplys.</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>Now, okay, this is still 2 more multiplys than the =
LL test=20
would take. But I believe there must be some advantages.</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>1) For the LL test using FFT multiplys, we have to =
Transform=20
the data, Multiply the matrices, Inverse Transform the data, then =
subtract 2. I=20
am assuming that the <U>only</U> reason we do the Forward and Inverse =
Transform=20
each time is so we can subtract the 2 ? </FONT></DIV>
<DIV><FONT size=3D2>Please correct me here if I'm wrong !</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>(by the way, I would appreciate some pointers to =
FFTs for=20
large integer multiplication for idiots - I understand the (very) basic =
concept,=20
but how does the modulus occur automatically, why do we need to scramble =
the=20
data, why does it all work etc.)</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>2) If we are doing base-3 prps, the only operation =
we need is=20
multiply - so therefore we Transform the start value 3, then multiply =
the matrix=20
by itself as many times as required, then finally do one Inverse =
Transform. This=20
must save a lot of time over traditional LL testing, all those =
Transforms=20
jumping in and out of virtual memory (a lot of us don't have 128+ MB of =
RAM=20
!!).</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>3) The base-3 prp does not prove primality 100%, but =
it does=20
prove compositeness. So we might narrow down our range of potential =
Mersenne=20
exponents more quickly. And if if turns out that when we test the =
remaining=20
exponents, the LL test fails - what the hell, we just found a new =
Carmichael=20
Number - might still be a new record !!</FONT></DIV>
<DIV><FONT size=3D2></FONT> </DIV>
<DIV><FONT size=3D2>Dave</FONT></DIV></BODY></HTML>
- ------=_NextPart_000_001E_01BF73DF.147B7640--
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 03:57:07 -0500
From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]>
Subject: RE: Mersenne: pi
Ken Kriesel, are you sure you did not mistype just ONE digit or parens in
that humongous expression at the end?
At 01:10 AM 2/10/00 -0600, Ken wrote:
>At 08:35 PM 2/9/2000 -0500, <[EMAIL PROTECTED]> wrote:
>>It would take infinite area of an infinitesimally thin layer of paint, which
>>would have no volume due to its thinness. Since paint can't be infinitely
>>thin,
>>this also means you can't actually fill the object with paint, because there
>>will be volume in areas into which paint molecules can't fit.
>>
>>Mike
>
>Filling the horn with paint has a couple additional problems:
>
>since it is an infinitely long capillary, filling time would be infinity^4
>or so (laminar flow conductance being proportional to diameter^4
>and inversely proportional to length)
>
>A realizable section of Gabriel's horn would necessarily be lumpy
>when constructed of real material. Think of a tube constructed
>of soccer balls glued together. If the horn inner diameter is a kilometer,
>great, it looks pretty smooth. (Say for the sake of argument the
>diameter of these soccer balls is 3 decimeters.)
>But further along, where the inner
>diameter has fallen off to one meter, it's beginning to look pretty
>lumpy already, and when inner diameter drops to 1 decimeter,
>the tube roughness is very significant.
>Now move out to where the inner diameter is 1 Angstrom,
>and the atoms of which the wall is constructed are 3 Angstroms
>diameter, and it looks the same.
>
>I'm surprised noone responded about continued fractions to
>Ian Halliday:
>At 10:42 PM 2/9/2000 +1300, [EMAIL PROTECTED] wrote:
>>Over history, there have been numerous other approximations to the value
>>of pi. Our current culture seems to favour 22/7 as an approximation, and
>>the Biblical approximation above suggests 333/106. However, this is not
>>the best available in three digits, which is, so far as I know, 355/113,
>>which is correct to an astonishing one part in ten million. I understand
>>that in certain quarters, 3 1/7 was not in vogue, with 3 1/8 favoured.
>>What, argued these particular mystics, could be a better number than
>>five squared shared by two cubed? N P Smith asked whether we should be
>>more concerned by those who serious propose answers which are clearly
>>wrong or by those who spend time in repeatedly refuting these spurious
>>claims.
>
>PI~=3.1415926535897932384626433832795
>subtract the integer part, take the reciprocal of the rest, and iterate, to
>produce the continued fraction's coefficients.
>Reassemble successively increasing numbers of terms,
>until the rational number obtained is sufficiently accurate.
>This is an effective method of determining gear ratios approximating
>arbitrary reals.
>
>3+ 1 / (7 +
>1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/(14+1/(2+1/(1+...))))
>)))))))
>3= 3
>4= 3 +1
>3.14 2857142857... =3+1/7 = 22/7
>3.1 25 = 3+1/(7+1) = 25/8
>3.1415 09433962264150943396226415... =3+1/(7+1/15) = 3 + 15/106 = 333/106
>3+1/(7+1/(15+1/)) =355/113, see below
>3.141592 9203539823008849557522124... =3+1/(7+1/(15+1/1)) = 3 + 1/(7+1/16)=
>3+1/(113/16) = 3+ 16/113 = 355/113
>3+1/(7+1/(15+1/(1+1)))= 3.1415 525114155251141552511415525
>3+1/(7+1/(15+1/(1+1/292))) = 103993/33102 = 3.141592653 0119026040722614947737
>3+1/(7+1/(15+1/(1+1/293)))= 3.141592653 9214210447087159415927
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/1))))) = 3.141592653 4674367055204547853492
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1)))))) = 3.141592653
>6189366233975003014106
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1))))))) = 3.1415926535
>583573009183052053374
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/2))))))) = 3.14159265358
>10777712044193065819
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1)))))))) = 3.1415926535
>914039784825424142193
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1)))))))))= 3.14159265358
>70561991705458087813
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1/3)))))))))=3.14159265358
>9 3891715436873217069
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1))))))))))=3.1415926
>53589 8153832419437773074
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/2))))))))))=3.14159
>2653589 6274836288508219852
>3+1/(7+1/(15+1/(1+1/(292+1/(1+1/(1+1/(1+1/(2+1/(1+1/(3+1/(1+1/14)))))))))))=
>80143857/25510582=3.14159265358979 26593756269457122
>
>Ken Kriesel, PE <[EMAIL PROTECTED]>
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 12:31:37 -0000
From: "Casey. Noel" <[EMAIL PROTECTED]>
Subject: Subject: Re: Mersenne: pi
>Date: Wed, 09 Feb 2000 10:50:44 -0500
>From: Jeff Woods <[EMAIL PROTECTED]>
>Subject: Re: Mersenne: pi
>You're bumping up against the Fundamental Theorem of Calculus here. Pi
>DOES have a precisely defined value, but you cannot express it in decimal
>form. You can express it as an infinite expansion, however.
>
This is partially correct, but a more intuitive explanation is that:
Pi is defined as the ratio of Perimeter to Diameter of a circle. ( Pi*D/D
)
Since a circle can be considered as a polygon of infinite number of sides,
it follows that the perimeter
is not finite and Pi is not precise accordingly.
Noel Casey
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 09:20:47 -0500
From: "Stephan Grupp" <[EMAIL PROTECTED]>
Subject: Mersenne: non-synchronized old results
I missed the answer in the digest to the question regarding old results
that are left in your Primenet account after a synchronization. I, too,
have wondered about these accumlating old results (although I just
checked my Account Report and they all have miraculously disappeared).
Are those "legacy" exponents counted in your P90 years? Had they been
(NOT to reopen this thread) poached or reassigned in some other way?
- -steve grupp
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 10:37:19 -0500
From: George Woltman <[EMAIL PROTECTED]>
Subject: Re: Mersenne: non-synchronized old results
Hi,
At 09:20 AM 2/10/00 -0500, Stephan Grupp wrote:
>I missed the answer in the digest to the question regarding old results
>that are left in your Primenet account after a synchronization. I, too,
>have wondered about these accumlating old results (although I just
>checked my Account Report and they all have miraculously disappeared).
>Are those "legacy" exponents counted in your P90 years? Had they been
>(NOT to reopen this thread) poached or reassigned in some other way?
This will take a little explaining....
A database merge is done using the binary database format that only
the old-time GIMPSers remember. The Primenet server removes results
from the cleared exponents report if the exponent is no longer in the
binary database. Unfortunately this algorithm has a flaw. The exponent
may still be in the binary database - only now it is marked for
double-checking. So even though you properly did a first-time check,
the exponent is still in the database, and your line still appears in the
cleared exponents report.
At present the binary database has data on all exponents below 7 million
that need double-checking. In the past it had been 5 million, so not all
result lines between 5 million and 7 million were saved. Furthermore,
buggy v17 results hung around for quite a while because the exponent
was not removed from the binary database for obvious reasons.
Now, why did these old lines recently disappear? That's a completely
different issue! The prime95 client sends two result messages to the
server for every LL test. One is an easy to use C structure that the
server uses to update its databases. The other is a text message
(identical to the results.txt line) that I download once a week and
update my database. Once in a great while I plow through the cleared
exponents report and see if the primenet server database has results
that I am missing (there were 5 since last May). I've emailed the 5
users in hopes of getting them to email the results.txt file to me. I also
told Scott to purge the cleared exponents report of all results sent in prior
to Feb 1, 2000.
Obviously this isn't the cleanest way for Scott and I to maintain our
databases. It developed this way partly for historical reasons and
partly due to constraints on our free time.
Best regards,
George
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 14:58:46 -0600
From: [EMAIL PROTECTED]
Subject: Mersenne: Pi and Greek
I just found out that pi is the 16th letter of the Greek Alphabet. So this
is more evidence for the theory that the numbers 4 and 16 are important in
regards to pi and also to mersenne primes.
Dan
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 16:26:08 -0600
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Base-3 Pseudoprimes
At 03:54 PM 2/10/00 +0800, "Dave Mullen" <[EMAIL PROTECTED]> wrote:
>
>1) For the LL
>test using FFT multiplys, we have to Transform the data, Multiply the
>matrices, Inverse Transform the data, then subtract 2. I am assuming that
>the only reason we do the Forward and Inverse Transform each time is so we
>can subtract the 2 ? Please correct me here if I'm wrong !
I found this in the Lucas Wiman FAQ. ([EMAIL PROTECTED]). Can't remember
the link though.
My only question would be, "Can we not figure out a way to stay in the
frequency domain and correct the errors internally?"
Dan-Somebody-MilesDaniel
>From the Lucas Wiman FAQ.:
Q:6.4: In Q2.6, you say that it doesn't make sense to use a probable prime
test. But wouldn't it make sense to do this, since you could stay in
frequency space throughout the whole test, and save the time consuming
FFT's and IFFT's?
A: Well, first of all, you could still do this with the LL test
(since x^2-2 has a Fourier transform, or by subtracting the convolution
product of ...00001*...00002). However, the FFT's and IFFT's make certain
that errors don't occur (by transforming back into time space, we can make
certain that errors don't accumulate, remember this is an irrational base).
This also allows "quick checks" e.g. the sum of the squares of the
digits=sum of digits in the square (this takes almost no time at all since
we have to manipulate the number anyway.)
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 18:11:07 EST
From: [EMAIL PROTECTED]
Subject: Mersenne: Re: Gabriel's horn
Chris Nash wrote:
>If y=f(x), the volume of revolution is given by
{snip}
Chris, you forgot to explicitly give that f(x) = 1/x, although one
can infer that from the rest of your psot.
Brain teaser:
Are there infinitely many smooth functions f(x) which have the same
volume as the classical Gabriel's Horn when rotated about the x-axis
and x goes from 1 to infinity, and which also have infinite surface area?
(It would suffice to find a one-parameter function family which satisfies
this criterion.)
Gabriel's Horn is one of my favorite Calculus problems. Another is
the famous closed-form method of finding the integral of the Gaussian
exp(-x^2), where the fascinating number sqrt(pi) appears in the result.
The famous Euler identity, exp(i*pi)+1=0, which can be obtained from
the Taylor series for the exponential function and which involves the
five most fundamental constants in mathematics, is yet another.
Gauss' "Theorema Egregium" ("Totally awesome theorem" in dude-speak :)
about the curvature of surfaces also deserves mention, but is getting
way off-topic.
Cheers,
- -Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 18:11:14 EST
From: [EMAIL PROTECTED]
Subject: Mersenne: Re: credit for manual testing
Bill Rea wrote:
>Do people using the manual check out forms get in the Top Producers
>list? I ask because I've never been able to find myself in the list
>and I had an email from a former GIMPS contributor who claimed he
>got no credit for exponents tested through the manual check out/check in
>pages.
So far as I know, manual testing work doesn't get credited on the PrimeNet
top producers pages, but does appear on the GIMPS top producers pages:
http://www.mersenne.org./top.htm <== top 100 based on P90 CPU-years
http://www.mersenne.org./top2.htm <== everybody else
I don't know if manual testing results are included in the PrimeNet
total FLOPS throughput figure, which has jumped appreciably in the
last month.
Thanks to Scott for adding CPU MHz and program version fields to the
PrimeNet account status pages. One problem i noticed, however, is that
all of my manual testing machines are listed as running Prime95 v16,
even the ones that have in the past reported results using Mlucas.
Lastly, it would also be nice to be able to enter something other than
an x86 CPU type when requesting work from the PrimeNet server - right
now I'm just clicking on "pentium" for all my non-x86 machines, so as
to get an appropriate amount of work assigned. There could be preset
fields for the better-known RISC CPUs, e.g.
Alpha SGI/MIPS Sparc IBM RS6000 Mac/PowerPC
- --------- --------- --------- --------- ----------
21064/ev4 R3000 Sparc 1 (not sure ?
21164/ev5 R4000 Sparc 2 about the ?
21264/ev6 R5000 Sparc 5 early ones) 401
R8000 Sparc 10 Power 1/SP1 403
R10000 Ultra 1 Power 2/SP2 G3
R12000 Ultra 2 Power 3/SP3 G4
and an "other" field, where users can manually enter a type and speed
for any other CPU types.
I've ignored fine distinctions, e.g. the Alpha ev45 and ev56 and MIPS 4400
in the above, and some of the types may be redundant, but the table is
only for purposes of illustration. If Scott decides this is worthwhile,
he can appeal to the axperts with various platforms for an appropriately
representative set of CPU types.
Cheers,
- -Ernst
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 18:47:36 -0500 (EST)
From: Jason Stratos Papadopoulos <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Base-3 Pseudoprimes
On Thu, 10 Feb 2000 [EMAIL PROTECTED] wrote:
> My only question would be, "Can we not figure out a way to stay in the
> frequency domain and correct the errors internally?"
If you can figure out a way to propagate carries while in the transform
domain, then you're home free (there are FFTs base on number theory that
have no rounding errors). I've thought about this for a while, but
have no idea where to start (carry propagation is a nonlinear operation,
so it's difficult to apply FFT techniques to it).
jasonp
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 16:46:22 -0800
From: Russel Brooks <[EMAIL PROTECTED]>
Subject: Mersenne: Double-Checking
Do ALL exponents get Double-Checked? ...or are only selected exponents
done beecause the original LL run was suspect?
Just curious,
Russ
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 19:51:06 -0600
From: [EMAIL PROTECTED]
Subject: Mersenne: Email to mersenne
Anyone know why a email with subject "Re: more info on pi" I sent 24 hrs,
2-9-00, ago has not appeared on the list? I sent it with a reply all. Then
today, 2-10-00, I forwarded another copy directly to [EMAIL PROTECTED]
Another message I sent at the same time titled "Pi and Greek" 2-10-00
showed up on the list right away.
Where did the two copies of "Re: more info on pi", 2-9-00, go?
Thanks
Dan
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 19:33:18 -0700
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Re: credit for manual testing
> So far as I know, manual testing work doesn't get credited on the PrimeNet
> top producers pages, but does appear on the GIMPS top producers pages:
>
> http://www.mersenne.org./top.htm <== top 100 based on P90 CPU-years
> http://www.mersenne.org./top2.htm <== everybody else
Know what's weird about those lists? My brother shows up in 19th place, and
I'm in 400 something place, but we both use the same Primenet account.
Hmmm...
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 18:58:52 -0800
From: Stefan Struiker <[EMAIL PROTECTED]>
Subject: Mersenne: "How Many Angels, How Many Pins?" Or PrimeNet's Assignment Strategy
Team M:
Is it better to have 10 pins at 500MHz with one or two angels dancing,
or one 5GHz behemoth looking for luck, given the way PrimeNet
assigns exponents?
Mixing Metaphors,
Stefanovic
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 22:56:17 -0500
From: "Vincent J. Mooney Jr." <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Pi and Greek
Not so. Read up on why pi was selected, by whom and when.
History of Pi by Peter Beckmann is one source.
At 02:58 PM 2/10/00 -0600, Dan wrote:
>I just found out that pi is the 16th letter of the Greek Alphabet. So this
>is more evidence for the theory that the numbers 4 and 16 are important in
>regards to pi and also to mersenne primes.
>Dan
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 21:54:07 -0600 (CST)
From: Conrad Curry <[EMAIL PROTECTED]>
Subject: Mersenne: M629 Factored
NFSNET announces the complete factorization of the
Cunningham number N = 2^629-1 by the Special Number
Field Sieve (SNFS). It was previously known that
N = 223 * 131071 * 616318177 *
45470534643405479586527115047619453123209 *
c133
where c133 is a 133 digit composite number given by
c133 = 271969848617541351506846646350039886577438256\
967129164588443766178354672639577547402508931\
6642385249566550449538370439917146391733319
The two polynomials used were
X^5 - 2 and X - 2^126
with common root 2^126 (mod N).
A total of 9222606 relations was collected with
large prime bound of 100 million on both polynomials.
The sieving was done by a group of 35 volunteers. The
size of the resulting matrix was 1718132 X 1739803.
The linear algebra was done at Centrum voor Wiskunde
en Informatica (CWI) by Peter Montgomery.
The factorization of M629 was 'Most' wanted by the
Cunningham project and the smallest number of the
form 2^n-1 that has not yet been completely factored.
That distinction now goes to M641.
On Feb. 8, 2000 it was found that c133 = p60 * p74
where
p60 = 2052968152651685677561640475673600974472471091\
42889252157111
p74 = 1324764089819199363588233386818302510772681585\
9285731487950046819912806129
Acknowledgements are due to the volunteer sievers
Pierre Abbat Travis Boulden
Sean Brockest Greg Childers
Conrad Curry Laurent Desnogues
Geoffrey Faivre-Malloy Patrick Fossano
Pocza Gabor Jeff Gilchrist
Kelly Hall Philip Heede
Ullrich Heinemann Jim Howell
Craig Kitchen Don Leclair
Joe Leherbauer Yaroslav Levchenko
Holger Menz Thomas Noekleby
Alexis Nunes Henrik Oluf Olsen
Kirk Pearson Bill Rea
Anthony Rumpel Dean Rumpel
Jukka Santala Brian Schroeder
Anastassios Sideridis simon
Alan Simpson Adrian Sloan
Soren Hjorth Sorensen Matthew Whiteside
Joe Williams
We thank also the School of Mathematical Sciences at
the University of Southern Mississippi, CWI, and
Takefive Software, Salzburg, Austria for the use of
their computers.
NFSNET is currently sieving M641 and is about 2/3
done. M641 is the smallest Mersenne number whose
complete factorization is unknown and is 'Most' wanted
by the Cunningham project.
The Cunningham Project
http://www.cerias.purdue.edu/homes/ssw/cun/index.html
The NFSNET Project
http://orca.st.usm.edu/~cwcurry/nfs/nfs.html
The ECMNET Project
http://www.loria.fr/~zimmerma/records/ecmnet.html
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Fri, 11 Feb 2000 00:29:21 -0500
From: Sandy Harris <[EMAIL PROTECTED]>
Subject: Mersenne: Are these lemmas useful?
Here's something I posted in 1996 to sci.crypt.research, now with
some typos corrected.
It produced little reaction there. I'm hoping someone here can see
how to apply it to factoring, or perhaps just to the Mersenne case.
- --------------- forwarded message -----------------------------
Like many others I've been trying for some time to find a fast
factoring algorithm and/or to break RSA. Not too surprisingly,
I haven't succeeded ( yet? :-).
I have, however, proved a couple of little theorems which I
haven't seen in the literature.
Can anyone:
find errors in my proofs?
tell me if they're original?
apply them to factoring?
Fermat's little theorem is that for any prime p and integer i:
i^p == i mod p
My 1st lemma generalises this to:
i^(p^n) == i mod p
The proof is by induction.
Fermat gives us the i = 1 case.
For the induction step:
i^(p^n) = i^(p*p^(n-1))
= (i^(p^(n-1)))^p
but by hypothesis
(i^(p^(n-1))) == i mod p
so
i^(p^n) == i^p mod p
== i mod p
QED
My 2nd lemma applies to a strong prime s
s = 2r + 1 r,s both prime
I'll also assume r odd, ignoring the r=2, s=5 case.
Fermat gives us:
i^s == i mod s
and for non-zero i:
i^(s-1) == 1 mod s
i^2r == 1 mod s
but we also have
n^r == n mod r (Fermat)
n^s == n^(2r+1)
== n^3 mod r
so
n^s = n^3 + kr for some integer k
But n^s and n^3 both have the parity of n so kr must be even
So if r is odd (if s > 5), k must be even.
Which gives us:
n^s = n^3 + 2jr for some int j
or
n^s == n^3 mod 2r
whence
i^(n^s) == i^(n^3) mod s
Which is my 2nd lemma.
------------ end forwarded message --------------------------
The second lemma can be generalised to the case where s = 2r + t
with s and t prime,
i^(n^s) == i^(n^(t+2)) mod s
which reduces to the above if t = 1.
I thought at one point this led to factoring N = xy with x, y prime.
Very likely for some t you have:
x = 2a + t
y = 2b + t
with a and b prime, in which case i^(n^xy) simplifies nicely. Unfortunately I couldn't
find an efficient way to discover t.
Can anyone suggest a method for that, or apply the lemmas in some
other interesting way?
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 10 Feb 2000 23:32:38 -0600
From: Ken Kriesel <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Double-Checking
At 04:46 PM 2/10/2000 -0800, you wrote:
>Do ALL exponents get Double-Checked? ...or are only selected exponents
>done because the original LL run was suspect?
>
>Just curious,
>Russ
Suspect exponents get done earlier.
All are to get double checked eventually.
A mersenne prime is not said to be proven the Nth mersenne
prime until after all prime exponents below it have matching
double or triple or higher checks. (Single checks showing
compositeness could be in error, hiding another prime.)
For QA test purposes, due to poaching, or because of errors in
multiple runs, quite a few get triple checked and a few get
quadruple checked.
Assume that a set of 400,000 exponents get single checked,
and double checked, and the error rate per check is 0.5%.
If the error occurrence is independent, that means about 4000
will not match. Of these 4000 then the triple checks would
have errors in about 20, and require a quadruple check which
most likely would match one of the previous results.
Already double or triple checked exponents make the best check
values for a new program.
Ken
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Fri, 11 Feb 2000 09:50:36 -0000
From: "Andy Steward" <[EMAIL PROTECTED]>
Subject: Mersenne: Record p-1 factors
Dear All,
Firstly, apologies to anyone receiving multiple copies of this message.
The following are the only six 30+ digit factors found by Pollard's p-1
of which I am aware:
(1) p34=8222057557067636644603420882415653
p-1=2^2.3.17.23.43.11657.506797.1632809.1692107.2496721
N=917^43-1
By: Steward 1999
(2) p34=7146831801094929757704917464134401
p-1=2^8.5^2.11^2.23^2.821.3371.39209.3394739.47358559
N=575th Fibonacci Number
By: Silverman 1989
(3) p33=451990098872812878233073602931247
p-1=2.3.7^2.29.1423.55457.1907071.5110913.68921857
N=782^49-1
By: Steward 1999
(4) p32=49858990580788843054012690078841
p-1=2^3.5.13.19.977.1231.4643.74941.1045397.11535449
N=2^977-1
By: Brent
(5) p31=4302886402340485071334706663243
p-1=2.7^2.139.401.129757.183361.488893.67720951
N=303^49-1
By: Steward 1999
(6) p30=174463386657191516033932614401
p-1=2^8.5^2.17.37.1627.5387.68111.152081.477361
N=2^740+1
By: Baillie
Please let me know of any others. I will allow a couple of weeks for
replies and then collate them into an appendix to my website. As you
will note from positions 1, 3 and 5 this is not entirely a detached or
altruistic exercise!
Regards,
Andy
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Fri, 11 Feb 2000 03:01:50 -0700
From: "Aaron Blosser" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Double-Checking
> Assume that a set of 400,000 exponents get single checked,
> and double checked, and the error rate per check is 0.5%.
> If the error occurrence is independent, that means about 4000
> will not match. Of these 4000 then the triple checks would
> have errors in about 20, and require a quadruple check which
> most likely would match one of the previous results.
But, just to clarify, even if both a first time check and a double check
both fail and come up with a bad residue for some reason, the partial
residues from each run won't match, so they'd still be caught and flagged
for a triple check. A triple check will match the first or the second run,
or maybe neither requiring a 4th run.
It all sounds pretty solid to me. :-)
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Fri, 11 Feb 100 02:31:58 -0800 (PST)
From: [EMAIL PROTECTED] (Gordon Irlam)
Subject: Re: Mersenne: Email to mersenne
> Anyone know why a email with subject "Re: more info on pi" I sent 24 hrs,
> 2-9-00, ago has not appeared on the list? I sent it with a reply all. Then
> today, 2-10-00, I forwarded another copy directly to [EMAIL PROTECTED]
>
> Another message I sent at the same time titled "Pi and Greek" 2-10-00
> showed up on the list right away.
>
> Where did the two copies of "Re: more info on pi", 2-9-00, go?
You can try sending it to the list again, and cc'ing me at the
same time. I can watch and figure out the cause of the problem.
There are several possible explanations. The most likely is that
you using words like "help" or "subscribe" in the first few lines
of your message, and majordomo misidentifies it as a misdirected
admin request.
gordoni (list admin)
_________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Fri, 11 Feb 2000 06:45:21 EST
From: [EMAIL PROTECTED]
Subject: Mersenne: Re: Base e arithmetic
In a message dated 10/02/00 07:19:48 GMT Standard Time,
[EMAIL PROTECTED] (Aaron Blosser) writes:
<<
What I'm getting at is that at some point, pi reaches a practical limit at
which expanding more decimal points is an abstraction because we could never
measure anything large enough for it to be useful. I mean, c'mon! The
universe is only so big! :-)
>>
This reminds me of a discussion I had years ago about the optimum design
for a currency. Most countries have coins/notes of value 1, 2, 5, 10, 20, 50,
100 basic currency units, but in Romaina I found they used 1, 3, 10, 30, 100
... multiples.
Presumably the object is to make it such that over an average of many
transactions, the minimum number of coins/notes changes hands. The
optimum ratio between successive currency units (notes/coins) seems to
be between 2 and 3, and a friend suggested that e (2.71828...) would be
the best value, i.e. we have coins and notes valued at 1, e, e^2, e^3 ...
cents or whatever. Maybe pi could be expressed exactly in such a
system. After all, e^(pi*i) = -1.
This led to a discussion as to whether or not it is possible to have a number
system based on a non-integer base. Maybe the great minds of GIMPS
can contribute to this.
Cheers, George.
_________________________________________________________________
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 #692
******************************
