Mersenne Digest Sunday, 17 May 1998 Volume 01 : Number 362 ---------------------------------------------------------------------- From: "Vincent J. Mooney Jr." Date: Fri, 15 May 1998 22:05:43 -0400 (EDT) Subject: Mersenne: Vcard I noticed several days ago that I had in my /Netscape/Eudora directory files named vcard.vcf and vcard1.vcf and vcard2.vcf and so on. A little investigation showed that a certain Jean-Luc Cooke was responsible for these file. Is there some way that he can stop sending them? No one else seems to send anythig remotely like this. Those who wish may check their file for vcard.vcf file. ****************************************************************************** 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 ******************************************************************************** Vincent J. Mooney Jr. vincentj@erols.com ------------------------------ From: "Gilles Polus" Date: Sat, 16 May 1998 06:48:38 +0200 Subject: Mersenne: Cryptography Message en plusieurs parties et au format MIME. - ------=_NextPart_000_0004_01BD8096.A823A540 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable I would know if there is any relation between Mersenne primes and = cryptography. Sorry, but I don't speak english fluently ( I'm french). - ------=_NextPart_000_0004_01BD8096.A823A540 Content-Type: text/html; charset="iso-8859-1" Content-Transfer-Encoding: quoted-printable

I would know if there is any = relation between=20 Mersenne primes and cryptography.

Sorry, but I don't speak english = fluently ( I'm=20 french).

