Instructions to link with George Woltman's gwnum.a library. Note that gwnum is only used for Stage 1 of ECM. Stage 2 is not affected. Users should familiarize themselves with the instructions in "INSTALL-ecm" before attempting the procedures here. 0) Download Prime 95 source files. As of June 2024, the current release is: https://www.mersenne.org/download/software/v30/30.19/p95v3019b20.source.zip Check links appended to "https://www.mersenne.org/download/software/" for future Prime 95 releases. Note: due to critical bug fixes in the gwnum/ecmstag1.c and FFT assembly files used by GMP-ECM, versions of P95 before v3019b12 will not work here (make check will fail) and should not be used. Unzip/extract the P95 file to any convenient location. 1) Build gwnum.a. Navigate to the directory /gwnum. Follow the instructions for your machine/OS in the readme.txt file. For example, on 64-bit linux systems the command to execute is "$ make -f make64". 2) Configure and build with the gwnum.a library. Navigate back to the ECM build directory. If you have previously configured and built ECM, execute the command $ make clean Now execute the command $ ./configure --with-gwnum= The directory must include the gwnum.a file as well as gwnum.h and related header files. For example, if the ECM and p95 folders are both in the same home folder, the command might look like $ ./configure --with-gwnum=../p95v3019b20.source/gwnum Note that you may also need to specify "--with-gmp=" if "configure" has trouble finding GMP. The line "configure: Linking with George Woltman's GWNUM" should appear near the end of the configure output. 3) compile the program with: $ make 4) To check that the program works correctly, type: $ make check This will run several tests for P+1, P-1, ECM, & ECM with gwnum. These tests take a few minutes. It should normally end with the "TOTAL" count equal to the "PASS" count, with the remaining counts all zero. 5) Usage. ECM with gwnum now has full capability to help find factors for integers of any form. Prior to this release gwnum was limited to processing input integers of the form "(k*b^n+c)/(factors, if any)". This is still the preferred form, if possible, since gwnum is optimized for such input. Note that to use gwnum, input numbers must be greater than 2^350, regardless of form. (1) When the "k*b^n+c" form is used, the 'k*' term is not required if k = 1. The exponent 'n' may be entered as an integer or in the form (b2^n2), with 'n' or '(b2^n2)' < 10^10. Also, k must be a positive integer with 1 <= k < 2^53, and c must be a non-zero integer with |c| < 2^23. Note that the k upper limit of 2^53-1 is taken from the file p95v3019b20.source/gwnum/gwnum.c, line 2181: "if (k > 9007199254740991.0) return (GWERROR_K_TOO_LARGE);" and is subject to change by Woltman. (2) For integer-character-only input strings N, GMP-ECM may detect if N = k*b^n+c, and find k, b, n, and c, but if possible the "k*b^n+c" form should be used. (3) Special note: the kbnc form should be used even if we are only interested in a part of it. For example, suppose we wish to attempt to factor the Cunningham number 2,4882M = 2^2441+2^1221+1, which has 5 as a factor. We could enter it as "(2^2441+2^1221+1)/5" on the command line, and the gwnum generic code would be used. But stage 1 will actually be faster if we enter it as "(2^4882+1)/(5*(2^2441-2^1221+1))", since gwnum will use the kbnc form 2^4882+1. Here is some sample output to illustrate: $ echo "(2^2441+2^1221+1)/5" | ./ecm -sigma 0:8796261600422429213 -go 11685787 12e5 33e6 GMP-ECM 7.0.6 [configured with GMP 6.3.0, GWNUM 30.19, --enable-asm-redc, --enable-assert] [ECM] Due to incompatible licenses, this binary file must not be distributed. Input number is (2^2441+2^1221+1)/5 (735 digits) Using B1=1200000, B2=33000000, polynomial x^2, sigma=0:8796261600422429213 Using gwnum_ecmStage1_generic(1200000, 1) Step 1 took 16734ms Step 2 took 515ms ********** Factor found in step 2: 28560168011064685473913587072588901 Found prime factor of 35 digits: 28560168011064685473913587072588901 Composite cofactor ((2^2441+2^1221+1)/5)/28560168011064685473913587072588901 has 700 digits $ echo "(2^4882+1)/(5*(2^2441-2^1221+1))" | ./ecm -sigma 0:8796261600422429213 -go 11685787 12e5 33e6 ...Input number is (2^4882+1)/(5*(2^2441-2^1221+1)) (735 digits) ...Using gwnum_ecmStage1(1, 2, 4882, 1, 1200000, 1) Step 1 took 7871ms Step 2 took 519ms ********** Factor found in step 2: 28560168011064685473913587072588901 In contrast, the same input but with "-force-no-gwnum" in the command line had the following timings: Using Lucas chain codes Step 1 took 22331ms Step 2 took 525ms (4) Since the gwnum routines use classical Montgomery curves of the form By^2 = x^3 + Ax^2 + x, "-param 0" or "-sigma 0:" should always be specified on the command line. Note that -param may default to 1 if "-param" is unspecified, in which case the gwnum routines will not be used. The message "Using gwnum_ecmStage1(k, b, n, c, B1, gw_B1done)" or the message "Using gwnum_ecmStage1_generic(B1, gw_B1done)" (with parameters replaced by actual values) will be output at the start of stage 1 whenever one of the gwnum routines is used. If one of these messages is expected but doesn't appear, repeat the test with "-v" (verbose) in the command line to discover the reason. 6) Thresholds. The file "ecm-impl.h" now includes estimates of the input bit sizes above which gwnum will be used: #define GWNUM_KBNC_THRESHOLD 1130 /* bits */ #define GWNUM_SPEC_DIV_THRESHOLD 1215 /* bits */ #define GWNUM_GENERIC_THRESHOLD 2100 /* bits */ The "SPEC_DIV" threshold is specific to inputs of the form 2^n+/-1, for which ECM uses "special division" for reduction. Since we currently have no tuning capability for these, and the thresholds may vary considerably from machine to machine, we now have two new command line invocations which the user may use to control gwnum usage for any particular test: "-force-gwnum" - override the thresholds in ecm-impl.h and require gwnum routines to be used for any input number greater than 2^350, which is the gwnum.a library threshold. "-force-no-gwnum" - gwnum routines will not be used. Use of these switches allows any user to estimate thresholds on their machine, edit "ecm-impl.h" accordingly, and rebuild. 7) Speedups. Depending on input number size relative to the thresholds, stage 1 timing comparisons with & without gwnum can range from a few percent near the threshold to factors of 10 and beyond for larger inputs. Here are two runs, the first without gwnum, and the next with gwnum, for the generalized Fermat number 6^2048+1: $ echo "(6^(2^11)+1)/(96479889653761)" | ./ecm -force-no-gwnum -sigma 0:6685190033435505716 21e6 9e9 ...Input number is (6^(2^11)+1)/(96479889653761) (1580 digits) Using B1=21000000, B2=9000000000, polynomial Dickson(6), sigma=0:6685190033435505716 Using Lucas chain codes Step 1 took 1299300ms Step 2 took 42448ms ********** Factor found in step 2: 27235071532927521153002936160735956993 Found prime factor of 38 digits: 27235071532927521153002936160735956993 Composite cofactor ((6^(2^11)+1)/(96479889653761))/27235071532927521153002936160735956993 has 1543 digits $ echo "(6^(2^11)+1)/(96479889653761)" | ./ecm -sigma 0:6685190033435505716 21e6 9e9 ...Using gwnum_ecmStage1(1, 6, 2048, 1, 21000000, 1) Step 1 took 145443ms Step 2 took 42417ms ********** Factor found in step 2: 27235071532927521153002936160735956993 Found prime factor of 38 digits: 27235071532927521153002936160735956993 Composite cofactor ((6^(2^11)+1)/(96479889653761))/27235071532927521153002936160735956993 has 1543 digits As is easily seen, (no gwnum stage 1 time)/(gwnum stage 1 time) = 8.93 (!) ============================================================================ In case of a problem, report it to us, with: - the output of the config.log file - the versions of GMP-ECM, GMP, and GWNUM used (first output line), for example: GMP-ECM x.y.z [configured with GMP u.v.w, GWNUM r.s, --enable-asm-redc] [P+1] - the detailed input enabling us to reproduce the problem, for example: $ echo 328006342451 | ./ecm -pp1 -x0 5 120 7043 - the output you get. Then send your bug report at . This is a public list, with archives available at .