Mers package programs input and output format description $Id: mersfmt.txt,v 1.11 2006/01/02 23:12:46 wedgingt Exp $ The basic format of the mers programs, server, and so on is: M( {exponent} ){letter}[: {extent}][{,| #} {info}] ... where {exponent} is the power of two, {letter} is defined below, {extent} is the extent of trial factoring, a factor, or some other value depending on {letter}, a comma (,) or pound sign (#), and arbitrary {info} in free form. Every space in the format is literal in that at least one must be present. Square brackets like '[]' surround optional items and braces like '{}' surround descriptions of the data that goes there. Everything after the first comma or pound sign is presently ignored by my database update routines; this will change as I make improvements to retain the discoverer and method used in the database itself. Since most of the routines are shell scripts that include sorting on the exponent, extent, and letter, the spaces are important to separate fields for the generic UNIX/Linux sort program. The intent is to have one fairly simple format for all data so that all the programs can share code to read and write it; I have a long way to go to achieve that goal, but the mers package's rw.c's input() function and ecm3.c's main() program read and, when appropriate, write all or nearly all of the formats below and can also read certain other formats used by George Woltman and the Cunningham Project. Now, for the descriptions of the {letter}s presently in use. All examples contain actual data as of when each section was originally written or was last modified. M( {exponent} )P[{,| #} {info}] M( 3021377 )P 'P'rime, perhaps with info about the discovery. See primeM.txt for a complete list of known Mersenne prime exponents. M( {exponent} )C: {prime-factor}[{,| #} {info} M( 5056039 )C: 58799938797499937, golem.arc.nasa.gov (fd 48) #0 @ Fri Jul 25 02:34:39 1997 'C'omposite with known prime factor. The example is the output format of my (unreleased) TCP/IP server. M( {exponent} )C, {residue}[{,| #} {info}] M( 41 )C, 0x000000c771a34e19, n = 8, mersenne1 v2.50 Kline 'C'omposite with the Lucas-Lehmer residue and usually info on the program, version, user, and/or date. Verified residues are available at mersenne.org on the GIMPS status page in George Woltman's format. M( {exponent} )c: {digits}[{,| #} {info}] M( 1201 )c: 344 'c'ofactor of {digits} digits is known to be composite. The number of decimal digits is recorded since that will change every time a new factor is found. M( {exponent} )H: {extent}[{,| #} {info}] M( 727 )H: 9007199397668929 'H'ighest trial factor attempted. Mersenne is known to be composite. Note that some smaller trial factors may not have been attempted since my database updates presently assume that all factorers are trial factorers (see also the 'G' line below). The extent may be in (integer) power of two format: M( 727 )H: 2^53 The mers package program extract.c prints George Woltman's DATABASE file in this last format when given the -4 or the -m flag. M( {exponent} )U: {extent}[{,| #} {info}] M( 2147483743 )U: 844412082585031 'U'nknown primality. Extent is the highest trial factor attempted. The extent may be in power of two format as explained for 'H' lines. M( {exponent} )I: {extent}[{,| #} {info}] M( 3018241 )I: 9855104373917401 'I'nterrupted trial factor attempt. Same as 'U' except that extent itself should be re-checked. Mostly obsolete as of early 1996 as the only factorer that prints it is obsolete. M( {exponent} )D[{,| #} {info}] M( 7673 )D 'D'one; all prime factors are known. The largest prime factor may not be listed explicitly in a 'C' line. See also the 'L' and 'M' lines below. M( {exponent} )d[{,| #} {info}] M( 32531 )C: 65063 M( 32531 )C: 25225122959 M( 32531 )d 'd'one; all prime factors are thought to be known. The largest factor is at least a pseudo-prime in some base other than 2 and may not be listed explicitly in a 'C' line. See also the 'L' and 'M' lines below. M( {exponent} )e: {ECM bound} {curves/trials} [CPUsecs/curve] [{,| #} {info}] M( 601 )e: 3000000 1 Elliptic Curve Method curves tried at the given (first stage) bound. This is printed by ecm3.c. The database does not store this but instead adds it to the next (E:) line for the exponent. M( {exponent} )E: {ECM "work"} {ECM largest bound} [maxCPUsecs/curve] [{,| #} {info}] M( 601 )E: 17684960000 3000000 The ECM "work" and largest (stage 1) ECM bound attempted. The "work" is presently defined as the sum for all curves of the stage 1 bound used. M( {exponent} )o: {P-1 first stage bound} [P-1 second stage bound][{,| #} {info}] M( 727 )o: 15000000000 First and second stage bounds tested using a P-1 factorer. Note that the second stage bound is optional. M( {exponent} )q: {P+1 first stage bound} [P+1 second stage bound][{,| #} {info}] M( 727 )q: 0 0 First and second stage bounds tested using a P+1 factorer. M( {exponent} )G: {start of gap} {end of gap}[{,| #} {info}] M( 617 )G: 4093841106587383 4503599627370496 This denotes a gap in the trial factoring data. I presently keep it separately from the rest of the database. Note that this can also be used to account for the range having been tested by a buggy factorer that may have missed factors. M( {exponent} )g: {start} {stop}[{,| #} {info}] M( 4608557 )g: 51 51 This also denotes a gap in the trial factoring data, but restricted to starting and ending at a power of 2. The gap is from 2^(start - 1) thru 2^stop. E.g., the example indicates that M460857 has not been reliably checked for factors between 2^50 and 2^51. M( {exponent} )J: {start of "joined"/closed gap} {end of joined gap}[{,| #} {info}] M( 601 )J: 1203 1181614081 Denotes a "joined" gap in that it was produced by a trial factoring program that understands the 'G:' lines and is well tested and "well behaved" (e.g., will not produce gaps). The next four, L, M, l, and m, all relate to an algebraic factorization that applies only to composite exponents of the form n = 8*a - 4; the factors are the 'L' and 'M' "halves" referred to in the descriptions. The factorization is derived as follows: M(n) = M(8*a - 4) = 2^(8*a - 4) - 1 = (2^(4*a - 2))^2 - 1^2 = (2^(4*a - 2) - 1)*(2^(4*a - 2) + 1) = M(4*a - 2)*(M(4*a - 2) + 2) Thus, half of the factorization of M(n) (for any even n) will be taken care of by factoring M(n/2) = M(4*a - 2). The other half can be factored further into L and M: M(4*a - 2) + 2 = 2^(4*a - 2) + 1 = (2^(2*n - 1) - 2^n + 1)*(2^(2*n - 1) + 2^n + 1) = L*M Note that this factorization into L and M only works if the base, as for Mersenne numbers, is 2. M( {exponent} )L[{,| #} {info}] All prime factors are thought to be known of the 'L' part. The largest factor is at least a pseudo-prime in some base other than 2 and may not be listed explicitly in a 'C' line. M( {exponent} )M[{,| #} {info}] All prime factors are thought to be known of the 'M' part. The largest factor is at least a pseudo-prime in some base other than 2 and may not be listed explicitly in a 'C' line. Note that if both the L and M parts are thought to be completely factored, then the database may contain a 'd' or 'D' line (both described above) rather than the 'L' and 'M' lines. M( {exponent} )l: {digits}[{,| #} {info}] The L half's cofactor of {digits} digits is known to be composite. The number of decimal digits is recorded since that will change every time a new factor is found. M( {exponent} )m: {digits}[{,| #} {info}] The M half's cofactor of {digits} digits is known to be composite. The number of decimal digits is recorded since that will change every time a new factor is found. Back to my Mersenne page . The mers package of software that contains rw.c, input(), and ecm3.c, which I maintain, including the README.html file, is also available here and the current beta release is in beta.tgz ; both, with the '.tgz' extension, can be read by WinZip as well as the FSF's gunzip and UNIX/Linux tar programs. The current lowM.txt file, which records all data known to me for exponents less than 200,000, is in mersdata.zip, zip'd and mersdata.tgz, tar'd and then zip'd . Please send comments, ideas, questions, etc. to me, Will Edgington (permanent).