RE: Mersenne: Factors
Hoogendoorn, Sander writes: Torben Schlaqntz wrote: It seems to me that this k (in 2kp+1) is never: 4,12,20,28,36,46,52,60,68,76,84 at least for less than M416.947. Am I again a fool for a pattern already proved? It has been proven that k = 1 or 7 mod 8 Careful! It has been proven that _factors_ are of that form, not that the k's (of 2*k*p + 1 where 2*k*p + 1 is a factor of M(p)) are of that form. k, in fact, can be 0 mod 4, e.g., since, if a factor is 1 mod 8: factor = 2*k*p + 1 = 1 (mod 8) 2*k*p = 0 (mod 8) k*p = 0 (mod 4) k = 0 (mod 4) ... since p, being prime, is not 0 mod 4. This occurs, e.g., for M(11), as one of the factors is 89. Will _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors
Alexander Kruppa writes: Torben Schluntz wrote: I'd also like to know about any number fully factorized, whatever size it might be, and whatever size the factor(s) might be. Try Will Edgingtons's page, http://www.garlic.com/~wedgingt/mersenne.html . Use used to keep a comprehensive archive of known Mersenne factors. I am not sure how up to date this files are, but it is a good starting point. I still keep the data, but have not had time to update the online copies for a while now for several reasons that have nothing to do with GIMPS or other Mersenne stuffs. For example, the current primary cause of my lack of time is my new project at NASA/Ames: the AI-based planning software that I've been helping to develop for the past few years has been selected, this past Nov., for use by the upcoming Mars 2003 rover missions, to assist the human planners figure out what each rover can likely do during each Martian day. When I have time, I also maintain the mers package of programs - all in C source code and as portable as I know how to make them, which, of course, usually makes them slower than the other available programs - to do various things with Mersenne numbers, including verify that factors are prime, factor any composite factors, try to factor Mersenne numbers with Mersenne primes for exponents, etc., as well as the more typical tasks like Lucas-Lehmer tests, trial factoring, ECM, and P-1 of Mersenne numbers themselves. The URL given by Alexander is the primary one, which should have links to all sorts of other things, on my site and several others. Will _ Unsubscribe list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factor98
Reto Keiser writes: Where can I find the p-1 tool factor98.exe? As far as I know it supports p-1 factoring furteher than prime95 (prime95 only allows a b1 up to 700M). is this tool still available? As Stefanovic as already replied, yes, it's still out there. Further, I still have several Factor98 (and Factor95) save files for certain small Mersennes. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Linux And The Slippery Gnome
Trying to start a PrimeHunt on a Linux box, but can't find the
Gnome switch/requeste(o)r to get the screen resolution down enough
so I can read without a microscope. Can anyone help? Am running
Redhat 6.1 with a VooDoo 3500 GFX card.
Presuming you're running in an xterm window, try holding down a control
key and pressing holding your third mouse button while in that
window; xterm should bring up a list of font sizes. Simply release the
mouse button while the mouse cursor is on the one that you want to try.
This means that each xterm can have a different font size, if that's
what you want. The font, including size, can also be given on the
command line, as in 'xterm -fn 9x15bold' (e.g.). 'xlsfonts' will list
the fonts your X11 server knows about, but it's usually a very long
list, so you probably want to redirect it into a file ('xlsfonts
file') or something similar ('xlsfonts | more', perhaps).
Setting the font you want so that new xterms start with it is somewhat
messy, usually involving your ~/.Xdefaults file, but there may be a
configuration tool in Gnome that I'm not aware of (I was using X11
before Linux was created, let alone before Gnome, so ... :).
Some X11 configurations, usually declared in /etc/X11/XF86Config,
support more than one video resolution, which is usually changed while
running X with control-alt-(keypad's + key) and control-alt-(keypad -).
These support virtual screens in that the pixels that fit within the
display area are only part of what X11 is actually displaying; simply
try to move the mouse off the edge of the screen towards what you want
to see that's off the edge. The size of the virtual screen is only
limited by the amount of memory your video card can access and the
color depth (256 colors fit in 8 bits, e.g., as Mersenne hunters
should know :).
Will
http://www.garlic.com/~wedgingt/mersenne.html
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Factoring Assignments: Are They Always First-Time?
Stefan Struiker writes: When a requested factoring assignment is listed with, say, 52 in an account log, does this mean it has been factored to 52 bits, but _without_ success? Yes, the number should have no factors less than 2^52. Or could a factor have already been found in some cases, but less than 52 bits long? Nope, unless the factor was not reported for some reason (bug, disk crash, etc.). My strategy in factoring 13.3 mill exponents and up, is to save L-L testing and DCing time by knocking some out early. Seem to be on a roll, too, with factors found 40% of the time, with a turnaround of 40 hours per. That's a very high rate of factors, I'd've thought, but that happens sometimes. In any case, Prime95 "knows" how much factoring work should be done for a particular Mersenne number before starting an LL test (first or double-check) on it and will do more factoring if the data it gets from Primenet (or other source) indicates the number has not been factored "enough". The predicated chances of finding a factor during trial and P-1 factoring is taken into account, along with how long the factoring takes to do and how long the two LL tests will take. So your phrase "knocking some out early" is exactly correct: if noone tries to factor a particular Mersenne number before it is given to a Prime95 that wants to run an LL test, that Prime95 will do some factoring first, usually before it even finishes the prior Mersenne number's LL test (to make sure it has "enough" work in worktodo.ini). Eric Hahn writes: If it's listed as 52 in the fact-bits column of the report, it means that it's been trial-factored thru 2^52 without any factors being found. Currently, all exponents thru Prime95's limit of 79.3M have been factored to at least 2^50... If a factor is found for an exponent, it's eliminated from further testing of any kind. Yup. Here's a short summary of my current data. For Mersenne numbers with prime exponent that have no LL test nor a factor, here are the smallest exponents trial factored only as far as the last column: M( 5178743 )U: 2^62 M( 8896813 )U: 2^61 M( 9993539 )U: 2^60 M( 10078559 )U: 2^55 M( 11300657 )U: 2^54 M( 11505331 )U: 2^53 M( 11521879 )U: 2^52 M( 20500019 )U: 2^51 M( 30100181 )U: 2^50 M( 79300037 )U: 2^45 M( 79306169 )U: 2^43 The exponents above 79.3 million have probably only been worked on by me, personally, since they're above Prime95's limit, but I'm still a bit surprised they haven't been factored further; trial factoring to the same depth is _easier_ for larger exponents, not harder. Jeff Woods writes: Isn't the factor itself verified? Yes, if only by me, as I noted in another thread in the last couple of weeks. Will http://www.garlic.com/~wedgingt/mersenne.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Common practice for P-1 math?
I was wondering if it was common practice (ie: the norm) for P-1 to take the product of two or more factors when giving out a found factor, if two of more factors are found? Yes, if both factors are "smooth" enough, they could be found as their product, rather than individually. "Smooth" is defined as one less than the factor having no factors larger than the stage one P-1 bound plus up to one factor between the stage 1 and stage 2 bounds. To clarify, I was curious about how P-1 would indicate more than one factor being found. So, I took M113 and fed it into Prime95 with the bounds of B1=200, B2=2. Prime95 notified me that P-1 had found a factor in Stage #1, and that the factor was 9734174361238150513. This factors out to 3391 * 23279 * 65993 * 1868569, all of which are known factors of M113. For example, all the primes factors of 3390, 23278, 65992, and 1868568 are likely smaller than 200. If not, at most one factor of each number should be between 200 and 20,000. Note that there are three factors of 9734174361238150512 that are larger than 20,000; that doesn't matter. Because of this possibility of new factors being composite, I sometimes run a script that checks for composite factors in all my data and my update scripts check all new factors against smaller factors for the same exponent (to see if the smaller factor is a factor of the new factor). All new factors are also checked to verify that they are actually factors and whether they are also factors of some smaller Mersenne; the latter is not uncommon for new factors found by P-1 or ECM for composite exponent Mersenne numbers, but cannot happen for prime exponent Mersennes. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: What Happens Once A Factor Has Been Reported?
Once a factor has been logged for an M-candidate, either by P-1 or by "the other" method, what M-happens? Is a different sort of double-checking automatically done? I've forgotten what GIMPS or PrimeNet do in this regard, but all Mersenne factors sent to me - and George Woltman and several other people send all the factors they know about to me at some point - are verified to be correct by my update scripts. The actual calculation is done by a short function in the UNIX bc (basic calculator) command, which is not exactly speedy (nor slow - it's a very fast algorithm, that loops over the _bits_ of the Mersenne exponent), but it is completely independent, code-wise, from all the GIMPS and mers package programs. My update scripts also automatically download all the new data from ftp://mersenne.org/gimps, Paul Leyland's Cunningham Project site, Dr. Wagstaff's site at Purdue, and a few others, typically once every week or two. Will http://www.garlic.com/~wedgingt/mersenne.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Just curious
Aaron Blosser writes: I don't suppose George could just program something into the code to have it check for the user being idle (like the screen saver check does, but independent of the system screen saver routines) such that if the user doesn't hit a key or move the mouse for xx minutes, it would begin it's calculations (still at whatever priority you set it to...idle by default), but when the user is hitting keys or moving the mouse, it'll stop calculations altogether? That may allay the (unfounded) fears of some that Prime95 somehow steals cycles from other running programs. Unfortunately, I have personal experience in this area, though not with Prime95. My own (UNIX-based) Mersenne programs and scripts, from before GIMPS started, included checks not only that all logged on users were idle for at least three hours, including their terminal, mouse, and keyboard, but also that the load was only the 1.0 due to the program itself (and less than 0.1 or so when starting). These checks themselves (that the load remained low and any users were still idle), when performed every two minutes under SunOS 4.x on the SPARCstation 1's and 2's that were available at the time, usually kicked the load average up another 0.5 or so. But two minutes is quite a while to wait for something hogging your CPU to stop. At least according to the ten or so people that complained out of the roughly 100 computers my scripts were running on for a couple of years. And the scripts were careful to start only after hours, even if the computer appeared idle during the day. And the programs that did the actual work (almost always trial factoring because I didn't have an FFT-based LL program) always ran at the absolute lowest priority UNIX offers. Note further that checking to start things was done remotely; there was _no_ process of mine on the local machine when it was not idle, not merely a process only checking for idleness: the load average and user list could be checked without any local process. There were _still_ complaints. Even though the only thing that some of them could point at that indicated "slowness" was the load average being 1.0 instead of 0.0. So, no matter how much CPU you think this sort of change could gain GIMPS, I must suggest that it _not_ be done. Except - perhaps - under the control of another .ini variable and the default is to do things the current way. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: New mersenne.html MMPstats.txt, DB.nf bug fix
I've just updated my mersenne.html page, mostly by adding a new section of "quick links" near the top that point to other people's sites, including a new one for the factoring status of Fermat numbers maintained by Jocelyn Larouche. I also updated the data on M(M(p)) factoring progress and added a link pointing to the new Fermat number page from it as well. The only new data is from Tony Forbes, I believe. Lastly, a bug in my update scripts that affected the contents of the DB.nf file has been fixed. DB.nf lists the trial factoring progress for all Mersenne numbers with prime exponents that are known to be composite but for which we have no known factors. The bug caused some exponents that should have been included to be skipped, including M(727). Will http://www.garlic.com/~wedgingt/mersenne.html Mersenne number info, software http://www.garlic.com/~wedgingt/MMPstats.txtData on M(M(p)) factoring http://www.garlic.com/~wedgingt/mersdata.tgzData on M(n), tar'd gzip'd http://www.garlic.com/~wedgingt/mersdata.zipSame, zip'd _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: SPARC/Solaris client
Eric Bravick writes: Is anyone actually working on the SPARC/Solaris client? I've seen it under "coming soon" ever since I joined the effort. Speaking as someone with a bunch of SPARC CPU's sitting around doing (almost) nothing, I'm kind of interested in seeing this port... Yes, a lot of people are waiting quite patiently. Unfortunately, I have not had enough time, partly - but nowhere near entirely - because I don't have access to a SPARC any more. But, since you don't say what kind of client, I'll point out that there are LL test and factoring programs out there that run on SPARCs; the only current lack is automatic PrimeNet support. Using PrimeNet's manual test pages is quite feasible. Will http://www.garlic.com/~wedgingt/mersenne.html Mersenne info links mers.tgz Mers package (C software) mers.zip Zip'd instead of tar'd gzip'd _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: M727 has a factor?!?!?
P-1 on P727 with B1=30, B2=1 P727 stage 1 complete. 116 transforms. Time: 0.018 sec. (4659194 clocks) Stage 1 GCD complete. Time: 0.001 sec. (164887 clocks) P727 has a factor: 11633 This meets all the criteria too 1) 11633 is PRIME. 2) 2kp+1 = 2*(8)*727+1 = 11633 3) 8n+1 = 8*(1454)+1 = 11633 4) 2^p (mod n) = 2^727 (mod 11633) = 1 11633 divides M1454 where 1454 = 2*727, but 11633 does not divide M727. Your #4 calculation has a bug, probably a rounding error; the correct result is 11631. In fact: M( 1454 )C: 11633 M( 1454 )C: 52068472442119144511578580563 M( 1454 )C: 59803996769241650545074361210286131 M( 1454 )D That is, M1454 is considered to be completely factored even though it is a multiple of M727, which is known to be composite but has no known prime factors. There are other cases like this in the data. From my "reverse method" program, I should now have all factors less than about 1.6 billion for _any_ Mersenne number with an exponent less than 2^30 (just over a billion). Will http://www.garlic.com/~wedgingt/mersenne.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: P-1 factoring of large exponent Mersenne numbers
Paul Leyland writes: A nasty thought just struck me. It struck me in a different context some time ago; it might even be archived. When applying P-1 to mersenne numbers, an additional 2*p ought to be included in the product, over and above all the powers of prime B1. Can anyone who knows for certain reassure me that this has been done for the prime95 V20 implementation? I don't know about the prime95 V20 implementation per se, but George was aware of this quite some time ago, because he once told me that it is/was being done in Factor98, his older, stand-alone, P-1 factorer. While I'm here, I still accept P-1 factoring reservations and Factor98 and Factor95 save files for small exponent Mersennes. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: p-1 and trial factoring
Reto Keiser writes: A lot of factors of exponents between 1 and 100 were found using the new P-1 method. Is there a database which contains which exponent were tested using which B1 and maybe a database od the save files? The P-1 data is also collected by me, in the 'o:' lines of my programs' usual format (merfmt.txt). I also collect P-1 save files and try to keep track of who is running Factor98 and other (older) P-1 programs on which exponents. Note that this will likely not affect the new GIMPS and Primenet P-1 efforts, as I'm concentrating on small exponents where complete factorizations might be feasible; the new GIMPS P-1 efforts will be to find a first factor to avoid having to do LL tests. Will http://www.garlic.com/~wedgingt/mersenne.html mersfmt.txt _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Trial-factorers
Eric Hahn writes: I'm looking for program(s) capable of trial-factoring prime exponent Mersenne numbers (using 2kp+1) meeting the following requirements: 1) Capable of trial-factoring any exponent 1 (at least to some considerably large number, say 1 trillion?) If your C compiler supports a 64 bit integer type, the mers package factorers mersfacgmp and mersfaclip can use that for the exponent, allowing exponents to about 2^64/24 (about 768 quadrillion, ~7e17). The '/24' can be reduced to '/2' by using a lower number of sieve passes. If you don't have a 64 bit integer type, then you're limited to 2^32/24 or so (about 178 million). See setup.h for the #define's of BIG_LONG. As I recall, Brian [Beesley] mentioned something once about having a program that could test an exponent of an arbitrary size... Brian?? The mersfac* code could be modified to allow arbitrary exponents without a lot of work, but it wouldn't be trivial to do either. I do intend on doing it someday, however, to support the factoring of the M(M(p))'s, as the sieving of trial factors in mmtrial is not as good as that in mersfac*. 2) Capable of testing a factor of any size. (even over the 2^76 limit of Prime95). Mersfacgmp and mersfaclip use the FSF's libgmp and A. Lenstra's freeLIP libraries, respectively, for the trial factors. 3) Capable of trial-factoring a range of k's. (example: from k=1000 to k=2500) As Alexander Kruppa noted, this is not supported directly, but could be done fairly easily with bc. And it could be added to mersfac* directly without a lot of effort; see rw.c where it reads the command line and the input file(s), especially the -m flag. The -a flag is probably also of interest; without it, mersfac* will stop when it finds a factor rather than looking for all the factors in a range. The simplest way to do it with bc would be to create 'G' (gap) lines like: M( exp )G: start stop where 'exp' is the exponent and 'start' and 'stop' are the first and last trial factors to test. In any case, part of the output will be 'J' (join) lines, that show exactly what range of trial factors were actually tested; please include them in any output of mersfac* that you send to me. Will http://www.garlic.com/~wedgingt/mersenne.html mers.tar.gz mers.tgz mers.zip ` _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Updated web pages; new factor counts percentages
I've updated my web pages Yet Again, including adding some quick links at the top of mersenne.html to the other Mersenne related files on my web site. The 1stfacnt.txt file is gone; I've split it into facntHU.txt (for incompletely factored Mersennes) and facntD.txt (for completely factored Mersennes) and the counts are no longer only for first factors, but for second factors, third factors, etc., as well. The files also provide counts for all exponents, for only prime exponents, and percentages with at least one, at least two, etc., factors out of the exponents for which I have any data at all, rather than just counts of factors. There's a significant drop in the percentages of prime exponent Mersennes with known factors for exponents above 10 million, but that may simply be because GIMPS and Primenet factoring haven't done much for exponents that large yet. Comments? All Mersenne numbers with prime exponents less than 80 million have been trial factored to at least 2^41. All Mersenne numbers with exponents under 24687 have had primality checks of their cofactors. All SPRP cofactors with less than 836 decimal digits have primality proofs (with a few exceptions; the binary version of ECPP that I have crashes for some numbers). Will http://www.garlic.com/~wedgingt/mersenne.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: Factors Everywhere
Brian J. Beesley writes: 1) I don't see any particular need to make available files in human- readable format, provided that we provide a specification for the file, and also binary executables for common platforms for converting a machine-readable file to human-readbale format. I, personally, have no way of producing executables except for Intel CPUs, and presently only for Linux (I just yesterday got a old P100 machine up running Win98 (and Prime95, of course:)). I have thought about a binary data format off and on for a while now, but mostly in terms of making updates easier by designing a format that can be updated in place (at least most of the time), which is a different problem. On the other hand, it could be that "zipping" a human-readable format file provides near-optimal compression. Most likely, and this avoids having to provide executables to read it: they're already out there. 2) Since factors are of the form 2kp+1, it is only neccessary to list p k. This saves a significant amount of storage (compared with listing p and 2kp+1) and the proper factor is easily recovered. Unfortunately, it's only this simple when p is odd. For even p, factors can be one more than any multiple of p, not just one more than even multiples of p. And I'd really rather not have a different format for even exponents ... 3) If the data was held in variable-length records in a format similar to p,n,k1,k2,k3... where n is the number of known factors and k1, k2, k3,... are the multipliers for each of the known factors in turn, this would save much duplication compared with the current format (of factor.txt). This is also a good idea, but a few of the lines would be _very_ long, which some text editors and other programs will have problems with. I'd also suggest dropping n; including it doesn't really add anything and it can be computed quickly from the other data. Perhaps something like: n p,pk1 ,pk2 ,pk3 Note that M(n) has no known factors. 4) For values of p which fit into a (integer) CPU register and "small" values of k (up to approx. 64K), trial factoring is so fast that I doubt it would be any faster to search a file than to repeat the calculation - even if the file is already available locally. Yes, but then there's no way to be sure whether the factor is already known or not. There was a bug in an early post-GIMPS-start factorer of mine that caused it to miss _exactly_ one factor, of M(47). If I hadn't had an explicit list of factors to compare with, I would have never found the bug. Perhaps the file should contain a "flag" denoting that factors are known, but have been omitted for this reason. This might be enough, though. But note that this can already be done using the DATABASE format, if you're willing to omit all factors. Hm; so perhaps a DATABASE file with all the exponents and trial factoring extents and a second, human readable, file, as above, is a possibility. And I've long thought about a small program ( function) to do fast, binary lookups in large Mersenne data files like these (human readable or binary), akin to the common UNIX "look" program for dictionary files, but, of course, doing a numeric search rather than a dictionary search. We should still have a large master file somewhere, but this need not be uploaded frequently. I update my local copy about twice a week usually; it takes only a couple hours on my new PIII/450MHz machine and was well under a day even on my old P233MMX system. These times include automatically downloading data out there every few days to a month, as appropriate for the particular file. 5) Following on from (4), it seems to make sense to record the highest value of k tested by trial factoring, rather than the maximum number of bits. This is lacking in the DATABASE format, but my format implies this info. And, for a year or more, I've actually been treating the "distance" in k's to get to the next power of two as a "gap" in the trial factoring data and thus most of it is just above powers of two. Note also that exponents with known factors can be worked on by Prime95 again, after mersfacgmp or some other factorer pushes the extent past the next power of two above a factor. 6) PrimeNet trial factoring has moved well into the 10 millions, however George's factor.zip file contains data only up to 10 million. Yup. This also means that my factors and his for exponents above 10 million have not been compared for some time. I know there is a problem with uploading the large files concerned; hopefully, the suggestions above will help to reduce the size of the file, sufficiently to make it feasible to expand the exponent range to cover (at least) the active Primenet assignments for long enough for cheap, high-speed Internet connectivity to become widespread. Or perhaps George should simply shift to the factors of the exponents
Mersenne: Factors Everywhere
Eric Hahn writes:
[I've already replied in detail to Eric privately.]
I've come up with this SWAHBI (like a SWAG, but an idea
instead of a guess).
Hm, "silly, wild *ssed, half-baked idea" ? That's not an acronym I've
seen before.:)
What I'm looking for is the following two items for *all*
Mersenne numbers 2^p-1 where p is prime and p1:
1) All known factors (including, but not limited to,
the smallest known factor (noted if it isn't))
My data contains some prime exponents with as many as eight known
prime factors.
2) Largest potential factor attempted
I have this as well, but there are also some gaps in the trial
factoring efforts to date, which I also keep track of and try to
close.
I ask that the two items are human-readable at the
very least.
The format I use is described in the mersfmt.txt file; it is human
readable, being primarily alphanumeric plus parentheses and colon (:).
Conversion to just about any other printable format is easy; UNIX has
lots of tools that allow this sort of text manipulation.
I've pulled a couple of files off mersenne.org
(FACTORS.ZIP and NOFACTOR.ZIP) as well as off
Alex Kruppa's page. While the files appear complete
as far as I can tell, they only cover the ranges
of p between 11 - 9,999,991 and 33,219,281 - 35,999,993.
Correct. George has still not asked me for my data for exponents
above 10 million, but it's probably almost as easy to retest as to
have me send (my data isn't very deep for the exponents above 21
million or so), and makes for a good double check.
They also don't cover *all* known factors!
Correct; since GIMPS is mainly looking for Mersenne primes, Prime95
stops at the smallest factor (which is not always the first factor it
finds for an exponent because of the 16 pass approach in the sieving
code).
Any and all information on the ranges between 10M - 33.22M and
above 36M is greatly appreciated, as well as any known factors not
listed in the files I've pulled.
My prime exponent data for all ranges is now about 111 MB; this
includes all known factors, each exponent's largest attempted trial
factor, and all the ECM and P-1 effort (but no P-1 save files). The
gaps data is another 9MB, and the P-1 save files, mostly from
Factor98, are about another 110 MB. All but the P-1 save files use
the format described in:
http://www.garlic.com/~wedgingt/mersfmt.txt
... which is human readable and accepted by the mers package programs.
The P-1 save files are understood by the mers package's extract enough
to print most everything but the "residue" itself, including the beta
release's extract understanding the new P-1 save file format of George
Woltman's Prime95 v19. Extract's understanding of the P-1 save file
formats will be extended, when I get around to it, to converting from
one P-1 format to another.
Conrad Curry writes:
Will Edgington maintains this information, but it may be
hundreds of megabytes in size. If a website, such as
Entropia, has the space it will be useful to make this database
available (in many small compressed files) so that others may
use it.
Yes, but the first problem is that my 56Kb modem is in the way.:(
But I would be willing to upload it a range at a time over a month or
so, going back to the start to update ranges that have changed since
their last upload, if someone out there has enough web disk space
for it.
And what GIMPS needs, the list of prime exponents with some data but
no known factors, is still quite small, especially in the binary
DATABASE format (which extract can print in the mersfmt.txt format);
that DATABASE file for all prime exponents with data but no factors is
only 2MB presently. It is produced by the contract program during my
updates and put in the mersdata.{zip,tgz,tar.gz} file.
Eric Hahn writes:
If no information is known where p100M, then what can I do??
I have some data for exponents over 2^31. The smallest prime exponent
with no data is only 21556027 presently (though I increase it some
with every update), however, and most of the data is below that.
Also, generating new data for a given prime exponent under about 2^60
(if your machine has an eight byte integer type available in C) or so
is easy using mersfacgmp; all it takes is CPU time.
Will
http://www.garlic.com/~wedgingt/mersenne.html
mers.tgz
mers.tar.gz
mers.zip
mersfmt.txt
mersdata.tgz
mersdata.tar.gz
mersdata.zip
_
Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: M(M(127)) and other M(M(p))
Chris Nash writes: I really hope that neither Will Edgington (with M(M(6972593))) nor Chip Kerchner (with M(M(1398269))) dedicated any computer time whatsoever to search for factors 2*k*M(p)+1 up to k=4. I didn't, except perhaps to have mmtrial verify that the smaller k's were sieved out. As Will's page http://www.garlic.com/~wedgingt/MMPstats.txt points out, since M(p)=1 mod 3, k cannot be 1 mod 3. Also, since M(p)=-1 mod 8 for odd p=3, k must be 0 or 1 mod 4 (otherwise 2 is not a quadratic residue of this supposed factor, the 8x+-1 condition). Thanks; I'll add this to the next MMPstatus file and to mmtrial.c. Should have thought of it myself, but quadratic residues are still new to me. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Updated info on M(M(p))
The list of known factors of iterated Mersenne numbers recently forwarded to these lists include all factors known to me, but the search limits have been significantly improved, some well before Nov. 1996 I believe. The MMPstats.txt file that I maintain is about to be updated to the following. If you do not have web access, feel free to email me; I can arrange to have it emailed to you automatically when it changes as part of the script that updates my web pages. Note the implication that I try to keep track of who is working on which exponents; this is simply to avoid duplication of effort. Will http://www.garlic.com/~wedgingt/MMPstats.txt mersfmt.txt mersenne.html Status of M(M(p)) where M(p) is a Mersenne prime $Id: MMP.status,v 1.49 1999/09/23 23:00:18 wedgingt Exp $ A factor will always be of the form 2*k*m + 1 where m = M(p) = 2^p - 1 is a Mersenne prime. 'U: k=61' is short-hand that trial factors = 2*k*m + 1 have been checked. The format is otherwise based on my usual Mersenne format, described in A HREF="http://www.garlic.com/~wedgingt/mersfmt.txt" mersfmt.txt /A. Note that, since m == 1 (mod 3), factors of M(m) cannot have k == 1 (mod 3) since 2*k*m + 1 == 0 (mod 3) in that case. Chris Nash pointed out on the Mersenne list (1999 Sep 22) that, for odd Mersenne exponents, k must be 0 or 1 mod 4, since, otherwise, 2 is not a quadratic residue of the supposed factor. Credit for first find of each factor (C: line) is given to the best of my knowledge. The one with my name is from my pre-GIMPS (see www.mersenne.org) data and probably pre-dates W. Keller's (also unpublished) 1994 discovery. Note that I have no P-1 factoring info for M(p) M(17) and no P-1 save files. M( M( 2 ) )P M( M( 3 ) )P M( M( 5 ) )P M( M( 7 ) )P M( M( 13 ) )C: 338193759479 # k = 20644229, Wilfrid Keller (1976) M( M( 13 ) )H: 2^55 # Charles F. Kerchner III, Prime95, stopped M( M( 13 ) )H: k=2199291723780 # " M( M( 13 ) )o: 3e9 # Warut Roonguthai, Factor95, stopped (no P-1 save file) M( M( 17 ) )C: 231733529# k = 884, Raphael Robinson (1957) M( M( 17 ) )C: 64296354767 # k = 245273, Wilfrid Keller (1983?) M( M( 17 ) )H: 2^60 # Charles F. Kerchner III, Prime95, stopped M( M( 17 ) )H: k=17592320263168 # " M( M( 17 ) )o: 3961649 # (unknown, no P-1 save file) M( M( 19 ) )C: 62914441 # k = 60, Raphael Robinson (1957) M( M( 19 ) )C: 5746991873407# k = 5480769, Will Edgington (Wilfrid Keller 1994) M( M( 19 ) )H: 2^60 # Warut Roonguthai, Prime95, stopped M( M( 19 ) )H: k=4398054899728 # " M( M( 31 ) )C: 295257526626031 # k = 68745, Warut Roonguthai (Guy Haworth 1983) M( M( 31 ) )C: 87054709261955177# k = 20269004, Tony Forbes (Wilfrid Keller 1994) M( M( 31 ) )H: 1984697089407967495 M( M( 31 ) )H: k=462098301 M( M( 61 ) )U: k=9363198284 # Landon Curt Noll, own program, stopped # Sturle Sunde, continuing 1999 Sep 22 M( M( 89 ) )U: k=13516351613# Landon Curt Noll, own program, stopped M( M( 107 ) )U: k=2016797660# Landon Curt Noll, own program, stopped M( M( 127 ) )U: k=12500 # Landon Curt Noll, own program, continuing M( M( 521 ) )U: k=2000 # Rob Hooft, mmtrial, stopped M( M( 607 ) )U: k=617 # Samuli Larvala, own program, stopped M( M( 1279 ) )U: k=17758437 # Conrad Curry, mmfac (see below), stopped M( M( 2203 ) )U: k=11356378 # Conrad Curry, mmfac, stopped M( M( 2281 ) )U: k=3026696 # Rob Hooft, mmtrial, stopped M( M( 3217 ) )U: k=304345 # Eric Prestemon, mmtrial, stopped M( M( 4253 ) )U: k=58 # Conrad Curry, mmfac, stopped M( M( 4423 ) )U: k=88 # Conrad Curry, mmfac, stopped M( M( 9689 ) )U: k=69034# Conrad Curry, mmfac, stopped M( M( 9941 ) )U: k=14000# Conrad Curry, mmfac, stopped M( M( 11213 ) )U: k=2573# Eric Prestemon, mmtrial, stopped M( M( 19937 ) )U: k=1501# Conrad Curry, mmfac, stopped M( M( 21701 ) )U: k=7123# Conrad Curry, mmfac, stopped M( M( 23209 ) )U: k=2731# Conrad Curry, mmfac, stopped M( M( 44497 ) )U: k=30169 # Chris Nash, by sieving possible factors, 1999 Sep 21 M( M( 86243 ) )U: k=271 # Conrad Curry, mmfac, stopped M( M( 110503 ) )U: k=7 # Will Edgington, mmtrial, stopped M( M( 132049 ) )U: k=40 # Will Edgington, mmtrial, stopped M( M( 216091 ) )U: k=19 # Charles F. Kerchner III, own program M( M( 756839 ) )U: k=23 # Charles F. Kerchner III, own program M( M( 859433 ) )U: k=32
Re: Mersenne: Simple question about P-1 factoring method
[EMAIL PROTECTED] writes: Am I correct? Or could a factor smaller than 2*k*p + 1 be missed in some cases? In the last example a factor 16*97 + 1 could be missed. Otherwise all factors below 2*k*p + 1 should be found. One extra squaring will achieve the 2*k*p + 1 bound. Gack. Yes, I should have caught that myself; it's the same situation as for p, isn't it? The power of the P-1 algorithm is that it can potentially find many larger factors, such as 252*p +1 using a stage 1 bound of 10. Of course; I realize that. I was only looking at it this odd way because of the trial factoring gaps I need to close. Since I already have the P-1 data, it's easy to do this. If I didn't already have the P-1 data, it would (most likely) be faster to simply do the trial factoring. Further, it seems to me that doing trial factoring to extend from P-1 factoring doesn't make sense. Note that trial factoring would have to check 2*(k + 1)*p + 1 next; P-1 only has to do k + 1 next if it's a prime or prime power (or p). Trial factoring could use the knowledge of P-1 being done thru a stage one of k by "sieving" the trial factors based on one less than the trial factors as well as the usual sieving of the trial factors themselves, but that's exactly the set that P-1 would test with larger stage one bounds, and P-1 would, as you point out, find more factors with at most a little extra work. Right? I've heard that P-1 is "more efficient" than trial factoring; does the proof go along these lines? Or is it more complicated than this? Of course, if this is correct, then I should fill the trial factoring gaps using P-1, at least to the largest stage one the program that I use supports. Does it matter whether p is prime or not? I don't think so, but ... Not if you always include an exponentiation by p, and repeat it if necessary as you do primes = k. So a composite p should effectively be treated as if it were prime in the powering even though it's prime factors are being used as well? That certainly makes sense, given the extra power of 2 and of p used because of the special form of Mersenne factors. Thanks, Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Up to date benchmarks sites?
The benchmarks site linked from www.mersenne.org: http://www2.tripnet.se/~nlg/mersenne/benchmk.htm ... has not been updated in over a year. Is there an up to date one? Further, the link there to another site for non Intel/Cyrix/Mac/AMD systems at: http://www.via.nl/users/mccidd/html/mersenne/benchmark.html ... is timing out in the nameserver. Anyone know the status of it? Please reply to me privately; I'll reply to the list when I have solid info. While I'm here, I now have more room at my ISP, so I'll be adding more files there as I have time. I've just put mersdata.zip there again for those of you that have asked for that data but couldn't unpack mersdata.tgz for whatever reason. Will http://www.garlic.com/~wedgingt/mersdata.zip mersdata.tgz mersdata.tar.gz mersenne.html README.html _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: new accounts
Lucas Wiman writes: You could do factoring, the margin between factoring on a PC and an UltraSPARC should be much slimmer than LL tests. The last time I did timings like this - admittedly, probably over a year ago, but the mers package hasn't changed much since, especially in terms of performance - this is wrong. SPARC LL testing - especially with MacLucasUNIX - is much closer to matching Prime95 LL testing than SPARC trial factoring - with mersfacgmp, say - is to matching Prime95's trial factoring, by, as I recall, a factor of about 12. Could someone out there do some new tests and send me the info? I no longer have access to any SPARCs for Mersenne stuffs. Mersfacgmp can probably be helped significantly by adjusting the size of the sieve array and how many small primes are used to check the primality of the trial factors, however; would anyone like to try some experiments? I would add detailed info the the comments in the mers Makefile so noone has to repeat the testing. The UltraSPARC would probably significantly outperform a similar megahertz PC, if we had similarly optimized code running on each. Perhaps. I know my friend's SPARC (running at 233 mhz, bus 233 mhz) sure does outperform my PII (running at 233 mhz, bus 66 mhz) on most things. I have certainly seen this for most things involving large amounts of I/O; again, not recently. But the advantage seems to disappear or even reverse to the PC's favor once cost is taken into account. Will http://www.garlic.com/~wedgingt/mersenne.html mers.tar.gz ` _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Mp and E-Cash
Ken Kriesel writes: I think Duncan Booth's name at least ought to be considered when discussing the $ split. He wrote the first version of primenet server and client; Scott Kurowski continued from the starting point that Duncan provided. I suspect that Scott has considerably more total effort invested, but part of that is as a business venture. OK. Then what about John Sweeney? Jason Kline? Crandall Fagin? How about the people that wrote factoring code? As others have noted, this is a big can of worms that's just complicating things without really adding anything to the effort itself. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
RE: Mersenne: Mp and E-Cash
Lucas Wiman writes: I'm forced to agree with Aaron, aparently at gunpoint :-) (and I said this a while ago, BTW). Even if they (George and Scott) did this, then there would still be MacLucasUNIX, or everything else in the mers package, as well as Ernst's program, and good ol' lucas.c. MacLucasUNIX, mersenne1, etc., of the mers package can indeed be used to find such large Mersenne primes, right now, and someone out there is probably already doing it. But, if they are, they haven't told me and they are thus looking at exponents for which I have known factors; noone but me - and I mean noone, not even George - has all of my data for these large exponents. Any of these could be used. We've really got to put our feet back on the ground here. If we did put a license change on all of George's program derivitives, we would still have to get Will and Ernst to change their copyrights, and Richard Crandall. It's actually worse than this. I never intended to copyright any of the code I distribute, in part because some of it is already covered by copyright and/or patent for commercial purposes. Is trying to claim the EFF prize a commercial purpose? Don't ask me; I'm not a lawyer. Will _ Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: Another factor found for Fermat 16
Geoffrey Faivre-Malloy writes: I found another factor for Fermat 16. What do I do now? How can I factor this number that I found? Are there programs out there that will let me do that? Yes, there are such programs. One is ecmfactor, a program I maintain as part of the mers package at: http://www.garlic.com/~wedgingt/mers.tar.gz mers.tgz (two file names with the same contents). Ecmfactor uses the Elliptic Curve Method algorithm in the freeLIP library (written in C by Arjen Lenstra and presently maintained by Paul Leyland). If freeLIP compiles using your compiler, than ecmfactor should run fine. FYI, the factor is: M16384 has a factor: 3178457030898592746194675570663374420833971377365687459461386297851584459031 8073180374859604847822828243686877928403667633015295 I've appended the output from ecmfactor on this number. Also, Steven Whitaker is quite correct; M16384 is, usually at least, used to denote 2^16384 - 1, which is a Mersenne number. Fermat numbers are of the form 2^(2^n) + 1. However, since 16384 is a power of two, this particular Mersenne number, as Steven also notes, is related to the Fermat numbers, since: 2^(2*x) - 1 = (2^x)^2 - 1^2 = (2^x - 1)*(2^x + 1) (using the usual difference of squares method to get the two factors). Since 16384 is a power of two, this can be repeated several times on the 2^x - 1 half to get the factors that Steven lists. And, if you at all interested in prime numbers and factoring, then I strongly second Steven's suggestion of reading Chris Caldwell's web pages at: http://www.utm.edu/research/primes/index.html Will Ecmfactor says: % ecmfactor -d M16384.factor prime factor: 3 prime factor: 5 prime factor: 17 prime factor: 257 new cofactor is composite factor: 641 prime factor: 641 new cofactor is composite factor: 114689 prime factor: 114689 new cofactor is composite factor: 4179067011073 factor of factor: 65537 prime factor: 63766529 new cofactor is composite factor: 26017793 prime factor: 26017793 new cofactor is composite factor: 274177 prime factor: 274177 new cofactor is composite factor: 974849 prime factor: 974849 new cofactor is composite factor: 319489 prime factor: 319489 new cofactor is composite factor: 6700417 prime factor: 6700417 new cofactor is composite factor: 2424833 prime factor: 2424833 new cofactor is composite tried 1 curves at bound 100 without success tried 1 curves at bound 105 without success tried 1 curves at bound 110 without success tried 1 curves at bound 115 without success tried 1 curves at bound 120 without success tried 1 curves at bound 125 without success tried 1 curves at bound 130 without success factor: 45592577 prime factor: 45592577 new cofactor is composite tried 1 curves at bound 135 without success tried 1 curves at bound 140 without success tried 1 curves at bound 145 without success tried 1 curves at bound 150 without success tried 1 curves at bound 155 without success tried 1 curves at bound 161 without success tried 1 curves at bound 167 without success tried 1 curves at bound 173 without success tried 1 curves at bound 179 without success tried 1 curves at bound 185 without success tried 1 curves at bound 191 without success tried 1 curves at bound 197 without success tried 1 curves at bound 203 without success tried 1 curves at bound 209 without success tried 1 curves at bound 215 without success tried 1 curves at bound 221 without success tried 1 curves at bound 227 without success tried 1 curves at bound 233 without success tried 1 curves at bound 239 without success tried 1 curves at bound 245 without success tried 1 curves at bound 252 without success tried 1 curves at bound 259 without success tried 1 curves at bound 266 without success tried 1 curves at bound 273 without success tried 1 curves at bound 280 without success tried 1 curves at bound 287 without success tried 1 curves at bound 294 without success tried 1 curves at bound 301 without success tried 1 curves at bound 308 without success tried 1 curves at bound 315 without success tried 1 curves at bound 322 without success tried 1 curves at bound 329 without success tried 1 curves at bound 336 without success tried 1 curves at bound 343 without success tried 1 curves at bound 350 without success tried 1 curves at bound 358 without success factor: 190274191361 prime factor: 190274191361 new cofactor is composite tried 1 curves at bound 366 without success tried 1 curves at bound 374 without success tried 1 curves at bound 382 without success tried 1 curves at bound 390 without success tried 1 curves at bound 398 without success tried 1 curves at bound 406 without success tried 1 curves at bound 414 without success tried 1 curves at bound 422 without success tried 1 curves at bound 430 without success tried 1 curves at bound 438 without success tried 1 curves at bound 446 without success tried 1 curves at bound 454 without
Mersenne: Another factor found for Fermat 16
Geoffrey Faivre-Malloy writes: M16384 has a factor: 3178457030898592746194675570663374420833971377365687459461386297851584459031 8073180374859604847822828243686877928403667633015295 Further, if you try to divide this into M8192 (2^8192 - 1), you should find that it factors that as well. That is, I checked all the factors of the number above that my run of ecmfactor printed and they all divided M8192 or an even smaller Mersenne (and therefore M16384, M32768, etc). The factoredM.txt and lowM.txt files in mersdata.tgz on my web pages list, among other factors: M( 256 )C: 59649589127497217 M( 512 )C: 1238926361552897 M( 1024 )C: 2424833 M( 1024 )C: 7455602825647884208337395736200454918783366342657 M( 2048 )C: 45592577 M( 2048 )C: 6487031809 M( 2048 )C: 4659775785220018543264560743076778192897 To here, the Mersenne numbers are completely factored (and are therefore in factoredM.txt); from here on, the other (presumably larger) factors are not known. M( 4096 )C: 319489 M( 4096 )C: 974849 M( 8192 )C: 114689 M( 8192 )C: 26017793 M( 8192 )C: 63766529 M( 8192 )C: 190274191361 M( 8192 )C: 1256132134125569 M( 16384 )C: 2710954639361 M( 16384 )C: 2663848877152141313 M( 16384 )C: 3603109844542291969 M( 16384 )C: 319546020820551643220672513 My data contains no factors of M(32768) = M(2^15) or higher that are not also factors of a smaller Mersenne number. The ecm3 program of the mers package knows that composite exponent Mersenne numbers have factors equal to smaller Mersenne numbers and pulls all those factors out using repeated GCD's before trying to factor the Mersenne number it is told to factor. E.g., it should never print 319489 as a factor of M(8192) or any larger Mersenne, since 319489 factors M(4096) but it will print 319489 as a factor of M(4096) because it factors no smaller Mersenne number. Will http://www.garlic.com/~wedgingt/mersdata.tgz http://www.garlic.com/~wedgingt/mers.tgz Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Defragmenting and Security
[EMAIL PROTECTED] writes: How about the No Icon option? (You can still access it by trying to run Prime95.exe again). And have it configured as a Win95 service. I'm not sure if my system is an anomaly, but even the Three-Fingered Salute doesn't show Prime95 to be on the list of tasks to shut down. If the weasel who stole your laptop doesn't look hard enough, he will then have almost no chance of finding the program. Heh. I've noticed that my mother's Win98 machine also does not list Prime95 in the Startup menu, presumably because it's running as a Win98 service. But it does show briefly as a very small window in the lower left hand corner of the screen during reboots while it's asking for her password. If you were to mark it as a hidden file as far as MSDOS is concerned and put it in the Windows directory or a subdir thereof, it would be even harder to find. In regards to defragmenting: I have defragmented my C hard drive (where Prime95 runs) a number of times, and it almost always takes over 30 minutes, which is how long Prime95 waits before writing save files. MS Defrag (taken from Symantec - look at the copyright notice!) is just as well-behaved as good old FAT16 Symantec Norton Utilities' defragmenter. Apparently, when a program writes to the HD, MS Defrag detects it and rescans the hard drive's contents. No errors are produced. If you are using a Symantec product, then it will also be well behaved. I don't know about other programs or non-Win95 systems. My mother's machine also runs Prime95 24/7 and defrags automatically every other week via the task scheduler. No problems yet of any kind. Seti@Home, on the other hand, is not only a bigger resource hog, it also interferes with Iomega's Zip backup program, causing backups to fail by crashing the program right at the end, just before the backup is complete. As I joked to her, I guess E.T. doesn't want her system backed up.:) Prime95, of course, doesn't interfere with backups. Will Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Re: factoring 10^7 digits (was LL and factoring quitting)
We will of course have to check factors considerably further than we are doing on our current exponent range (due to the increased LL iteration time.) Yup. And don't forget that the larger the exponent, the fewer the possible factors in a given range (e.g., from 0 to 2^40 or 0 to 2^63). Yes - on the principle that it's worthwhile to spend 5% to 10% of the LL testing time attemptimg to find at least one factor before we run a LL test, the pre-factoring should be run for 3 or 4 weeks per exponent first (assuming PIII-500 class power). At a rough guess, that's up to 2^66 or 2^67, but we don't have any benchmarks yet. Oh, but we do. George's factoring is not the only one out there. In particular, I maintain, as part of the mers package, factoring programs that use the freeLIP and gmp libraries to try arbitrarily large factors. Since George's program uses the Intel CPU's 64 bit mantissa floating point operations, it is limited to checking possible factors up to about 2^63. Of course, trial factoring to 2^40 is very quick - I spent only about 2 (PII-350) CPU hours spread over all 159,975 candidate exponents in the range I selected. But that's enough to eliminate a third of them. In fact, there was a problem with a particular version of George's factorer such that it didn't always find factors _smaller_ than 2^32 or so. And this was discovered only when GIMPS was expanding to the current high exponent of 20.5 million or so. So I ran mersfacgmp to find all the factors less than about 2^33 for all prime exponents up to about 21.5 million. It took a couple of days on my (then) 90MHz Pentium. Maybe we should start checking factors in (the range of prime numbers used in your database) in 2^40 segments, between you and me (and others?). Others, including myself, have already done parts of this. The data that I have collected from them all is significantly larger than the web-accessible disk space I have. But feel free to send me more factoring data and I'll send, in suitably sized chunks, whatever parts of the data that I have that you want. When you send me the source, I'll try to port it GCC (then maybe we can make something useful out of it :-) No need; mersfacgmp already supports GCC, since my primary machine is RedHat Linux v5.2. But see below for reasons that another program, independently developed, can be very useful. What type of sieving did you do (if any) ? Mersfacgmp does essentially the same sieving as George Woltman's code, though in a different order so as to test possible factors in order. Mersfacgmp tests possible factors in order so that the "checkpoint" file is just the largest number attempted so far. George's factoring checkpoint files are in binary and include the sieving pass number (out of 16). George's code is organized that way for the speed advantage. Did you write the modpow routine, or was it included with some math header? George got the basic algorithm from Knuth, I believe, and pointed it out to me not long after GIMPS started. It sped up my pre-GIMPS factoring program by something over a factor of three, as I recall. How much room for improvment in speed would you say is there in the source? Quite a bit, probably, but the primary loop is rather small and most of the math is done by libgmp (or freeLIP in the case of mersfaclip). I have limited computational resources, a PII233, a P100, but because of my work, I have practically unlimited resources in the 486 department they could finish a 2^40 section in about a day or so. As mentioned above, feel free to send me any data that you want; I've been saving this sort of data for a lot longer than GIMPS. E.g., I have some pre-GIMPS data for certain exponents up to about 240 million. The results file, containing all the data that I have, is now over 90 MB; the list of exponents alone is over 14 MB. If nothing else, sending me your data will let me compare it to what I already have for exponents and factoring ranges in commonn and check to see if any of the programs have bugs. This sort of comparison has found bugs in both the mers package programs and in George's programs several times and is a big reason for doing double checking with distinct programs on distinct hardware. Will http://www.garlic.com/~wedgingt/mersenne.html Brief web page w/ links mers.tgzMers package, tar'd, gzip'd Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Re: Mersenne Digest V1 #576
Daren Scot Wilson writes: I've switched from Linux to BeOS - entirely, not even dual-booting both. Same hardware as before - PII 400 MHz. BeOS is POSIX compatible, has TCP/IP, but the file system is offbeat, and from what I hear most linux software needs a little bit of tweaking to compile for Be. Is there any Mersenne testing software that can run on BeOS? Or other interesting math crunching software? See the mers package code that I maintain. It is ANSI C source code plus a shell script. There are also pointers to other programs, notably Ernst Mayer's Fortran90 LL tester, on my mersenne.html page. Will http://www.garlic.com/~wedgingt/mersenne.html mers.tgz mers.tar.gz Two different names for the mers source tar file since some web browsers don't realize that '.tgz' is binary and some operating systems don't like two dots in file names. If you need a zip or shar file or other format, just ask. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Serious problems with v.18
Here are my ideas on bugs: Bugs happen! They're a fact of life, omnipresent in all software. Showstopper bugs should not slip through testing and into release software. Correct: _should_ not. That does not mean _will_ not. Mistakes happen, at least as often as accidents. If testing could be perfected in this manner, then programs themselves could be perfected. Bugs should allways be caught in the testing, but so often they aren't. Minor bugs yes, massive showstoppers no. How can a bug be known to be a show stopper until it has been found? For that matter, I seem to recall that it cannot be proven that a program will _halt_, let alone do something useful, let alone do something useful without any bugs in any circumstances. In the meantime, a subgroup of testers have been created which should (hopefully) ensure that things like this cannot take place again. Yes... a good idea. With a shiny new lock on that barn door, perhaps these horses won't escape a second time and cost GIMPS hundreds of P90-years of time... I still think it would have been a good idea to have had this lock from the outset. But it's water under the bridge... Actually, a somewhat different "lock" has been on this barn door for years (since not long after GIMPS started at the latest), in the form of other programs, implemented independently and able to run on different hardware. I'm not sure about this bug in particular, but earlier bugs (in, at least, Prime95's factoring code and many of the mers package programs) were only discovered by comparing their results with results of those independent programs. The new subgroup of testers is still a good idea, of course, but they will only improve the quality of the releases, not make them bug-free. Anyone expecting otherwise has quite a bit to learn about programming. Will Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: New Prime...I wonder if the islands theorem will hold fast?
Luke Welsh writes: TTBOMK, the theory was never formalized. Regardless, Peter Lawrence Montgomery settled the issue: http://www2.netdoor.com/~acurry/mersenne/archive2/0032.html See also: http://www2.netdoor.com/~acurry/mersenne/archive2/0035.html http://www2.netdoor.com/~acurry/mersenne/archive2/0026.html http://www2.netdoor.com/~acurry/mersenne/archive2/0023.html That archive appears to be old and I do not see some replies that I later made to this thread. Notably, I added mersdistrib, a slightly modified version of the program that Peter included in the first message above, to the mers package at the URL below. Will http://www.garlic.com/~wedgingt/mers.tar.gz Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: factorization
Tony Forbes writes: I know it's a bit feeble the usual standards for ECM factorization, but Seems to me that "feeble" certainly doesn't include factors that are new! Besides, I'm doing some work on 11-digit factors.:) I just found this 36-digit factor of 2^2203+1 : 848425589476255002200418022118728331 Great! Thus 2^2203+1 = 3 * 13219 * 208613913329 * 743372438374143806443 * 282324958084937237369 * 848425589476255002200418022118728331 * C571 I apologise if this is not new or not interesting. New factors are always interesting, at least to me. And "new" is relative; I don't always have time to update my web pages each week. I am still trying to find numbers n 1000 where gcd(n, 30) = 1 and 2^n- 1 and 2^n+1 are completely factorized. Like 2203 would be once the C571 part has been factorized (2^2203-1 is prime). The only ones I know are 1121 and 1141. Anyone know of any more? There may be more in my data; check: http://www.garlic.com/~wedgingt/factoredM.txt Note that 2^n - 1 is listed there with n as the exponent; 2^n + 1 is listed there with 2*n as the exponent, since: 2^(2*n) - 1 = (2^n - 1)*(2^n + 1) by the difference of squares factoring method. E.g., take the case of 2^2203 + 1; it's listed under 'M( 4406 )' but does not include the first factor listed above (3) since that is also a factor of a smaller Mersenne number (M(2)). (If this wasn't done, 3 would be listed next to all even exponents, 7 next to all exponents that are multiples of 3, 5 next to all that are multiples of 4, etc; see ecm3.c of the mers package for how this is done). Will P.S. Here's the most recent run of a new program of mine: + 1strs8gmp -r617 32768 1300069 131 M( 20163 )C: 13001425009 M( 24603 )C: 13013067967 M( 28795 )C: 13014015431 M( 30644 )C: 13015272901 M( 19130 )C: 13016377211 M( 16105 )C: 13032166001 M( 10997 )C: 13032852617 M( 13762 )C: 13034540681 M( 20190 )C: 13044597481 M( 11660 )C: 13051970801 M( 17388 )C: 13053675853 M( 5358 )C: 13062782569 M( 7160 )C: 13070164721 M( 13414 )C: 13078100027 M( 13428 )C: 13098436597 M( 7292 )C: 13098758149 It printed all factors (from 13 to 13.1 billion) that are not already in my data of all Mersenne numbers between the two arguments to -r (617 and 2^15, here). It took about 6 hours this morning on my new P233MMX CPU (my P200's mainboard appears to have fried Sunday night in a power outage surge; sorry if email to me bounced in the mean time. I believe that no data was lost, though I still have some bad blocks to fix/redirect). Note that it would run at the same speed if the limit on the exponent were removed, but it would be full of data for composite exponents up to the size of the factor. Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: JavaLucas (again) Large FFT results and I need some help oh great prime gurus...
Blosser, Jeremy writes: So I ran JavaLucas with an FFT of 256k Its getting 1.75 sec/iteration. So... not too shabby really... Not bad at all. 1) What the algorithm for finding the best FFT size. I was doing: [...] So I looked at MacLucasUNIX, and it has: while (n ((BIG_DOUBLE)q)/ROUNDED_HALF_MANTISSA + 4.0) n = 1; size = n + ((n MASK) SHIFT); What I can't find is where the ROUNDED_HALF_MANTISSA came from, and why the mask and shift operation? ROUNDED_HALF_MANTISSA in MacLucasUNIX is mis-named, really; as I recall (and I didn't write the original use of it), it's just a constant based indirectly on the number of bits in the mantissa of the doubles being used. You'll find the declaration in setup.h, based on the define of BIG_DOUBLE. The mask and shift is a "trick" (that I believe George Woltman passed on to John Sweeney) to leave gaps in the arrays to improve cache performance. See the file "Wisdom" which John Sweeney wrote and I pass on as part of the mers distribution. I have no idea whether it will help or hurt Java performance, but there are some hooks in the mers package code to use it (MacLucasUNIX) or turn it off (mersenne1) in some of the functions that use the primary array. 2) I'm looking at the code, in Lucac.c and it looks like: a) create the scrambled array scrambled[j] = n[permute[j-1]] * two_to_phi[permute[j-1]] (not quite sure why) b) it converts the scrambled array to fft, squares it, does the inverse fft... c) multiplies the scrambled array * two_to_minusphi (Is this the mod here???) d) calls addsignal (this one has me lost) e) calls patch (carry?) I believe this is simpler in both mersenne1.c and MacLucasUNIX.c, though it's been a while since I've looked at any of them this closely and I myself don't fully understand FFTs. So, my question is, where is the subtraction? n = (n*n-2) % (2**p-1) I see the square, I see (I think) the mod... wheres the -2? MacLucasUNIX.c does it in normalize(). Mersenne1.c does it in main(). 3) I was thinking in the shower this morning... (Odd ain't it?) And for all n 2**p-1, the answer will always be n*n-2 right? Also, if n sqrt(MAXLONG), then we can do it in place without the FFT... Just looking at some data sets, the odd of n being less than sqrt(MAXLONG) is actually not to bad... (especially in Java which has 64-bit longs)... So where does this short cut fit in? (with a big FFT, this can be a big difference (I think))... I'm not sure, but I'd guess that you've goofed somewhere. For reasonably large p (in this case, anything over about 100), the chance of n being less than 33 bits should be miniscule, except, of course, during the first several iterations. But perhaps I'm misunderstanding what you're saying. And even when I tried the "obviously-it-will-work" change to start at 194 or 14 (rather than 4) in mersenne1 and MacLucasUNIX, there were problems on some computers and compilers. Will http://www.garlic.com/~wedgingt/mers.tar.gz mers.tgz mers.zip mersenne.html Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring bugs
[EMAIL PROTECTED] writes: As LL tests begin to go beyond the limits of older machines, now may be a good time to consider a distributed factoring effort. I've wanted to see one for a while now but frankly, implementing many of the algorithms is over my head. That, and the lack of a permanent home have made me shelf it. If, however, anyone wants to talk about donating code or a server, I don't see why we couldn't make one, and factor some of the unfinished mersennes. See ECMNet. I'm pretty sure there's a link off www.mersenne.org and off my mersenne.html. There's a new server/client setup that's apparently almost as automatic as Prime95/PrimeNet. (I haven't had time to try it yet). But note that ECMNet is trying to completely factor various numbers, including the Mersennes with exponents into the low thousands; it is not trying to find factors of the Mersenne numbers that GIMPS is interested in. If you want to do the latter, use Prime95. In my mind, the v17 bug illustrates how important factoring is. It provides an easily-verified proof of compositeness. Yes, and that's the whole reason there is a factorer part of GIMPS: because having it eliminates possibilities faster, and with no need for a doublecheck. Factors are very easy to confirm; my 200MHz Pentium can probably verify every known factor in a day or three (and I have had it do so a few times in the past). But Prime95's factoring code has also had bugs at times; a bug-free program is - as I'm sure most of us are aware - effectively impossible. Which is part of why there are other programs that do the same things, like the mers package that I maintain. Prior bugs in the mers package LL testers and factorers were exposed by comparisons with output from Prime95, just as prior bugs in Prime95 were exposed by comparisons with the mers package programs. Will http://www.garlic.com/~wedgingt/mersenne.html Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Re: Mersenne: Distribution of factors among congruence classes
Alex Kruppa wrote: Now I know how the 55 (mod 120) got there, it's: M( 310169 )C: 3486114749130405725455 and the problem is that that's not a factor. Not remotely. 3486114749130405725455 = 2*3*11*69720503*757595229073 +1 so doesn't seem to be a factor of another Mersenne we've tested, either. Must have snuck in there by mistake, or maybe a typo. You're using an old copy of my data; that particular false factor took me several updates to eradicate for some reason, but it's not in my data presently. Will Unsubscribe list info -- http://www.scruz.net/~luke/signup.htm
Mersenne: Factoring
Sander Hoogendoorn writes: Last weekend when i was testing Prime 95 i noticed that factoring low numbers took much longer as high numbers. Factoring M17XXX from 2^52 to 2^54 took minutes per pass while factoring M9XX from 2^52 to 2^54 took about one minute to complete the whole factoring. How is this possible? All factors of a Mersenne number with a prime exponent, p, are of the form 2*k*p + 1 where k is a natural number (positive integer). So the larger p is, the fewer the number of possible factors between two constants like 2^52 and 2^54. In this case, 17XXX divided by 9XX is at most 0.2%, so checking all the possible factors of M17XXX takes about 500 times as much CPU as checking all the possible factors of M9XX within the same range of numbers. This a large part of why higher exponent Mersennes are trial factored farther than lower exponent Mersennes. While I'm here, I'll mention for the newcomers that I collect all sorts of factoring data on Mersenne numbers, including George Woltman's ECM GIMPS data, the Cunningham Project ftp site data maintained by Paul Leyland, Conrad Curry's Factor98 data, and directly from interested individuals like yourself; just send it to me in email, plain text or as MIME attachment(s). The data I've collected for exponents under 200,000 is available below. I have data for many larger exponents, including all primes thru 21.5 million or so, but do not have room on my ISP's web server to upload it. Will http://www.garlic.com/~wedgingt/mersenne.html (proofs, links, etc.) mersfmt.txt (data format description) mersdata.zip (data, zip'd) mersdata.tgz (same data, different packing) factoredM.txt (completely factored Mersennes) ...
Mersenne: Raise the Lower Limits
Robert G. Wilson v, PhD ATP writes: The below chart gives the general lower bounds for which the limit of powers of two begins. As an example, 2^55 for the most part, is the least exponent as a limit for all Mersenne numbers greater than 1,040,000. There are exceptions and this is the object of this post. I would like to see that there are no exceptions except for the obviously untested Mersenne numbers. Once this is accomplished, then I would like to see the Mersenne numbers at which a particular exponent occurs also reduced. Exponent, Mersenne Nbrs. 52 1,400 53 400,000 54 730,000 55 1,040,000 56 1,335,240 57 1,602,275 58 2,222,000 59 2,655,000 60 3,602,100 61 4,715,000 62 5,260,000 I'm not sure that I see what you're talking about, but I'll guess, from the table you give, that you mean nearly all Mersenne numbers with exponents above 1400 have been factored thru 2^52, nearly all Mersenne numbers with exponents above 400,000 have been factored thru 2^53, and so on, and you would like someone to do trial factoring to change those "nearly all"s to "all"s, increase those powers of 2, and decrease the corresponding Mersenne exponents. I believe that the vast majority of trial factoring presently being done is the factoring step of GIMPS, prior to the LL test. For example, nearly everyone that was doing trial factoring of small exponents (already LL tested) is now doing ECM or P-1 factoring or has gone back to LL testing; the only two people I know of that are still running trial factoring of already LL tested exponents are Jean-Charles Meyrignac and myself, and I'm just filling gaps in prior trial factoring efforts, mostly between a known factor discovered by GIMPS and a larger factor or the next power of two. Since I can't use George's factorer for this "gap filling", I'm using mersfacgmp, which is considerably slower, and I've only got one CPU, which usually spends half its time doing cofactor pseudo-prime tests, looking for complete factorizations. So, unless other people assist, it's going to be a slow process, with the exception of the GIMPS factoring. On the other hand, that means that one person, even with only one computer, could make quite a relative contribution, if they want to. For that matter, there still aren't many people running ECM or P-1, which are typically faster than trial factoring for the small exponents (up to, say, the 17 limit of Factor98) anyway. And the advantage of ECM and P-1 is best for the smallest exponents, where their memory usage is less; the memory usage of trial factoring is effectively unaffected by the exponent's value. Other progress: all factors less than 2^32 for all exponents less than 25000 should be in lowM.txt (or factoredM.txt) now; some had been missed by GMP-ECM because the starting bound is too large to get all factors. All cofactors for exponents under about 14000 have been pseudo-prime tested. 1742 composite Mersenne numbers are now known to have either a prime or a pseudo-prime cofactor. Will
Re: Mersenne: RE: any large groups that run GIMPS software on corporate computers?
Simon Burge writes: You may want to try what I do with some of our machines - instead of killing and restarting the program, send it a STOP or a CONT signal (I assume Linux has these signals available, I'm a BSD and SysV person). Yes, Linux has them, being a mostly POSIX-compliant UNIX, which is closer to System V in some ways, closer to BSD in other ways, and a merge of them in yet other ways. The primary differences between this method and simply killing it and restarting it are: 1. This method doesn't generate a save file when the STOP is sent (this could be changed at a cost in reaction time to the STOP). 2. This method still occupies a process slot, swap space, etc., during pauses (usually only minor annoyances if your system has a reasonable amount of swap space). 3. This method pauses and resumes faster and with less I/O, making slightly better use of the idle time that's available (most of this advantage would be lost if STOP generated a save file). See 'kill -l' (lower case L; on many UNIX's) to see what signals are available. Will
Mersenne: ECM Factoring
Glenn Brown writes: The computer has found TWO factors of 2^647+1. It's still searching! WHY Good question. Most likely, because what's left is still composite. But since I don't know what program you're using nor what factors it has found, I can't help you more without more information. From the current lowM.txt file, which presently includes all the data that I have on incompletely factored Mersenne numbers with exponents up to 200,000: M( 1294 )C: 4570409 M( 1294 )C: 9021769 M( 1294 )C: 932184694939 ... since: (2^647 + 1)*(2^647 - 1) = (2^647)^2 - 1^2 = 2^1294 - 1 = M(1294) ... factors of 2^647 + 1 will be listed under M(1294) in lowM.txt. Factors of M(1294) that are also factors of M(647) are only listed under M(647). Data for completely factored Mersenne numbers is moved from lowM.txt to factoredM.txt. LowM.txt - factors, cofactors' primality, etc. - is verified by the ecm3 program of the mers package every time I update my data, usually for all exponents up to around 15,000 (depending on how long I let it run). New data is gathered from George Woltman's ftp site, Paul Leyland's Cunningham Project ftp site, and Conrad Curry's P-1 data ftp site automatically as part of my update scripts. Will http://www.garlic.com/~wedgingt/mersdata.tgz tar'd gzip'd lowM.txt, etc. mersdata.zip DOS zip'd lowM.txt, etc. mersfmt.txtdescription of format mersenne.html descriptions and links
Re: Mersenne: Goldbach's Conjecture
Nicolau C. Saldanha writes: Given N, let f1(N) be the number of primes of the form 4n+1 which are smaller than N, and f3(N) be the number of primes of the form 4n+3 which are smaller than N. Thus, f1(10) = 1 and f3(10) = 2. Is it true that f1(N) = f3(N) for all N? The answer is no, but I challenge you to find a counter-example. What I do not understand is why you consider it unwise to pose challenges to people who might actually be interested in them. "Challenge" in this context in English (at least as used in America) often implies that you believe that it cannot be done or that it would be very hard to do. It might be used to challenge someone to prove Goldbach's Conjecture or Fermat's Last Theorem, for example. Maybe you consider "challenge" a bad word? Not a bad word, but it does sound like a difference in usage. My point was that such a counter-example would large enough that: (a) a naive person, seeing the empirical evidence, would draw an incorrect conclusion. (b) some members of this list might find it interesting to consider the problem. "Interesting", "difficult", and "non-trivial" would have been closer to your intended meaning, then, I think. And if you simply wanted someone to find a counter-example, just asking for one is fine; the list has seen several conjectures proven and disproven (including at least one of mine, on my Mersenne web page) by example. Will http://www.garlic.com/~wedgingt/mersenne.html
Re: Mersenne: What up with PPC Macs?
Greg Hewgill writes: Would MacLucas be suitable for double checking? Not having a Mac, I have never run MacLucas, but there is lots of double checking work going on right now in the 1.3e6 - 1.6e6 range. I'm sure that there are quite a few people out there using MacLucasUNIX for double checking. Probably more, though, are using it for 'first checking'. Will http://www.garlic.com/~wedgingt/README.html
Mersenne: New mers release, v6.1
A week or so ago, I put a new release, v6.1, of the mers package on my web pages at: http://www.garlic.com/~wedgingt/mers.tgz The prior (non-beta) release was v4.42; v5.x only appeared as beta releases. There is already a newer beta release, as well. Two new programs have been added since v4.42. Mers3p does (slow, non-FFT) base-3 pseudo-prime tests of Mersenne numbers and ecmfactor uses freeLIP's ECM routines to factor arbitrary natural numbers. There are no great speed improvements, only a few fixes and somewhat improved and easier usage; I've included some details below. Will README.html has been somewhat improved and considerably updated, including references to the manual test forms of PrimeNet in preference to emailing George Woltman to get exponents to LL test. The fftll shell script will now ignore a leading 'Test=' so that the PrimeNet form result can be simply cut-and-pasted or saved as a file and the file name given to fftll as an argument. Ecm3 now knows how to handle even exponent Mersennes, including the 'L' and 'M' algebraic factors when the exponent is an odd multiple of four. See README.html and mersfmt.html for more details, including the algebra itself. Ecm3 also has several new flags. Extract and rw.c can now read and contract can produce DATABASE files with exponents larger than 2^24 (about 16.6 million). Extract can now print information from Factor98 save files. Mersdistrib should now compile and run on SGIs and SunOS 5.x. A small Makefile bug for DEC MIPS machines has been fixed. Small problems with libraries in Makefile.nofac have been fixed.
Mersenne: Pseudoprime tests?
Paul Derbyshire writes: I notice that GIMPS exponents are tested with a bit of trial factoring and then we go straight to LL testing, without any pseudoprime testing. I assume that pseudoprime tests are actually slower than the LL test itself? Or else they'd use them to eliminate some composite numbers before going on to the LL tests... The pseudo-prime test requires effectively the same amount of CPU time, since the only real difference is that the LL test does the subtraction of two each iteration. The real issue is that the pseudo-prime test is not certain, since some composites "look" prime to it. The LL test is certain, barring errors during execution. (I am aware that Mersenne numbers are always strong 2-pseudoprimes. I was thinking along the lines of other bases.) Base 3, e.g., which is where mers3p.c of the mers package came from, due to a prior discussion of this on this mailing list. Compare it to the recently posted LL test program implemented on top of GMP. Will http://www.garlic.com/~wedgingt/mersenne.html `
Mersenne: factoring code
I wrote: Henk Stokhorst writes: table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119 In case it still isn't clear to someone out there, this is the list of numbers less than 120 that are relatively prime (no common factors greater than 1) to 120. Oops! I should have thought about this some more before sending this out; it's not quite correct. All the numbers in this table are indeed relatively prime to 120, but there are 16 more such numbers, each differing from one of the above by 60. My only excuse is that I was thinking in terms of my old, pre-GIMPS, factoring code, which used 60 instead of 120 but still had 16 entries. Those 16 out of 60 are equal to (2 - 1)*(3 - 1)*(5 - 1) out of 2*3*5: cancel half, then one third, then one fifth. Will
Mersenne: factoring code
Henk Stokhorst writes: table:1,7,17,23,31,41,47,49,71,73,79,89,97,103,113,119 In case it still isn't clear to someone out there, this is the list of numbers less than 120 that are relatively prime (no common factors greater than 1) to 120. for number := first to last number in table do for factor := smallest to highest possible factor do result := Mersenne candidate divided by factor if result = number then factor found ; exit next factor next number Yes, this is the basic idea. While I would have expected the code for factor := smallest to highest possible factor do result := Mersenne candidate divided by factor for number := first to last number in table do if result = number then factor found ; exit next number next factor This is slightly incorrect; the "division" (the actual code does no long division) still has to take place inside the inner loop: for factor := smallest to highest possible factor do for number := first to last number in table do result := Mersenne candidate divided by (factor + number) if result = (factor + number) then (factor + number) is a factor ; exit next number next factor to be faster. Of course it isn't, but why? I believe that most of it is because there is less to do in the innermost loop. For example, the increase in the possible factor in the first case is a constant, the index into table doesn't change in the inner loop, and table isn't even read from in the inner loop. But it's also not quite that simple. If the Mersenne has one small factor and it happens to be 119 mod 120, the first method will search the entire range 15 times before finding it; the second method will find it quickly and exit. But the assembly code version is so fast - especially compared to the LL test times for the large exponents GIMPS is working on now - that it's probably not worth worrying about this last effect. Will