- ------=_NextPart_000_0004_01BD8096.A823A540-- ------------------------------ From: Chris Nash Date: Sat, 16 May 1998 05:42:51 -0400 Subject: Re: Mersenne: Use Fermat First? >http://www.engsoc.carleton.ca/~jlcooke/Numbers/GIMPS/ll.html *smiles* Cute. See what happens when you test M(101). It's the smallest example I can think of where your sieve isn't going to spot a factor before the pseudo-primality test. Your Fermat test returns true, LL returns false. If your pseudo-prime base you're using is 2... well I have a funny feeling your timings and results are all coming from your sieve. The Fermat test will always return true using base 2 with a Mersenne number of prime exponent. Oddly enough the LL test on M(101) seems quicker than the combined sieve and Fermat. If I were you I'd take the sieve out and then check your results, after all, we do already trial-factor before embarking on an LL test. Chris Nash ------------------------------ From: Rjpresser Date: Sat, 16 May 1998 09:59:45 EDT Subject: Re: Mersenne: Vcard vcard files are "virtual business cards", part of the S/MIME standard. People are supposed to attach them to email the way people attach business cards to paper mail. If he won't stop attaching them (they're probably in his preferences), you can probably configure Eudora to not automatically save attachments, or just run a sweep to delete them periodically - they do no harm. ------------------------------ From: "Vincent J. Mooney Jr." Date: Sat, 16 May 1998 11:20:57 -0400 (EDT) Subject: Mersenne: I don't want it I don't want it. Please stop sending it. It comes with every messsage you send. No one else sends unwanted e-mail like this. _NO ONE_ ********************************************* Jean-Luc Cooke wrote: It's a Netscape file. It contains data about me that can be added to your address book. Vincent J. Mooney Jr. wrote: > > I noticed several days ago that I had in my /Netscape/Eudora directory files > named vcard.vcf and vcard1.vcf and vcard2.vcf and so on. > > A little investigation showed that a certain Jean-Luc Cooke was responsible > for these file. Is there some way that he can stop sending them? > > No one else seems to send anythig remotely like this. Those who wish may > check their file for vcard.vcf file. > > ****************************************************************************** > 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 > ******************************************************************************** Vincent J. Mooney Jr. vincentj@erols.com ------------------------------ From: Jean-Luc Cooke Date: Sat, 16 May 1998 14:18:17 -0400 Subject: Re: Mersenne: Use Fermat First? This is a multi-part message in MIME format. - --------------689C5C4EBD163BB1EEAE43AC Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Chris Nash wrote: > > >http://www.engsoc.carleton.ca/~jlcooke/Numbers/GIMPS/ll.html > > *smiles* Cute. > > See what happens when you test M(101). It's the smallest example I can think > of where your sieve isn't going to spot a factor before the pseudo-primality > test. Your Fermat test returns true, LL returns false. Humm, the trial factoring takes almost no time at all. Like a few mili/micro seconds, even for the snail which is Java. 2207 does the same at 101. > If your pseudo-prime base you're using is 2... well I have a funny feeling > your timings and results are all coming from your sieve. The Fermat test > will always return true using base 2 with a Mersenne number of prime > exponent. Sieve of 100 is pretty fast. Okay then. What about base 3, 5, or 7? I'm looking for an improvement and hoping I can be shut down! :) Interesting with the 2-PRP thing, has something to do with the M(x)= 2^x-1 doesn't it? > Oddly enough the LL test on M(101) seems quicker than the combined sieve and > Fermat. If I were you I'd take the sieve out and then check your results, > after all, we do already trial-factor before embarking on an LL test. Humm, I don't know about that. The 101 test goes too fast for both F and LL go a bit too fast for me. I've tried some larger numbers like 541, 547, 1229, 2203 and 2207 and the F test goes faster. By several seconds on the 2203 test. I've changed the 2-PRP to 3-PRP to fix that problem you pointed out earlier! :) > Chris Nash TTYL JLC ps. I like this kinds of discussion. Mostly because I can follow half of it! - -- 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! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- - --------------689C5C4EBD163BB1EEAE43AC 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 - --------------689C5C4EBD163BB1EEAE43AC-- ------------------------------ From: "John R Pierce" Date: Sat, 16 May 1998 10:52:37 -0700 Subject: Re: Mersenne: I don't want it >I don't want it. Please stop sending it. It comes with every messsage you >send. > >No one else sends unwanted e-mail like this. _NO ONE_ I occasionally get messages with these 'Vcard' things, but my mailer doesn't detach attachments unless I ask it to. I always hated the way Eudora auto-dumps attachments in a folder without asking or notifying you. My mailer simply keeps the attachments with the original message unless I ask it to save them. However. Sending MIME or S/MIME anything to a email list generally isn't appropriate. If the list is 'digested', the digester can't reconcile the MIME and ends up looking like a bunch of gobbledygook... This is a multi-part message in MIME format. --------------C71A66875E1B24D09A6AC9F5 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit etc... ------------------------------ From: Jean-Luc Cooke Date: Sat, 16 May 1998 14:02:38 -0400 Subject: Re: Mersenne: Cryptography > Gilles Polus wrote: > > I would know if there is any relation between Mersenne primes and > cryptography. > Sorry, but I don't speak english fluently ( I'm french). Yes there is. They don't use Mersenne in Cryptography becase they are too easily recognized. For more info on RSA type cryptography check out the following URLS: http://www.engsoc.carleton.ca/~jlcooke/Numbers/ http://www.engsoc.carleton.ca/~jlcooke/RSA/ http://www.engsoc.carleton.ca/~jlcooke/JLCauth/ If you have any questions or suggestions, email me and I'll see what can do. I'm still new to this but very interested. Crypto is how I tripped upon the GIMPS project. TTYL JLC - -- 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! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- ------------------------------ From: Jean-Luc Cooke Date: Sat, 16 May 1998 18:17:34 -0400 Subject: Re: Mersenne: I don't want it For the dinosaurs of this group I've stopped sending my personal info. For the horrendous disk space and internet bandwidth that <1K takes up I have decided to sacrifice my open door policy to information, not for the sake of regression compatibility but for the sake all those who are digital directory neat freaks. TTYL JLC vcard-less. Vincent J. Mooney Jr. wrote: > > I don't want it. Please stop sending it. It comes with every messsage you > send. > > No one else sends unwanted e-mail like this. _NO ONE_ > > ********************************************* > Jean-Luc Cooke wrote: > > It's a Netscape file. > > It contains data about me that can be added to your address book. > > Vincent J. Mooney Jr. wrote: > > > > I noticed several days ago that I had in my /Netscape/Eudora directory files > > named vcard.vcf and vcard1.vcf and vcard2.vcf and so on. > > > > A little investigation showed that a certain Jean-Luc Cooke was responsible > > for these file. Is there some way that he can stop sending them? > > > > No one else seems to send anythig remotely like this. Those who wish may > > check their file for vcard.vcf file. > > > > ****************************************************************************** > > 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 > > > ******************************************************************************** > > Vincent J. Mooney Jr. vincentj@erols.com - -- 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! - ---------------------------------------------------------------------- Hyperactivity Unbounded http://www.engsoc.carleton.ca/~jlcooke - ---------------------------------------------------------------------- AOL-IM ID: JLinOTTAWA http://register.netscape.oscar.aol.com - ---------------------------------------------------------------------- ICQ# 4474419 http://www.mirabilis.com - ---------------------------------------------------------------------- Email addresses jlcooke@ottawa.com jlcooke@magma.ca jlcooke@magmacom.com jlcooke@engsoc.carleton.ca jlcooke@chat.carleton.ca - ---------------------------------------------------------------------- ------------------------------ From: "Brian O'Kelley" Date: Sat, 16 May 1998 20:04:38 -0400 Subject: Re: Mersenne: I don't want it How about changing it to a hyperlink? Seems much more appropriate. Thanks, b At 11:20 AM -0400 5/16/98, Vincent J. Mooney Jr. wrote: >I don't want it. Please stop sending it. It comes with every messsage you >send. > >No one else sends unwanted e-mail like this. _NO ONE_ > > >********************************************* >Jean-Luc Cooke wrote: > >It's a Netscape file. > >It contains data about me that can be added to your address book. > >Vincent J. Mooney Jr. wrote: >> >> I noticed several days ago that I had in my /Netscape/Eudora directory files >> named vcard.vcf and vcard1.vcf and vcard2.vcf and so on. >> >> A little investigation showed that a certain Jean-Luc Cooke was responsible >> for these file. Is there some way that he can stop sending them? >> >> No one else seems to send anythig remotely like this. Those who wish may >> check their file for vcard.vcf file. >> >> >>****************************************************************************** > >>> 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 >> >******************************************************************************* >* > >Vincent J. Mooney Jr. vincentj@erols.com ------------------------------ From: Chris Nash Date: Sat, 16 May 1998 20:36:41 -0400 Subject: Re: Mersenne: Use Fermat First? Jean-Luc >Humm, the trial factoring takes almost no time at all. Like a few >mili/micro seconds, even for the snail which is Java. 2207 does the >same at 101. What trial factors are you using in your sieve? I mean, if you are just using the same sieve (first 100 primes), it's very quickly not going to be of any use. All factors of any M(p) are of the form 2kp+1, so there's no point trial-factoring anything smaller than 2p+1. (You can sieve the 2kp+1, testing those are prime, before factoring though, just sieving 3,5,7 rubs out half the trial factors). >Sieve of 100 is pretty fast. Okay then. What about base 3, 5, or 7? I think there's a conjecture out there that if a Mersenne number of prime exponent (and some other restriction) is pseudoprime to base 3, then it is prime. Only a conjecture... The only ways I could possibly think of looking at this is considering 3^M as (2+1)^M and looking at binomial coefficients mod M, knowing some will vanish and others won't for composite M. >Interesting with the 2-PRP thing, has something to do with the M(x)= >2^x-1 doesn't it? Yep. Basically 2^x=1 mod M, and M=1 mod x. So 2^M=2^1=2 mod M :) > I've tried some larger numbers like 541, 547, 1229, 2203 and 2207 and > the F test goes faster. By several seconds on the 2203 test. F is going to be 'slightly' faster than LL. If you're getting it a great deal faster, maybe you're onto something... but I can't see how p iterations of 'square, then reduce mod M' is much faster thatn 'square, subtract 2, reduce mod M'. > ve changed the 2-PRP to 3-PRP to fix that problem you pointed out earlier! :) How good are your results? Are you getting 'not pseudoprime' for tbe majority of composite Mersenne numbers with prime exponent? Maybe we can get some quantities. Suppose your FF test takes t times as long as LL. You're getting t=0.66, but I'd be surprised if you can get t much less than 1. (the FFT implementation of squaring needs to accuracy-check the least-significant bits, so the subtract 2 step is practically free anyway). Now we only need really worry about composite M(p) tests. For primes, well there aren't many and an LL test is DEFINITELY necessary. Suppose a proportion p of these are pseudo-primes to base 3. We would like p to be very low :) We do an FF test. With probability (*grin*) p, we need to FF and LL. That takes 1+t times the duration of LL. With probability 1-p, we only need the FF test in relative time t. So we expect a testing time of (1-p)t+p(1+t) = t+p times the LL testing time. So we want p<1-t. You suggest t=0.66, so if you can find a pseudo-prime base that claims M is a pseudoprime less than 1/3 of the time, you win. I'm guessing t=0.95 or more is more likely... that would require returning M as pseudoprime to your base less than 1/20 of the time. I don't know how common pseudoprimes are among the M(p)... anyone got any figures? >ps. I like this kinds of discussion. Mostly because I can follow half >of it! *grin* I know the feeling. It's been quite some time since I was doing my math degree, and so much of it is getting so hazy. This FFT stuff is completely beyond me! Best Wishes and Good Luck! Chris Nash ------------------------------ From: George Woltman Date: Sat, 16 May 1998 21:09:37 -0400 Subject: Re: Mersenne: Cryptography Hi all, At 06:48 AM 5/16/98 +0200, Gilles Polus wrote: > I would know if there is any relation between Mersenne primes and >cryptography. Sorry, but I don't speak english fluently ( I'm french). Richard Crandall worked out a method for using Mersenne Primes in encryption. This was done while he worked at NeXT. They patented the algorithm and it is NOT publicly available. The fact that there are only 37 known Mersenne primes does not help you crack the message at all. Best regards, George ------------------------------ End of Mersenne Digest V1 #362 ******************************