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: 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: 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: 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
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
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
Re: Mersenne: V20 beta #3
Brian J. Beesley writes:
On 15 Apr 00, at 4:22, Henrik Olsen wrote:
> I just tried downloading 20.3, both mprime and sprime, as well as tried
> with mprime 19.0.2 . None of them where able to detect the network as
> being available on a machine running Mandrake Linux, kernel version
> 2.2.14-15mdksecure, probably due to /proc/net not being readable by
> non-root on such a system, which is a bit of a bummer, as I as I don't
> want to have to run it as root. :(
1) Install mprime with suid privelege. This should enable mprime to
read /proc/net as though it were running under root even though it's
actually running under an unpriveleged user.
As Henrik later points out, this is _not_ a good idea. I'm sure we
all trust George - or we wouldn't be running his binaries - but he is
not a Linux security expert, and even I wouldn't do this and I've not
only read the source code, I've worked with UNIX security since 1980
and I see nothing wrong with the code in the security sense.
Besides, there are other solutions. Which is, by the way, the first
"test" that setuid should not be used: it should only be used as a
last resort, after just about everything else has been tried.
2) Get out your hacker's hat and fix the problem in the source code.
The first time I read this, I thought you meant the Prime95 source
code. That's certainly where I'd look first.
I'd guess that all you need to change is the code which creates the
/proc pseudofilesystem at boot time. As you've probably found, you
don't seem to be able to change the permissions on "files" in the
/proc tree on a running system - even if you _are_ root.
I would guess that there are good reasons that the authors wrote it
this way. In any case, it's much easier to fix this in Prime95.
3) Is Mandrake really linux, or just a linux clone? I think the
latter. If I'm right, then perhaps switching to a genuine linux (Red
Hat, or SuSe) might be a sensible thing to do. Though the official
Red Hat distribution retail package is expensive, you can get just
the CD for about $2, or download the distribution FoC (not
reccomended unless you have fast internet access!)
This also would be a lot of work and may not even be an option for
many people. So:
4. Look at the Prime95 source code (well, for version 19.1 anyway,
which is the one I've got unpacked on my system presently) near line
761 of linux/primenet.c, where there's an fopen("/proc/net/route",
"r") inside an #ifdef __linux__. Look lower down, after the #endif,
and note that __FreeBSD__ doesn't have a similar check; it simply
always returns TRUE. Looks to me like it would be very simple to add
a check for the fopen() failing due to permissions or whatever under
Linux and return TRUE (i.e., that the system is connected to the
network), perhaps based on a new flag in one of the .ini files.
In fact, always returning TRUE from that function is not that big a
deal; if TRUE is returned when FALSE is correct, all that will happen
is that the later call to connect() - to actually try to connect to
Primenet - will fail and Prime95 will complain to the log file and
screen. I see such complaints all the time on my Win98 machines and
my new Debian Linux machine (which is running the unmodified RedHat
Linux mprime binary just fine, as far as I can tell).
Will
_
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
Re: Mersenne: Factoring Mersenne
Daniel Grace writes: > Anyway, any mersenne's factor can be written as 2kp+1 > directly). Call (P-1)/p = Q > > Then 2n = Q mod p > n = Q/2 mod p which is well defined > Therefore we can find the sun of the two factors mod p. I think what you are trying to say is M_p is composite for p a prime iff 1+2kp divides (2^(p-1)-1)/p - k for some k>0. If I am not mistaken factoring this using current methods is harder than factoring 2^p - 1. Yup, almost certainly, if only because k is needed twice. The current trial factoring method does not even use k per se. Remeber it is easy to trial divide 2^p - 1 using bit wise operators, because 2^p - 1=1+2+2^2+...+2^(p-1). Let u be a potential divisor (e.g. u=2kp+1) then let j be smallest int. such that 2^j-1>u then you can try dividing 2^p-1 using just j bits of storage. e.g. start with 1+2+2^2+...+2^(j-1), subtract u, shift to the left appending 1's at the start, until you get v>u, subtract u and so on. I think that the software stops if it gets a residue of 0 before all p bits have been eliminated - in this case u divides some smaller Mersenne. Not quite. My "reverse method" works that way, and will find the smallest Mersenne exponent which is a multiple of a given odd number, but the fastest-so-far trial factoring method actually squares and perhaps multiplies by two modulo the trial factor each loop, starting with two and looping over the _bits_ of the Mersenne exponent, making it quite fast. If the particular bit is one, the multiply by two occurs; if it's zero, it doesn't. That is, it calculates the Mersenne number (two to the exponent power) mod the trial factor. This algorithm is in Knuth, apparently, which I don't have a copy of. Before GIMPS, I was doing something slower; George Woltman told me about this method, speeding up my then-current trial factoring program by a factor of about three (in Jan. 1996 or so). Will _ 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
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( )G: where '' is the exponent and '' and '' 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
Re: Mersenne: New beta mers release: new Lucas-Lehmer program
Simon Burge writes: Unless you're doing a timed run, maybe "kill -STOP pid" and "kill -START pid" on the ecm3 run might give more accurate results - I hate to think of what's happening to the cache... I use this on machines that have mersenne1 running when users notice X load showing a constant load average of 1.0. I tried this just before uploading the new beta with tunefftw.c in it and MacLucasFFTW's speed improved by less than 3% over the run with the tuning done while ecm3 was running. So either the cache is not the bottleneck or that Linux's context switching with 128 MB RAM is quite good, as a guess. My early tests on a 200MHz UltraSparc are not that encouraging. [...times deleted...] Sigh.:( Though it does look like MacLucasFFTW is faster when the FFT length is enough lower ... by, hm, about 10% ? But MacLucasFFTW2 using two CPUs isn't as fast as two MacLucasUNIX's running at the same time, is it? I would guess not, from those numbers. The -C means don't checkpoint ever and -S N means print a speed update every N iterations. MacLucasFFTW2 is hard coded to use 2 threads. The case for 4609273 is iteresting, with nearly identical FFT lengths... Yeah.:( I'm assuming that you're seeing such a speed-up on Intel because of the lack of registers that MacLucasUNIX likes, and FFTW is doing a better job under these conditions. Looks that way, or something similar. Will - I'll send you a diff that I used for the timing stuff. Yes, please do when you have time; it'll save me from having to reimplement it. Will _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Re: Mersenne: New beta mers release: new Lucas-Lehmer program
Simon Burge writes: Only runtime wisdom - Will didn't put tunefftw.c in the distribution. If you or Will can send me a copy I'll try the tests again. OK, I've ftp'd a new beta release that includes tunefftw.c and runs it before doing the test of MacLucasFFTW. I've kept a not-very-close eye on fftw, and wrote a simple fftw-based LL tester about two years ago, but used fftw and not rfftw. For reference, it's at ftp://melanoma.cs.rmit.edu.au/pub/simonb/fftwll.tar.gz. OK, I'll take a look when I find time. Will http://www.garlic.com/~wedgingt/beta.tgz beta.tar.gz beta.zip beta.shar _ Unsubscribe & list info -- http://www.scruz.net/~luke/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
Mersenne: New beta mers release: new Lucas-Lehmer program
I have ftp'd a new beta release of the mers package to:
http://www.garlic.com/~wedgingt/beta.tgz
beta.tar.gz
beta.zip
beta.shar
I'm announcing it to the mailing list because it includes a brand new
Lucas-Lehmer test program called MacLucasFFTW. It was modified by
Guillermo Ballester Valor from MacLucasUNIX to use the FSF's FFTW
("Fastest Fourier Transform in the West") library, which is available
at www.fftw.org. I have made some small changes to get it to pass the
mers package's simple Makefile tests on my machine and noone else has
tried it yet, so it's perhaps more of a late alpha version than a
beta, but ...
... I had this odd feeling that people would want it quickly, because
Guillermo reported that it's faster than MacLucasUNIX by a factor of
nearly three (!) (for the same FFT lengths) on his PentiumPro and it's
about a factor of two faster on my Pentium III 450 MHz. Some of my
changes - short as they were - likely slowed it down, unfortunately.
More good news: FFTW supports non-power-of-two FFT lengths. And
"tunes" itself to the hardware and software around it at run time, and
MacLucasFFTW saves this tuning information externally in a file for
next time, so more tuning only needs to be done for new, mostly
larger, FFT lengths.
Guillermo was able to use most of the mers package functions, so the
usage and input/output formats and so on are the same as the other
mers package LL test programs.
I've included Guillermo's README file, renamed to README.MacLucasFFTW,
essentially verbatim.
Guillermo also sent me a short program that does the tuning outside of
MacLucasFFTW; I will include that in a later release if there are
requests for it, but MacLucasFFTW can do the tuning itself just as
well, and even prints when it's tuning and for what FFT length.
FFTW itself installs with the usual configure and make, and also
includes a test suite, invoked via make as well.
However, there are some (small) drawbacks: MacLucasFFTW may not be
able to read checkpoint files produced by the other programs; I know
it cannot do so on Intel hardware, because the others, there, use
'long double', a 64 bit mantissa type, and FFTW does not appear to
work with that. Guillermo and I have no non-Intel hardware to test
with, so someone out there will have to try that. Of course, for many
exponents, MacLucasFFTW will use a smaller FFT length, so ...
The other Lucas-Lehmer test programs in the mers package will not be
able to read MacLucasFFTW checkpoint files correctly, at least for the
non-power-of-two FFT lengths. They should, however, simply reject the
MacLucasFFTW checkpoint files that they can't use as invalid rather
than corrupting them or trying to "resume" from bogus data.
Lastly, I'm not sure where FFTW has been ported; machines not running
some flavor of UNIX may or may not be able to compile it: I simply
haven't had time to check.
The timings on my PIII/450MHz of the Makefile tests are:
time -v ./fftlucas -o- testLL.in | sed -e 's/, n = .*//' > test.fft
User time (seconds): 784.40
System time (seconds): 0.15
Percent of CPU this job got: 49%
Elapsed (wall clock) time (h:mm:ss or m:ss): 26:25.99
time -v ./mersenne1 -o stdout testLL.in | sed -e 's/, n = .*//' > test.mers1
User time (seconds): 711.40
System time (seconds): 0.05
Percent of CPU this job got: 49%
Elapsed (wall clock) time (h:mm:ss or m:ss): 23:47.97
time -v ./mersenne2 testLL.in | sed -e 's/, n = .*//' > test.mers2
User time (seconds): 745.58
System time (seconds): 0.03
Percent of CPU this job got: 49%
Elapsed (wall clock) time (h:mm:ss or m:ss): 25:00.22
time -v ./MacLucasUNIX `cat testLL.in` | sed -e 's/, n = .*//' > test.mlu
User time (seconds): 305.73
System time (seconds): 0.02
Percent of CPU this job got: 49%
Elapsed (wall clock) time (h:mm:ss or m:ss): 10:14.87
time -v ./MacLucasFFTW -ostdout `cat testLL.in` | sed -e 's/, n = .*//' -e '/^[^M]/d'
-e '/^$/d' > test.mlf
User time (seconds): 133.56
System time (seconds): 0.06
Percent of CPU this job got: 49%
Elapsed (wall clock) time (h:mm:ss or m:ss): 4:29.95
MacLucasFFTW had already done the tuning for the FFT lengths used
prior to this run, but I believe it would still be faster than
MacLucasUNIX even if it had not already done the tuning.
(The 49% CPU usage is because my computer was also doing a long term
ecm3 run, including during the FFTW tuning.)
Feel free to send me any questions, bug reports, and so on. As he
notes in comments and his README file, I believe Guillermo welcomes
feedback as well.
Will
http://www.garlic.com/~wedgingt/mersenne.html
beta.tar.gz
beta.tgz
beta.zip
Re: Mersenne: Factors Everywhere
Will Edgington writes: [Yes, I'm following up to my own message.:)] n p,pk1 ,pk2 ,pk3 Note that M(n) has no known factors. Trying this out just now, the 111 MB of data that I have for prime exponent Mersennes in the mersfmt reduces to a bit under 20 MB if this format is used for only the prime exponents with known factors. Gzip (using max compression) gets that down to 7.1 MB. Producing & gzip'ing it from the mersfmt of the data takes only a couple of minutes on my machine, so adding it to the automatic update won't slow things down enough to notice. A quick line count of ungzip'd file (about 2 seconds, from cache:) produces a count of 1,677,377 known factors of prime exponent Mersenne numbers (that aren't completely factored). Will _ 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 exponent
Mersenne: Mersdata update & web server "fix"
I have, just today (Sat., 25 Sept.), updated the mersdata file on my web site; the lowM.txt file now contains all of the data that I have for all Mersenne numbers with exponents thru 1 million, pushing the size of the mersdata file (gzip'd or zip'd) to about 6.5 MB. That pushes my usage to a bit over 15 MB of the 35 that I'm now allowed, so lowM.txt may get larger still. Or, if there's interest, I'll try to figure out a way to "rotate thru" all of my data somehow. As for the web server "fix", every now and then over the last year or so, someone complained that they couldn't download one or more of the .gz, .tgz, or .zip files from my ISP's web server; since I never had a problem and they were always, eventually, able to fix the problem by some tweaks in their web browser, I always just pointed them to their browser as being at fault. This past week, Henrik Olsen insisted that the problem is in my ISP's web server, and gave me enough info that, after trying something out, I now agree with him. While my ISP does not have the problem fixed yet, I have now notified them and added a file to my web disk space that should cure the problem for anyone downloading from there. So, be sure to let me know if you have any trouble downloading anything from my web pages. Will http://www.garlic.com/~wedgingt/mersenne.html 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: Front-end design
Pierre Abbat writes: I suggest a couple of named pipes for control (the front end writes to one and reads from the other, and mprime vice versa). Since writing to a pipe whose reader is stuck can get you blocked when the pipe is full, and writing to a pipe with nothing at the other end results in a SIGPIPE, mprime should not output anything to the pipe unless told to do so, and should trap SIGPIPE and turn off output. Um, there are easier ways. For one, file descriptors can be set non-blocking on all (modern) UNIX variants, which prevents getting stuck waiting for the other program and from getting a SIGPIPE. Also, most modern UNIXs implement pipes on top of UNIX domain (local to one machine) sockets; TCP/IP uses the same function call interface, sockets, but different addressing (for likely obvious reasons). See rw.c of the mers package and the Prime95 primenet.[ch] source code for how TCP/IP sockets can be used. Feel free to ask me, privately, detailed questions; I've been using TCP/IP via C, mostly for Mersenne stuff oddly enough:), off and on since about 1986. 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: 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 p>1:
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 p>100M, 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
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 http://www.garlic.com/~wedgingt/mersfmt.txt"> mersfmt.txt . 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=
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
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: Simple question about P-1 factoring method
If I understand P-1 factoring correctly, then using it to a stage one bound of k to try to factor M(p) will find all possible factors less than or equal to 2*k*p + 1. I'm assuming that p is less than k (or p is always used in the powering) and the convention several of us agreed on a while back that all prime powers less than the stage one bound are used in the powering, not just the primes themselves. That is, trying to factor M(97), say, to a stage one bound of 10 would use 8, 9, 5, 7, and 97, not just 2, 3, 5, and 7. Am I correct? Or could a factor smaller than 2*k*p + 1 be missed in some cases? Does it matter whether p is prime or not? I don't think so, but ... This is not idle curiousity; I want to use this knowledge to shrink some known trial factoring gaps in the data that I maintain, and this would reduce them substantially. Actually, the gaps are only in data for prime exponents, so that the one question above _is_ idle curiousity.:) Thanks, 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: 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: Though I don't have specific timings, I imagine this would be the case. I was referring to the Mfactor program by Peter Montgomery. Oh. And I see he's already replied; from that info, I would guess that Mfactor is only slightly faster than mersfacgmp on SPARCs (and mersfacgmp can, using libgmp, factor arbitrarily far). But actual numbers would be helpful. Volunteers? Feel free to send numbers only to me, if you like. I already have some numbers for MacLucasUNIX on Macs in private email that I need to put on my web pages somewhere. Or does someone already maintain a page with timings for non-Intel CPUs? I don't recall seeing one. I have heard this performs considerably better than a GMP based program (written by Alex Kruppa) on RISC architectures. I suppose that I could/should check up on this with my SPARC-owning friend. That would be helpful, yes. Again, I have no timings for this, but I would think that if you tried MacLucasUNIX on both a SPARC, and a PC, the SPARC would be the overall winner because of the massive amount of I/O that runs on LL tests. The only large amounts of I/O are the checkpoint files. Unless you're doing them too often, they will be a small fraction of the run time. Further, MacLucasUNIX, mersenne1, mersenne2, and fftlucas know about the Intel CPU's larger floating point variables, which gives the PCs an edge. See setup.h in the mers package for details. In factoring, I would imagine that the difference would be smaller, (using the same program). This, I don't even have a real guess about; the last time I did factoring on SPARCs, they were SPARC 2's (75 MHz?), which are much slower than Ultra's. Will http://www.garlic.com/~wedgingt/mersenne.html mers.tar.gz mers.tgz _ 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
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
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
Mersenne: Mersenne numbers
Kris Garrett writes: Has it been proven that all mersenne numbers greater than one are square free? Depends on your definition of 'Mersenne numbers'. If you include composite exponents, M(6) = 2^6 - 1 = 63 = 3*3*7 is not square free. If you include only prime exponents, then you don't need to specify "greater than one".:) But, so far as I'm aware, there is no proof that all prime exponent Mersenne numbers are square free. There is a partial proof towards the end of my mersenne.html page. Will http://www.garlic.com/~wedgingt/mersenne.html 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: 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: 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 suc
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: 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: 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
Re: Mersenne: VME claim
Henk Stokhorst writes: M(727) is not prime. VME made the claim that they could compute the first prime following M(727) in two seconds. Just want to know someone who can do the same trick and what software it takes. It took less than 2 seconds to find the next sequential prime : 7060034896770543742372772105511569658378384779628943811708504827156734575902 9962497646848024880749924272446637457099914453082421646959773690663827212173 6526607699022870679030143158018123175881930939339869708632591433883 Well, that's only 156 more than M727, so finding it is easy; the obvious sieve will do it. Verifying it's at least pseudo-prime took the mers package's ecmfactor program only 1.27 seconds CPU on my Linux Pentium 200MHz just now, and proving it prime using Morain's ECPP program took all of 50.9 seconds. So, even if they are proving it prime, it's not a big advance. More to the point, a better test, since they're unwilling to reveal their method, would be to give them some large, strong pseudo-primes mixed in with known primes of similar size. Anybody care enough to produce such a set? The composite factors of prime exponent Mersennes are all base-2 pseudo-primes, but that's not enough; they should probably be Cunningham numbers (which are pseudo-prime to all bases that aren't related to their factors). The only stronger tests that I can think of are making the program available via a TCP/IP server of some sort, so people like us can give it arbitrary numbers to check in real time, and a rigorous proof of the method, which requires making it public. 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: Fast check for common factor?
Don Leclair writes: There is the risk that more than one factor (or all factors!) might be extracted in between GCD's. This is easy to work around: After each unsuccessful GCD, save the current iteration number. If the next GCD(N,accumulator) is equal to 'N', back track to the iteration you saved and start again, executing the GCD more frequently. I believe that Factor98, at least, does things as Don describes, except that it does not "back up". Certainly, it does sometimes print "this factor is composite" (or similar) and I end up factoring those composite factors, when they're sent to me, using the ecmfactor program of the mers package. In fact, the ecmfactor program was written by me based on ecm3 precisely because I needed to factor some composite factors found by Factor98. As always, feel free to send me new code, bug reports, fixes, etc., for the package. I haven't seen many lately, but I also doubt it's perfect.:) As for new features, PrimeNet for the LL testers is in the early, pre-compilation, stage of implementation, so you don't need to mention that one to me, but go ahead and send me other ideas. Will http://www.garlic.com/~wedgingt/mers.tar.gz mers.tgz(same contents) beta.tgz(beta version) README.html (nearest thing to a FAQ)
Mersenne: Completely factorized (2^n-1)(2^n+1)
Tony Forbes writes: I am looking for odd numbers n (not necessarily prime), n not divisible by 3, n > 1000 such that both 2^n-1 and 2^n+1 have been completely factorized into primes. Look at the factoredM.txt file on my web pages. 2^n + 1 is listed under 2^(2*n) - 1, from the difference of squares factorization. So, if there are entries in factoredM.txt for n and 2*n with n odd above 1000, then n meets your criteria. The Cunningham tables give 1121 and I have been unable to find any more. However, there has been a lot of recent factorizing activity and my sources may well be out of date. I'll say; factoredM.txt has grown _very_ fast lately, I think, though I haven't actually counted for a while. I am also interested to know who found the factors 58142098448088409 and 359071640268582342735956401 of 2^1121+1. It appears that I got them straight from Paul Leyland's Cunningham Project ftp site; certainly, I don't see, after a few searches in the appropriate files, email direct to me announcing their discovery. Will http://www.garlic.com/~wedgingt/factoredM.txt
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: [meta] List bug, please fix; Yuri Sorkin, your email is phony
Paul Derbyshire writes: [deleted] Since you deleted all the text that you're replying to and your mailer did not add to the 'References:' header, I cannot even be sure what you are replying to, but I'll assume you're replying to me since I'm the only one, as far as I noticed, that said anything about UNIX; however, since even that reference was just a mention of Linux in a footnote, it's quite possible I'm mistaken. On the other hand, I see that my current mailer, GNU Emacs' vm package, added my note's msg-ID to the references above despite your mailer not doing so. It is somewhat rude or inconsiderate to be unix-centric. Yes, I suppose it is. Did you think I was being UNIX-centric? That was certainly not my intention, though I must admit a bias in that direction since I do not often use other systems. However, I have not only used other systems at times, I have been systems, network, and email admin for many such machines, on and off the Internet since before it was the Internet, over the past 14 or so years. Being the kind of group this is, I suspect there are others out there with even more experience, especially with MSWindows and Macs, but I _have_ used mailers on all three. Your assuming otherwise could itself be construed as rude or inconsiderate, it seems to me. I use a PC running Windoze... the mail client, the best free one I could find, is Eudora Light. Many people do use MSWindows and Eudora. Personally, I found Eudora so cumbersome and troublesome that I gave up on it quickly, but perhaps it has improved since and there are certainly a lot of people out there that prefer it over all mailers. That doesn't mean it has no bugs, nor that it follows Internet standards. Unfortunately, I do not have recent information on MSWindows mailers, so someone else will have to help you with that if you want to try something else. I presume there are still several newsgroups on the subject, if nothing else. It has an option to reply to the Reply-To or to the Reply-To and any addresses Cc:ed but that's it as far as I know... Now, if one of us had the source to Eudora Light, this could be fixed - um, OK, perhaps "changed" is a better word - in a jiffy; does anyone have it? Somehow, I doubt it, though I've been wrong before, so it's possible I'm wrong now; thus, I really am asking. In the mean time, I'm nearly certain that there are other free emailers out there for MSWindows that do this and other things (like 'References:') better. But, as others have noted, this discussion does not really belong on this list; anyone who's interested is free to contact me directly and, if there's interest, I'll coordinate a short-term mailing "list" to get better info on mailers and report back to those that care. Will http://www.garlic.com/~wedgingt/mersenne.html
Mersenne: [meta] List bug, please fix; Yuri Sorkin, your email is phony
Paul Derbyshire writes: To list admins: Please fix the damn listserv software so it sets Reply-To: to "[EMAIL PROTECTED]" will you? Right now it is unintelligently just forwarding the messages, leaving the Reply-To pointing at the author, and it is tedious to have to keep changing the address whenever replying to the list. Also error-prone. Sorry, I disagree. Of course, my email programs* allow me to reply to either just the author (Reply-To or From) or the author and everyone on the To: and Cc: lists. In fact, my opinion is that any email program that doesn't allow both is broken and should be fixed. To Yuri Sorkin: your e-mail address bounces... that's not exactly a friendly gesture, signing on this list with a bogus address. Yuri has been on this list and part of GIMPS, including providing and testing programs, from very early on; I think it's far more likely that his mail server is experiencing problems. In any case, the listserv software automatically drops addresses that bounce too many times or something similar. I myself have been caught by that last two or three times when my mail server was having problems. Will * Linux comes with several; I believe that they can all do this.
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: Faster GMP exp mod 2**p-1
Alexander Kruppa writes: I saw code posted earlier today that did LL testing with the GMP library. It used the mpz_powm_ui function for exponentiating modulo x. For x=2**p-1 this function can be sped up considerably, since a mod (2^p-1) = a % 2^p + a / 2^p (integer operations) and these can be done by bit shifting/masking. Yup; good eye. I figured this out years ago, but I think the only place it's presently used in the mers package is in mers3p. The LL test programs do the modulo as part of the FFT, though, so it would actually slow them down. I use this function below for my P-1 factorer (not released (yet?)). It gave me a factor 3 speedup. It´s a pretty straigtforward exponentiation algo exp(b,e) = if (e & 1) b*exp(b**2,e >>1) else exp(b**2,e >>1) with the modulo by bit shifting. This is what the trial factorers, George's and the mers package's, do, except that the modulo is by the trial factor, and thus can't be sped up this way but allows the use of single word arithmetic, and the exponentiation is of two. George told me about it and we put it in my pre-GIMPS trial factorer, which also gave it a speed up of a factor of three or so. To Will Edington: I think I saw in the P-1 factorer of the mers package that it used mpz_powm_ui, too, perhaps you may want to replace it. Yup, when I get around to it. But that program is so slow, noone is using it so far as I'm aware. It also does not support save files. What would be really nice is if someone that understands the FFT code of MacLucasUNIX, mersenne1, or even fftlucas would use that knowledge to write a P-1 and/or ECM factorer. I'd do it myself, except that I don't understand FFTs themselves enough, let alone the mers package programs that implement them. Will
Mersenne: What up with PPC Macs?
Richard McDonald writes: A bunch of Macs in my life would love to add to the effort, along with my PCs. I've found the MacLucas program, which was never very useable, is now unuseable; presumably the exponents are too large. The MacLucasUNIX program of the mers package is a direct descendant of John Sweeney's MacLucas program and I have just been informed by a Mac user that the current version, v6.1, compiles and passes the Makefile tests, so give it a try it you like. It will run best on PowerPC CPUs (Mac or not), since that's what John Sweeney tuned the code for, but don't expect it to be as fast as George Woltman's programs. http://www.garlic.com/~wedgingt/mers.tgz Someone else tells me that Navigator and IE both download that in text rather than binary mode, so I've also named it 'mers.tar.gz', which should be correctly recognized as binary. WinZip will likely not recognize the latter, however; rename it to the former first. I can't find anything online about efforts to produce a proper client (network enabled & stable) for Mac, which surprises me. MacLucasUNIX is not network-capable, but there are people (including me, slowly) that are working on adding PrimeNet support, but without support for the Prime95 style checksum to verify results. Will http://www.garlic.com/~wedgingt/README.html http://www.garlic.com/~wedgingt/mersenne.html
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: 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.
Re: Mersenne: When triple checking fails
Marc-Etienne Vargenau writes: Yes, I have the same problem. With Netscape on Macinstosh or Unix (Solaris). I sent a few days ago a private e-mail to George about this and he answered that I was the only one to have this problem. He told me that ftp://gimps:[EMAIL PROTECTED]/home/gimps/programs.txt works and that ftp://gimps:[EMAIL PROTECTED]/programs.txt dit not work with Internet Explorer on his computer. I would probably consider this a bug in Internet Explorer. >From your description, it is a bug either in IE or in either the HTTP or FTP server on 209.45.246.79; the FTP protocol is quite clear as to the directory at login. But FTP itself (my Linux ftp client, e.g., rather than a web browser) is working correctly, so the FTP server appears to be working fine. My Linux box's lynx (a text-only web browser) gets seriously confused by either URL; the server is sending something that causes lynx to switch my xterm to an alternate, unreadable, character set (which implies a bug in lynx, too; it shouldn't do that sort of thing no matter what it gets over the connection). Oddly enough, my Linux Netscape Navigator also works only with the longer URL, so something screwy is going on. But note that the URL: ftp://gimps:[EMAIL PROTECTED]/~gimps/programs.txt ... should work with correct and broken (in this fashion) browsers, even if it does appear to be from the Department of Redundancy Department.:) 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
Re: Mersenne: factoring code
Henk Stokhorst writes: I simplified the code a little bit, it says divide, whereas in the real code fourier transformations seem to be used. But I assumed more people would be familiar with dividing than fourier transformatios. The factoring code does not use fourier transformations; only the squaring code of the Lucas-Lehmer test needs that. But rather than having to even calculate, let alone divide anything into, the Mersenne number itself, the factoring code (in both Prime95 and the mers package trial factorers) calculates (2^exponent) modulo the trial factor a bit (literally) of the exponent at a time, something like this: acc = 2; topbit = 2; while (topbit <= exponent) topbit = 2*topbit; for (bit = topbit/2; bit > 0; bit = bit/2) acc = (acc*acc) % trial_factor; if (exponent & bit) /* is this bit set/on in the exponent? */ acc = 2*acc; if (acc == (trial_factor + 1)) found_a_factor(trial_factor); ... where '%' is the C modulo (remainder) operator and '&' is the C bit-wise and operator. The comparison to trial_factor + 1 rather than to just 1 is because the last '2*acc' is not '(2*acc) % trial_factor'. Will
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: Two questions on Prime95.exe
Bill Cherepy writes: I recently join the project and I'm testing my first exponent. I have two questions on Prime95.exe, the Windows 95 version. Welcome!:) When the program reached about 47% complete on the LL iterations, Status listed a second exponent for me with a Dec date. It this normal? Yes, if your computer is estimating that it will complete the first and then the second (and any later) exponents' LL tests within the number of days of work you've told Prime95 to ask PrimeNet for. Does the program run the LL test to 100% completion? Yes, given enough CPU time. When it does complete, it will print a line (in the window and to results.txt) saying that the Mersenne number is either composite (99+%) or prime (about 38 in 3 million :). Note that, if your second (or any later) exponent needs factoring, Prime95 may do that factoring before completing an LL test already in progress. If there is a small enough factor, it will take much less time to find it than doing an LL test and it will eliminate the need for the LL test, meaning your computer will suddenly have much less future work. Will
Mersenne: Mersenne exponential range
[EMAIL PROTECTED] writes: I was looking at the available ranges to test Mersenne primes and I noticed the range included exponents which by definition cannot yield primes. The ranges listed at www.mersenne.org and PrimeNet are mostly meant to include only prime exponents. The only exception I can think of at the moment is the ECM (Elliptic Curve Method) factoring pages at www.mersenne.org. I looked at some Mersenne htmls and didn't see any mention of even number exponents excluded from the search. They (all composite exponents, actually) are excluded from the search for Mersenne primes. No composite exponent Mersenne can be prime; see my: http://www.garlic.com/~wedgingt/mersenne.html for a proof. if the exponent, n, is an even number integer then 2^n is a square and 2^n-1 is factorable by: ((2^n)1/2 -1) ((2^n)1/2 +1) = 2^n-1 Correct. See my recent message to this list titled 'Composite exponent Mersenne numbers' for another factorization when n is an odd multiple of four. I've added the appropriate references to the email headers to make this easier once this message is archived. My computer is a pentium 133, 64mb ram , 2gig hd, MS95, math coprocessor. Could I contribute to the prime search? Yes, both for a new Mersenne prime - which is what GIMPS is looking for - and for new prime factors of smaller Mersenne numbers. There are several programs for each that will run on your hardware and operating system. For Mersenne prime hunting in particular, you want George Woltman's prime95, at www.mersenne.org; it's easily the fastest on Intel CPUs. Will
Mersenne: Composite exponent Mersenne numbers
Foghorn Leghorn writes: Second, I see that there are now some composite exponents in the ECM factoring page. Why are none of them even? Is there a technical reason that makes them less interesting? As Sam Laur and George Woltman have mentioned, even exponent Mersennes are always composite. George also pointed out the explicit factorization based on the usual difference of squares rule: x^2 - y^2 = (x - y)*(x + y) which, for our current purposes, gives: M(2*n) = 2^(2*n) - 1 = (2^n)^2 - 1^2 = (2^n - 1)*(2^n + 1) = M(n)*(M(n) + 2) So, if you want to know the factors of M(2*n), then factor M(n) and M(n) + 2 == 2^n + 1. Thus, (part of) the Cunningham Project tries to factor '2-' and '2+' numbers, 2^n - 1 for odd n and 2^n + 1 for all n. To fully understand the Cunningham Project 2+ file, there's another "algebraic factorization" that works for 2+ numbers for certain n's: 2^(4*a - 2) + 1 = (2^(2*a - 1) - 2^a + 1) *(2^(2*a - 1) + 2^a + 1) The first column of the 2+ file for the lines that can be factored in this was is n = 4*a - 2. For example, here are a couple of early lines in 2+: 14L 113 14M 29 2^14 + 1 = 16385 = 5*29*113 where 14 = n = 4*a - 2, giving a = 4. So: 2^14 + 1 = 2^(4*4 - 2) + 1 = (2^(2*4 - 1) - 2^4 + 1) *(2^(2*4 - 1) + 2^4 + 1) = (2^7 - 16 + 1)*(2^7 + 16 + 1) = (128 - 15)*(128 + 17) = 113*145 = 113*5*29 5 will always appear in this complete factorization if n is even, since M(4) = 15 and 5 divides no smaller Mersenne number (3 also always appears, but in the Mersenne (2-) half when n is even, in this case 2^14 - 1 = 16383 = 3*43*127 = 129*127 where 127 is, of course, 2^7 - 1 == M(7)). Paul Leyland maintains the Cunningham Project data, presently at both of ftp://ftp.cam.uk.eu.microsoft.com/pub/math/cunningham/ and ftp://sable.ox.ac.uk/pub/math/cunningham/. George Woltman continued: However, prime95 can be used on even exponents. If both 2^n-1 and 2^n+1 have not been fully factored then you can modify your lowm.txt file and try factoring 2^2n-1. If one of the two smaller values has been factored, then you are better off factoring either 2^n-1 or waiting for an upgrade that can factor numbers of the form 2^n+1. The beta mers package version of ecm3 can also now handle even exponent Mersenne numbers, including, imperfectly, the L and M "halves" described above when the exponent is 8*a - 4 == 2*n. The program knows enough to split the halves into distinct numbers to factor, but does not yet distinguish, in the output, to which half a new factor belongs. Old "factors", from the input, are checked against both halves before being rejected as incorrect (if it divides neither half). Ecm3 also handles composite (including even) exponent Mersennes slightly better than Prime95 by pulling out factors that are due to smaller Mersennes (with exponents that factor the larger, composite exponent) before trying to factor what's left. For even exponent (2*x) Mersennes, this means that ecm3 only works on the 2^x + 1 part; the rest is ignored by ecm3 since it will be or already has been factored independently as M(x) == 2^x - 1. Prime95's much greater speed, due to the FFT multiplication, is thus at least partially offset in that ecm3 is trying to factor smaller numbers - often _much_ smaller - when the exponent is composite. At least until George decides to improve Prime95 in this way.:) Further, since ecm3 can now handle even exponents, my data files, including lowM.txt, will now include data for even exponents. I have already added the data from the Cunningham Project's 2+ file and will update my web site's mersdata.zip and mersdata.gz data files within a day or so, after I check some details of my new update scripts and the newest version of ecm3. Lastly, feel free to send me data related to composite exponent Mersenne numbers; it will get added as I have time, as for the prime exponents. Note that the mers package trial factorers still only work for prime exponents; the sieving code needs to be substantially modified to deal with composite exponents. I will almost certainly not cure this defect any time soon, since ECM and P-1 are much faster than trial factoring, _especially_ for these smaller exponents. Will
Re: Mersenne: When triple checking fails
Ken Kriesel writes: M4190237 is not prime. Res64: 14FC0406840D6CF3. WQ1: 2DB378F5 (exponent) (result) (residue) (SW version) (security code) Do other programs (MacLucas, mersenne1, etc.) have a security code, or are those results on the honor system? They are on the honor system, at least for the mers package. That's because the source code to generate the security code must be secret; if the source code were available, someone could add it to any program and the result would appear to be legitimate no matter how the residue was generated. PrimeNet goes a step further and adds a random value to the bytes checksummed by the security code. This means that adding PrimeNet support to the mers package programs is presently impossible, at least in the sense of verified-by- security-code results, since I have no way of compiling the package anywhere but my Intel Linux box and have no way of distributing binaries (executables) even if someone else compiled them for me. But I am finally looking at adding PrimeNet support (without security codes) to the mers package programs. Don't expect anything soon, though. Will
Mersenne: Exponents
[EMAIL PROTECTED] writes: For some reason, Mr. Woltman didn't respond to the E-mail I sent him at [EMAIL PROTECTED] I'm sending it here in hopes that he'll see it: My friend AYL, who's been running Prime95 on a slow P75 on and off for a while, recently got a fast PII 400Mhz that's on 24hrs a day. So he just completed the two exponents which I got for him quite a while ago: 4631663 and 4631821. (He has no E-mail or Internet access). I'd like to request 10 or so more prime exponents to work on. :-D (10 should take about 2 months). I suggest that you do what I do for another no-email GIMPS member: use the manual checkin & reservation page of PrimeNet. I created an account for him with my email address and a name of 'His Name c/o Will Edgington'; that way, I get the email warnings about exponents timing out but I can also download a status report with only his data on it and put it on a diskette (along with the new version of Prime95 this time) to USMail to him. Will `
Re: Mersenne: Hitting the snail...
Brian J Beesley writes: > It would also - improperly - catch those of us that can't use the > automatic networking but whose machines are slower than the estimate > for some reason. A participant without email access that sends me > USMail with his data now and then is about to get caught by this for > an exponent that he's working on; 60 days simply isn't going to be > enough even though the prediction was for less than 40 days. Not neccessarily. Yes, it would, because only the automatic networking code in Prime95 is supported directly by the server. Since all my activitiy for the person noted above is via the manual web forms, his status report says the last activity by his account was in July even though I have submitted a new residue and a new factor already in October. I had to ask Scott to manually add 30 days to the predictions to prevent it from timing out an exponent part way thru the LL test. The only reason I won't have to do that repeatedly is Prime95's new ability to do double check LL tests of exponents already tested by Prime95. What I meant was, if the last date any message was received about an exponent is more than 4 months ago, reassign it, even if the expected completion date hasn't yet arrived. Yes, I agree that something like this has to be done. But it still causes problems, as described above. > Also, P-1 factoring, using Factor98, is still useful, there are still > many exponents under 1000 that noone is working on, and it will work > on exponents thru 170,000. Reserve exponents for P-1 by sending me > email; I also have some Factor98 save files for many exponents. Perhaps you should publicise this a bit... That was part of the reason I mentioned it, actually. Where else would it make sense to publicize it? Does ECM find only prime factors, or is it just that it is so much more likely to find factors which are numerically small, so that factors composed of a product of two or more largish primes are most unlikely to be discovered without discovering the prime factors? The mers package's ecm3 and ecmfactor only print prime factors because they check the primality of factors found and factor them in turn if they fail a pseudo-prime test. But they generally only find composite factors of Mersennes early on, with low bounds and no already known factors. How do you verify that an arbitary number with ~1000 digits really is prime? (Let alone a number ten times that length!) There are programs out there, notably Morain's ECPP (Elliptic Curve Primality Prover), that provide primality proofs. I don't have one myself, so I don't know a lot about them. I think the rules would have to state that the "prize" factor must be found using one of a set of specific programs, which must supply the "s number" so that the calculation can be verified. "S number"? And factors can be confirmed quickly and easily, much easier than large primes; what does it matter how it was produced as long as it's a new factor, previously unknown? Will
Re: Mersenne: Hitting the snail...
Brian J Beesley writes: Also this would catch those users still using 15.x, which doesn't have the same automatic mechanism for intermediate check-ins. It would also - improperly - catch those of us that can't use the automatic networking but whose machines are slower than the estimate for some reason. A participant without email access that sends me USMail with his data now and then is about to get caught by this for an exponent that he's working on; 60 days simply isn't going to be enough even though the prediction was for less than 40 days. I think trial factoring is far enough ahead that encouraging slow machines to do that isn't going to be helpful. However, slow machines can still run ECM factoring usefully. I think it would be better to encourage them to try ECM. Using slow machines for trial factoring still makes good sense to me; if nothing else, it means the faster machines are spending that much more time on LL tests, even if it is a small extra amount of time. ECM, as you note, is also productive; small exponents should be reserved with Paul Zimmerman of ECMNet (there's a link on www.mersenne.org). Also, P-1 factoring, using Factor98, is still useful, there are still many exponents under 1000 that noone is working on, and it will work on exponents thru 170,000. Reserve exponents for P-1 by sending me email; I also have some Factor98 save files for many exponents. (b) an annual prize for the numerically largest factor found during each calendar year - though I don't know where the money would come from. Neither do I; I'm still kind of surprised someone is offering money for the next Mersenne prime. And it would have to be worded very carefully; I can give you lots of very large factors quite quickly, including fifteen or more that are almost certainly prime but noone has proven to be prime. The largest is 9778 digits and would be the largest "hard" prime known by a wide margin. Would any of them count? I can likely find almost arbitrarily large ones in the future; how about them? And a prize for the smallest new factor would be even easier to rig in this fashion; I have a 10-15 year old program whose entire purpose is to print out small factors of Mersennes in _factor_ order! See my old postings about my "reverse method". Will
RE: Mersenne: Hitting the snail...
I suppose the factoring methods do not guarantee to find _prime_ factors. Correct. In fact, I recently added the ecmfactor program to the mers package precisely because other programs, notably Factor98 (which uses the P-1 method), print composite factors. I use ecmfactor routinely (once a week or so) to factor a composite factor discovered by someone else using Factor98. Ecmfactor uses the freeLIP library's ECM (Elliptic Curve Method) functions to factor arbitrary natural numbers. Ecm3 uses the same functions to factor Mersenne number cofactors (the part left after some known factors are divided out). Will
Re: Mersenne: Prediction
Yvan Dutil writes: Maybe a multi-level objective would be better. Say for 2001: -Exploration factoring up to 15 000 000 Depending on what you mean by "exploration", this is already done thru 21.5 million or so. -one L-L up to 10 000 000 -two L-L up to 6 000 000 Others can almost certainly better estimate how likely these are. -ECM complete factoring up to 100 000 This is, I think, wildly optimistic; it's quite likely that there will still be Mersenne numbers with exponents under 1000 that are not completely factored by 2001. M727 still has no known factors, for example, and no ECM effort for any exponent above 23,059 has been reported to me; in contrast, there's been some P-1 effort to just under 170,000. Further, there are far fewer people running ECM (or P-1) factoring than there are people running Lucas-Lehmer tests and 'complete' factoring is much harder than LL tests for the same exponent. There are still exponents under 1000 that noone is running P-1 on, for that matter; if you want to reserve some, send me email. Will
Re: Mersenne: Double-checking (was snails)
Eduard Kostolansky writes: Oh, GOD! I think, this will be the real death of us - UNIX double-checkers. Possible, I suppose, but for people that only have UNIX boxes and want to contribute ... Of course, there's always ECM factoring, NFSNet, Ernst Mayer's F90 code, and others. Note for Will Edgington: Will, I don't wanna die!! It's time to upgrade MacLucasUnix! Or is it impossible?? I'm sure it's possible, but I certainly don't know enough to improve the speed. And have not even had time to keep up with bug reports, recently, though that should change over the next few weeks. Will
