Mersenne Digest Thursday, March 15 2001 Volume 01 : Number 829
----------------------------------------------------------------------
Date: Tue, 13 Mar 2001 16:08:39 +0100
From: Guillermo Ballester Valor <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Primitive roots for Galois transforms?
Hi:
[EMAIL PROTECTED] wrote:
>
> Jason Stratos Papadopoulos wrote (to Peter Montgomery):
> >
> > > Ernst Mayer and I exchanged many mailings about
> > > using GF(p^2) when p = 2^61 - 1.
> > > I thought he had implemented it, as part of a
> > > mixed integer/complex FFT.
> >
> > As I remember, he *had* implemented it but the project is in limbo now for
> > several reasons: first, the Alpha compiler wouldn't interleave the integer
> > and floating point instructions, and also Ernst mentioned that
> > non-power-of-two transforms in GF(p^2) had some subtle difficulty
> > (something about the order that you applied the various radices being
> > important). Last I heard he was embarking on implementing a mixed
> > integer/complex FFT in assembly language, but that was quite a while ago
> > and he likely has moved on.
> >
>
[...snip...]
> The other "problem" I encountered, which you alluded to,
> is that one of the really nice properties of arithmetic
> over GF(q^2), namely that arithmetic modulo the gaussian
> integers closely mirrors that over the complex numbers,
> fails for non-power-of-2 runlengths, in the sense that
> the conjugation property exploited by complex FFTs which
> pack real inputs into half-length complex vectors no
> longer holds for the modular data. The conjugates are
> still there, but their locations in the transform
> output are all screwed up, to use nontechnical language.
> This probably can be overcome or at least mitigated to
> some degree, but it didn't look like it was going to be
> pretty when I first encountered it. But starting with
> a simple power-of-2 runlength implementation and using
> a good compiler (I plan to switch to C) should be a
> worthwhile effort.
>
I wonder if there is possible to find primitive roots in GF(q^2), say a
+ ib, with the condition
a^2 + b^2 = 1 mod q
If this were possible, then
(a + ib)*(a - ib) = 1 + 0i (mod q)
i, e. the inverse of the root would be the conjugate, and the
transformed of a real integer signal should have the same symmetries
than in trigonometric complex case. Could it resolve the problem for a
non-power-of-two FFT length ?. If the answer is yes: any trick to find
the root other than brute force?
Regards.
Guillermo.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 15:48:45 -0000
From: "Andy Hedges" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: VB primality test program
The code is a terrible mess and hardly OO. If anyone makes any radical
improvements to it I would love a copy.
The URL is http://www.a0a.co.uk/mirrors/mersenne/LL.zip
Andy
- -----Original Message-----
From: [EMAIL PROTECTED]
[mailto:[EMAIL PROTECTED]]On Behalf Of Monte
Westlund
Sent: 13 March 2001 14:30
To: [EMAIL PROTECTED]
Subject: Re: Mersenne: VB primality test program
On Mon, 12 Mar 2001 22:12:54 -0800, you wrote:
>
>I'm afraid VB would be awfully slow at any sort of intensive numerical work
>like this, and not very good with precision either, so I rather doubt
anyone
>has spent any signficant time on anything much more sophisticated than a
>erathonese sieve program
>
>-jrp
>
I know VB would not be the first choice. It's more for benchmarking
some machines(Prime95 is not an option on them), and to explore a bit.
Monte
_________________________________________________________________________
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: Tue, 13 Mar 2001 07:49:48 -0800
From: Milton Brown <[EMAIL PROTECTED]>
Subject: Re: Mersenne: VB primality test program
Perhaps you could interface your VB code with
Microsoft C or C++, to be faster.
Milton L. Brown
[EMAIL PROTECTED]
Monte Westlund wrote:
> On Mon, 12 Mar 2001 22:12:54 -0800, you wrote:
>
> >
> >I'm afraid VB would be awfully slow at any sort of intensive numerical work
> >like this, and not very good with precision either, so I rather doubt anyone
> >has spent any signficant time on anything much more sophisticated than a
> >erathonese sieve program
> >
> >-jrp
> >
>
> I know VB would not be the first choice. It's more for benchmarking
> some machines(Prime95 is not an option on them), and to explore a bit.
>
> Monte
> _________________________________________________________________________
> 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: Tue, 13 Mar 2001 09:01:32 -0800
From: "Ethan Hansen" <[EMAIL PROTECTED]>
Subject: RE: Mersenne: Security of prime95
One option for those (including myself) who are concerned either about
another application hijacking the Prime95 communication link, or a Trojan
masquerading as Prime95 is to use an adequate firewall. One application for
Windows PCs is ZoneAlarm (www.zonelabs.com), and it's free. It blocks both
external access to your computer, and perhaps more importantly, only allows
the programs you approve to access the outside world _from_ your computer.
ZoneAlarm creates MD5 checksums for each program that tries talking to the
Internet, and thus prevents another program from calling itself "Prime95" to
gain access. For a good discussion of available firewalls, see
http://grc.com/lt/leaktest.htm.
Regards,
Ethan
> -----Original Message-----
> From: [EMAIL PROTECTED]
> Sent: Monday, March 12, 2001 22:21
> To: [EMAIL PROTECTED]
> Subject: Re: Mersenne: Security of prime95
> By giving out incorrect information? "The network communications
> between the
> server and client pose no risk as there is no instruction
> payload" is simply
> wrong.
>
> I'm not trying to scaremonger. I don't think the risks are that
> great either,
> or I wouldn't be running it. I can't speak for anyone else, but
> what /I/ find
> reassuring is to be told that security was a primary consideration in the
> project design, implementation, and testing. I do not find it
> reassuring to
> be told that there is "no risk".
>
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 18:02:03 +0100 (MET)
From: [EMAIL PROTECTED]
Subject: Re: Mersenne: Primitive roots for Galois transforms?
> From [EMAIL PROTECTED] Tue Mar 13 16:06:33 2001
> I wonder if there is possible to find primitive roots in GF(q^2), say a
> + ib, with the condition
>
> a^2 + b^2 = 1 mod q
>
> If this were possible, then
>
> (a + ib)*(a - ib) = 1 + 0i (mod q)
>
> i, e. the inverse of the root would be the conjugate, and the
> transformed of a real integer signal should have the same symmetries
> than in trigonometric complex case. Could it resolve the problem for a
> non-power-of-two FFT length ?. If the answer is yes: any trick to find
> the root other than brute force?
>
> Regards.
>
> Guillermo.
No. Given alpha = a + ib in GF(q^2), where q == 3 (mod 4), observe that
alpha^q = (a + ib)^q = a^q + (ib)^q = a^q + i^q b^q = a - ib
is the conjugate of alpha. Therefore
alpha^(q+1) = alpha * alpha^q = (a + ib)*(a - ib) = a^2 + b^2.
If alpha is a primitive root in GF(q^2) (order q^2 - 1),
then alpha^(q + 1) is a primitive root in GF(q) (order q - 1).
In particular, a^2 + b^2 <> 1.
(I deleted names other than [EMAIL PROTECTED] from the To: and Cc:
lines, so we don't receive duplicates).
Peter
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 12:34:19 -0600
From: "Tom Cage" <[EMAIL PROTECTED]>
Subject: Mersenne: Glucas for the Macintosh, new version
On Monday, 12 March 2001, Guillermo Ballester Valor [EMAIL PROTECTED]
released version 2.7 of Glucas which is now available for the Macintosh.
G3 and G4 clients along with complete source code may be downloaded at
http://www.belchfirecomputing.com/GIMPS/GIMPS.html
Happy Hunting,
Tom Cage
http://www.belchfirecomputing.com
**** Math is cheaper than physics !!! ****
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 21:32:10 -0000
From: "Brian J. Beesley" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Security of prime95
On 13 Mar 2001, at 0:53, Alex Kruppa wrote:
> > Actually, if George just got a signed PGP key, he could communicate
> > the CRC32 & MD5 checksums of the various files to us by signed email.
>
> First off, please dont use CRC32 for authenticating!
I was most certainly _not_ advocating use of CRC32 alone. In fact, at
the current state of the art, I think MD5 alone is "good enough", but
the effort of matching even CRC32 as well as MD5 should be enough to
satisfy even the most paranoid - and gives an extra "period of grace"
should MD5 be broken. As you say, SHA would be a better choice than
CRC32, but...
> With a PGP detatched siganture packed along with Prime95.exe
> (and one for each .dll of course), all you have to do is double-
> click on
> the .sig file, a PGP window pops up and shows a green light if the
> file
> is ok and a red light if it isn't - which is the way most users
> like it
> (that includes me, I like life simple, if possible..)
OK. Good idea.
> I dont think even most PGP users have a stand-alone md5 program. Most
> linux distributions come with md5sum, but I wouldnt know a Windows
> program off my head.
In the days when it was forbidden to export the US version of
Netscape because of the "strong" encryption content, there was a
program called Fortify which could be used to upgrade the
international version to use US domestic strength encryption. That
package contains a console utility which can be used calculate the
MD5 sum of any file. Check out http://www.fortify.net/
Any idea where I could get a freeware SHA checksum utility?
Regards
Brian Beesley
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Wed, 14 Mar 2001 00:22:53 +0100
From: "Steinar H. Gunderson" <[EMAIL PROTECTED]>
Subject: Mersenne: Re: Security of prime95
On Tue, Mar 13, 2001 at 09:32:10PM -0000, Brian J. Beesley wrote:
>Any idea where I could get a freeware SHA checksum utility?
I made one once, but I'm not sure where I have it nowadays. It should be
quite trivial scripting one in Perl using the SHA1 module from CPAN.
/* 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: Wed, 14 Mar 2001 01:40:47 -0000
From: "Michael Bell" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Quitting GIMPS
Hi,
I also quit GIMPS a couple of years ago, after completing one Lucas-Lehmer
test. I then hopped around various distributed projects, including RC5, OGR
(before it was run by distributed, and since it has been), sum of powers
etc.
As I'm interested in prime numbers I have ended up spending most of my time
searching for unusual forms of primes, where with just one computer, and
less time than a single LL test you can go get yourself a record - albeit a
fairly obscure one, like the largest quintuplet of primes, or the largest
extreme prime triplet. I personally find these much more interesting as you
actually have to think about what you are doing and find the best way of
doing it rather than telling your computer to go fetch another test.
If you are interested try having a look at www.utm.edu/research/primes.
Michael.
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 22:14:54 -0500
From: "Joshua Zelinsky" <[EMAIL PROTECTED]>
Subject: Mersenne: SETI again
This is a the gist of a message on the theory-edge group that I just
received:
>here's a nice technology review article on
>distributed computing startups & technology.
>http://www.techreview.com/web/essex031201.asp
And this is coming from people who are also interested in pure mathematics!
Actually, the review mentions us, so its not half bad compared to others. It
gives what seems to be an accurate summary of the current economic situation
for for-profit distributed computing. I reccomend that everyone read it.
Sincerely,
Joshua Zelinsky
Lord_Bern@hotmail.
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Tue, 13 Mar 2001 23:03:41 -0500
From: Nathan Russell <[EMAIL PROTECTED]>
Subject: Re: Mersenne: SETI again
On Tue, 13 Mar 2001 22:14:54 -0500, you wrote:
>
>This is a the gist of a message on the theory-edge group that I just
>received:
>
>>here's a nice technology review article on
>>distributed computing startups & technology.
>
>>http://www.techreview.com/web/essex031201.asp
>
>And this is coming from people who are also interested in pure mathematics!
>Actually, the review mentions us, so its not half bad compared to others. It
>gives what seems to be an accurate summary of the current economic situation
>for for-profit distributed computing. I reccomend that everyone read it.
Personally, I think it could have given a slightly longer mention of
us - especially in view of the repeated mentions of SETI. This is the
total discussion of GIMPS in the article:
"The company claiming the most experience is Entropia of San Diego.
Formed in 1997, it provided technology for SETI@Home and for The Great
Internet Mersenne Prime Search, a search for the largest prime
numbers. "
To be fair, though, distributed.net was not mentioned in much greater
detail.
That said, I found it intersting that there are so many companies in
for-profit distributed computing these days, compared to even when I
joined GIMPS, slightly over a year ago. There is /still/ little
public word about what type of work is being done, and there are still
no companies that pay users on a per CPU hour/day basis, which is
something that I would expect fairly soon.
Nathan
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Wed, 14 Mar 2001 01:59:24 -0500
From: "Marc" <[EMAIL PROTECTED]>
Subject: Mersenne: Hello everyone... I'm Still Alive ;)
This is a multi-part message in MIME format.
- ------=_NextPart_000_0009_01C0AC2A.64DA35C0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
LoL, Just felt the need to send a big hello out to all my fellow GIMPS =
participants. It has been just over 6 years since I joined the project. =
There were only 212 members when I joined. My friend Mike Gach was one =
of the first 60 members to join and got me interested. It has been a =
long but enjoyable time with everyone. I miss the comments and =
discussions from some of the earliest members, but am ever glad to see =
new and motivated members joining our ranks. Kudos out to George =
Woltman and Scott Kurowski for doing the lions share of development =
which we all enjoy. Big thanks to all those in the credits also, there =
are many many more key people who have put hard work into making this =
project what it is and I apologize for not specifically naming everyone =
involved.
For everyone new to the project let me just say "WELCOME"! Rest assured =
you have found a great group of people that not only share this common =
interest, but from reading almost every e-mail on the mersenne list I =
can also testify that our group appears to maintain a group of people =
with a high standard of ethics and genuine interest in team work. Don't =
let the daunting size of the current assignments overwhelm you, your =
efforts do not go unrecognized and certainly offer the hope of a =
possible reward ;) It has been quite some time since our last discovery =
and I would suspect we are on the verge of a new record breaker. You =
never know if you are the next one to be a Titan;) Keep up the good =
work everyone new and old! The future is ours (well as geeks speak goes =
anyway) hehe
Marc Honey =20
- ------=_NextPart_000_0009_01C0AC2A.64DA35C0
Content-Type: text/html;
charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD>
<META content=3D"text/html; charset=3Diso-8859-1" =
http-equiv=3DContent-Type>
<META content=3D"MSHTML 5.00.2614.3500" name=3DGENERATOR>
<STYLE></STYLE>
</HEAD>
<BODY bgColor=3D#ffffff>
<DIV><FONT face=3DArial size=3D2>LoL, Just felt the need to send a big =
hello out to=20
all my fellow GIMPS participants. It has been just over 6 years =
since I=20
joined the project. There were only 212 members when I =
joined. My=20
friend Mike Gach was one of the first 60 members to join and got me=20
interested. It has been a long but enjoyable time with =
everyone. I=20
miss the comments and discussions from some of the earliest members, but =
am ever=20
glad to see new and motivated members joining our ranks. Kudos out =
to=20
George Woltman and Scott Kurowski for doing the lions share of =
development which=20
we all enjoy. Big thanks to all those in the credits also, =
there are=20
many many more key people who have put hard work into making this =
project what=20
it is and I apologize for not specifically naming everyone=20
involved.</FONT></DIV>
<DIV><FONT face=3DArial size=3D2></FONT> </DIV>
<DIV><FONT face=3DArial size=3D2>For everyone new to the project let me =
just=20
say "WELCOME"! Rest assured you have found a great group of =
people=20
that not only share this common interest, but from reading almost every =
e-mail=20
on the mersenne list I can also testify that our group appears to =
maintain=20
a group of people with a high standard of ethics and genuine interest in =
team=20
work. Don't let the daunting size of the current assignments =
overwhelm=20
you, your efforts do not go unrecognized and certainly offer the hope of =
a=20
possible reward ;) It has been quite some time since our last =
discovery=20
and I would suspect we are on the verge of a new record breaker. =
You never=20
know if you are the next one to be a Titan;) Keep up the good =
work=20
everyone new and old! The future is ours (well as geeks speak goes =
anyway)=20
hehe</FONT></DIV>
<DIV> </DIV>
<DIV><FONT face=3DArial size=3D2>Marc =
Honey</FONT> </DIV></BODY></HTML>
- ------=_NextPart_000_0009_01C0AC2A.64DA35C0--
_________________________________________________________________________
Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
------------------------------
Date: Thu, 15 Mar 2001 17:55:48 -0500
From: "Joshua Zelinsky" <[EMAIL PROTECTED]>
Subject: Re: Mersenne: Security of prime95
Brian J. Beesley wrote:
>"Joshua Zelinsky" wrote:
>
> > While were on the topic of authentification. Why not have a code for the
> > server as well. Prime95 could automatically check it whenver it
>contacted
> > the server. That would help prevent hackers from acting as the server.
>
>Er ... does this help? You have to have a challenge/response
>sequence. Just playing back a code is no help, hackers can easily
>replicate that.
That's what I meant. Sorry about the poor phrasing.
Sincerely,
Joshua Zelinsky
[EMAIL PROTECTED]
_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com
_________________________________________________________________________
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 #829
******************************
