Mersenne Digest Sunday, 24 May 1998 Volume 01 : Number 366 ---------------------------------------------------------------------- From: "John R Pierce" Date: Thu, 21 May 1998 06:28:39 -0700 Subject: Re: Mersenne: FFT ??? >I don't stop to see the word FFT. >But, what means this word ? Fast Fourier Transform. Its an efficient method of computing Discrete Fourier Transforms. Fourier Transforms are 'normally' used to convert time domain data into frequency domain data and visa versa. But, due to some quirks of mathematics outlined by Donald Knuth in his "Seminumerical Programming", they can also be used to perform very high precision multiplies. >I want also to know what are the Carmichael's numbers. That I dunno. - -jrp ------------------------------ From: Nicolau Corcao Saldanha Date: Thu, 21 May 1998 10:34:34 -0300 Subject: Re: Mersenne: Re: > What relevance does this have? It limits the possibilities for what the > prime components could be by about 80% (or 60% if the composite ends in > 1). It also shows that composites that end in 1, are stronger, with > respect > to trial division attacks, than composites that end in 3,7 or 9. I am not > sure if this strength issue holds true for other factoring methods. I'm not sure what this means but Dirichlet's Theorem, which proves that given coprime a and b there are infinitely many primes of the form an+b also shows that, given a, the proportion of primes in these sequences are roughly the same. In particular, in the limit, a prime number has equal probability of ending in 1, 3, 7 or 9. You may find a precise statement in Borevich-Shafarevich, Number Theory. An excelent book, btw. Best wishes, N. ------------------------------ From: Paul Leyland Date: Thu, 21 May 1998 07:25:29 -0700 Subject: RE: Mersenne: FFT ??? > >I want also to know what are the Carmichael's numbers. > > > That I dunno. But I do. According to Fermat, the number a^(n-1) is equivalent to 1 modulo n whenever n is a prime number. Unfortunately, this is not an infallible test to see whether n is prime --- some composite values of n also pass the test. With most composite numbers it is usually very easy to find a value of "a" which shows n not to be prime - --- such a value is called a witness in the jargon. Finding a witness for a Carmichael number is particularly difficult, as the only witnesses are those which are factors of n. It has been shown that there are an infinite number of Carmichael numbers. The smallest is 561 = 3*11*17. It's also been shown that there are many special forms of Carmichael numbers. For instance, if 6t+1, 12t+1 and 12t+1 are all prime for the same value of t, their product is a Carmichael number. The smallest example of this form has t=1 and the Carmichael number is 7*13*19 = 1729. Paul ------------------------------ From: "Robert G. Wilson v, PhD ATP" Date: Thu, 21 May 1998 10:15:04 -0500 Subject: Mersenne: Re: Chuck W. wrote: > Although I realize that it is nothing terribly new, I have come across > some things that interested me and I figured others might be interested: > > As we all should know, all primes MUST end in 1,3,7 or 9. Further, I have > determined that all composites, made up of two primes, must end in 1,3,7, > or 9 as well. Further this breaks down as follows: > > Let N be a composite number > 0 whose last digit is n, made up of primes > P1 > 0 and P2 > 0 whose ending digits are p1 and p2 respectively. > > If n = 1 then (p1 = 1 and p2 = 1) > or (p1 = 7 and p2 = 3) > or (p1 = 9 and p2 = 9) > If n = 3 then (p1 = 1 and p2 = 3) > or (p1 = 7 and p2 = 9) > If n = 7 then (p1 = 1 and p2 = 7) > or (p1 = 3 and p2 = 9) > If n = 9 then (p1 = 1 and p2 = 9) > or (p1 = 3 and p2 = 3) > Missed one here at If n=9 then ... or (p1 = 7 and p2 = 7). Therefore for any ending digit, you must check each and every prime in your search because no seive eliminates a possible prime candidate. A prime candidate whose last digit is one can have a final digit of 1 or 3 or 7 or 9. The same holds true for a composite ending with 3, 7 or 9. There is no new information to be gained here. Using the last two digits of the composite number does nothing either. > Please note that only specific combinations are possible (hence the > and/or). I can provide the proof if you need it. I won't waste the space > at this time. > Yes, only specific combinations are possible but no help on finding the first factor. > What relevance does this have? It limits the possibilities for what the > prime components could be by about 80% (or 60% if the composite ends in > 1). It also shows that composites that end in 1, are stronger, with > respect > to trial division attacks, than composites that end in 3,7 or 9. I am not > sure if this strength issue holds true for other factoring methods. > It limits nothing. > Is this a case for revisiting trial division? IMHO absolutely not... I do > believe this could be used with other optimizations to make factoring > large composites a bit easier... > Nope. > Is there anyone who can take the time to explain the ppmpq method of > factorization to me? The web seems to be sorely absent of any good > explanations. > > Thank you... > > - > I tell you the truth, we speak of what we know, and we testify to what > we have seen, but still you people do not accept our testimony. > > ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ > : WWW+PGP: http://www.silverlink.net/poke : > : E-Mail: chuckw@silverlink.net : ------------------------------ From: "Chuck W. " Date: Thu, 21 May 1998 08:32:52 -0700 (PDT) Subject: Mersenne: Re: we use base 2X5 Yes, you are correct. I should have added a "Large number" constraint to my proof, I.E. Let N > 0 be a composite made up of primes P1 > 10 and p2 > 10. On Wed, 20 May 1998, two inch deep pile carpet wrote: > Chuck W. wrote: > > > As we all should know, all primes MUST end in 1,3,7 or 9. Further, I have > > determined that all composites, made up of two primes, must end in 1,3,7, > > or 9 as well. Further this breaks down as follows: > > > Except, which goes without saying, but here I am, 2 and 5 and composites > including them -- like, say, 34. > > > Because we use base 10, which is composite, having 2 and 5 as its > prime factors, we know that the last digit being a multiple of two > implies divisibility by two and the lst digit dividing by 5 implies > divisibility by five. > > Were we to use a different digital base different phenomena would > be observable. In base 9 for instance you might notice that all > primes (except three) end in 1,2,4,5,7, or 8 due to numbers ending > in 0,3 or 6 in base 9 being divisible by three. > > > ______________________________________________________________________ > David Nicol 816.235.1187 UMKC Network Operations david@news.umkc.edu > "Irving was twirling his gun around..." > - - I tell you the truth, we speak of what we know, and we testify to what we have seen, but still you people do not accept our testimony. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : WWW+PGP: http://www.silverlink.net/poke : : E-Mail: chuckw@silverlink.net : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ : According to Section 227(b)((3)(B) of US Code Title 47 I am entitled : : to $500 per un-solicited commercial e-mail. : ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ------------------------------ From: "Steven Whitaker" Date: Thu, 21 May 1998 17:35:54 +0100 Subject: Re: Mersenne: FFT ??? A Carmichael number is a number that is a pseudo-prime to any base ie c is a Carmichael number if a^(c-1) - 1 mod c = 0 for all values of a but c is not prime. 561 (=3*11*17) is the lowest Carmichael number. The reason they're important is that the above test is also true for all primes, so it's used as a quick(ish) test for probable primality but on its own will also show all Carmichael numbers as probable primes. Hope this helps Steve - ---------- > From: John R Pierce > To: Mersenne discussion list > Subject: Re: Mersenne: FFT ??? > Date: 21 May 1998 14:28 > > >I don't stop to see the word FFT. > >But, what means this word ? > > > Fast Fourier Transform. Its an efficient method of computing Discrete > Fourier Transforms. Fourier Transforms are 'normally' used to convert time > domain data into frequency domain data and visa versa. But, due to some > quirks of mathematics outlined by Donald Knuth in his "Seminumerical > Programming", they can also be used to perform very high precision > multiplies. > > >I want also to know what are the Carmichael's numbers. > > > That I dunno. > > -jrp > ------------------------------ From: "Guillermo Ballester Valor" Date: Thu, 21 May 1998 19:07:18 +0200 Subject: Mersenne: Re: Fermat base-3 for LL Hi: Ernst. W. Mayer wrote: > That is, the ONLY advantage of the Fermat-base-3 test is that it > yields a residue which, if the number proves composite, is still of > further use, unlike the LL residue, which is useful only for results > verification. Perhaps there is other advantage in Fermat base-3 Test: P.L. Montgomery has proposed a scheme to perform two independent fermat test with the same program. Is this is accepted, we DEFINITELY can reject an exponent with two conincident matches i.e. we don't need a double check to be sure there is not a failure in hardware or software. I am saying we also need TWO FERMAT TEST PER EXPONENT, but it can be done by the same program (not the same machine), and we will not have thousands and thousands of exponents looking for a searcher to double-check. ************************************** Guillermo Ballester Valor c/ Córdoba, 19 18151-Ogijares (SPAIN) Phone: 34 58 597503 E-mail: gbv@ctv.es ************************************* ------------------------------ From: matic@cyberia.net.lb (Imad R. Faiad) Date: Thu, 21 May 1998 17:45:05 GMT Subject: Mersenne: Is the Primenet Server Down? Is the Primenet server down? ------------------------------ From: Jean-Luc Cooke Date: Thu, 21 May 1998 14:04:09 -0400 Subject: Mersenne: Re: Chuck's Idea Hi again, I don't know if I mentioned this before or not. But then I was developing something "new" (Gauss and Fermat did this long ago actually, oops!) I tried what Chuck was doing but with different numbers than x mod 10. More like the first n primes. I called a PMC for the lack of anything cool. Ah well, let me know if anyone's interested in my amateur attempts. TTYL JLC - -- < censored :) > ------------------------------ From: STL137 Date: Thu, 21 May 1998 19:44:58 EDT Subject: Mersenne: Re: Mersenne Digest V1 #365 Uh, what is this DAT file? WINMAIL.DAT? I ain't gonna download this...... STL137 ------------------------------ From: LozCS Date: Thu, 21 May 1998 20:57:27 EDT Subject: Mersenne: Update on AOL Has anybody got Prime95 to update automatically with AOL? I've tried it on 3 separate machines with no joy is it possible? Lawrence...... ------------------------------ From: "Ernst W. Mayer" Date: Thu, 21 May 1998 21:00:40 -0400 Subject: Mersenne: beta of lucas_mayer V2.5 Dear all: a beta of lucas_mayer V2.5 is available (in F90 source only, for now) at ftp://nigel.mae.cwru.edu/pub/mayer/lucas_mayer_V2.5.f90.gz Please also download the updated README file. Major changes from V2.4d include: * A radix-16, 2-D padded array FFT scheme. This is much L1-cache-friendlier than the 1-D array FFT in V2.4, especially at large N. Typical speedups (for FFT lengths of current interest, i.e. 256K and larger): - On Alpha ev5 (21164) and ev56, the 2-D code is 30-40% faster than V2.4. - On Alpha ev6 (21264), the 2-D code is twice as fast as the 1-D. - On SGI (250MHz Octane), the speedup is impressive indeed: 100 iterations of V2.4d at N=256K took 160s, V2.5 took just 60s. The only platform I've tried on which the new version gives little or no improvement (it's a tad slower at 256K, 15-20% faster at 512K and 1024K) is Alpha ev4 (21064). * The code allows FFT lengths up to 1024K, and can test exponents up to ~20 million. Other notes: - - Savefiles are compatible with v2.4. - - Iterations between checkpoints has been reduced from 10000 to 2000. - - The Alpha binaries have not yet been updated - I'm waiting for a friend with the latest version of the DEC F90 compiler to send me these. - - I have posted an SGI binary to ftp://nigel.mae.cwru.edu/pub/mayer/bin/lucas_mayer_v2.5.exe.gz, but am not yet sure which of the F90 RTL files are needed to run the binary on systems lacking a Fortran-90 compiler. Any help in this regard is appreciated. - - I have no access to a high-end SPARC with F90 compiler. Timings, optimal compile options and/or binaries from someone who has such would be appreciated. - - Non-power-of-2 FFT lengths will appear in a later version of 2.5. George and I now have complementary problems: his latest Prime95 (Prime98?) suffers from suboptimal cache performance at large runlengths, but has very good assembly-coded FFT routines. Lucas_mayer 2.5, on the other hand, has excellent cache performance (Peter Montgomery reports an L1 miss rate around 1%, which remains essentially constant for FFT lengths up to the maximum, using the profiling software on his SGI), but the critical portions of the FFT could use assembly coding. Peter and I are now working on this. Your comments/timings/questions/suggestions are welcome. Happy Memorial Day weekend to our US readers. Cheers, Ernst ------------------------------ From: "Cornelius Caesar" Date: Fri, 22 May 98 17:17:37 CES Subject: Mersenne: Re: Mersenne Newsletter #14 George Woltman wrote: >Fortunately, version 16 should keep our computers busy for years to come! This is the kind of statement which usually is proved wrong much sooner than expected... ;-) Cornelius Caesar ------------------------------ From: "Alan R. Vidmar" Date: Fri, 22 May 1998 11:35:44 +0000 Subject: Re: Mersenne: Re: Mersenne Newsletter #14 Can anyone tell me what the differences between Prime95 16.3 for 95/NT and Prime95 for NT? I am running NT exclusively, does the NT only version run faster? Thanks, Alan "There's too much blood in my caffeine system." -Unknown Alan R. Vidmar Network Analyst/Administrator Alan.Vidmar@Colorado.EDU University of Colorado ** This message printed with 100% recycled electrons ** ------------------------------ From: David Underbakke Date: Fri, 22 May 1998 17:04:52 -0500 Subject: Re: Mersenne: Re: Mersenne Newsletter #14 At 11:35 AM 5/22/98 +0000, you wrote: >Can anyone tell me what the differences between Prime95 16.3 for >95/NT and Prime95 for NT? > >I am running NT exclusively, does the NT only version run faster? > Are you sure you don't mean Prime95 and NTPrime? Prime95 is runs as an application on either Win95/Win98/WinNT, while NTPrime runs as a service, only in WinNT. ___________ David Underbakke ------------------------------ From: Harald Tveit Alvestrand Date: Sat, 23 May 1998 11:46:02 +0200 Subject: Mersenne: About the Test/Status display..... One wish...... when I choose test/status in the NTPrime or Prime95 programs, it would be lovely if, rather than "You will be working on these exponents", I could get a display like this: expected completion dates: for M3750547: Jun 04 21:40 1998 (Lucas-Lehmer) for M4173483: Jun 05 22:30 1998 (Factoring) I was looking at the stuff the program sends to the PrimeNet server, and was thinking "gee, I wish I could look at that" (the personal stats are down at the moment, so I can't get it that way). Why not? Harald A - -- Harald Tveit Alvestrand, Maxware, Norway Harald.Alvestrand@maxware.no ------------------------------ From: George Woltman Date: Sat, 23 May 1998 14:35:16 -0400 Subject: Mersenne: Version 16 upgrade Hi all, When upgrading to version 16 be sure you upgrade the primenet.dll too. If you are using the http protocol, you must copy the new httpnet.dll on top of primenet.dll The server is out of exponents below 5,260,000. Over a 1,000 new machines have been added to the GIMPS pool lately. I'll work over the weekend making sure no ranges have fallen through the cracks. Best regards, George ------------------------------ From: Jean-Luc Cooke Date: Sat, 23 May 1998 16:30:42 -0400 Subject: Mersenne: Squareroot of Integers Hello, I'm trying to do something evolving encryption and I need to take the square root of a large integer. The software package I'm using doesn't have a functions for that. Can someone please give me one? Preferably a Maclaurin-Taylor Polynomial summation or something that fast. TTYL JLC - -- < censored :) > ------------------------------ End of Mersenne Digest V1 #366 ******************************