ECM(1)

📦
version 7.0.7 · 6 versions
, in fedora 43, fedora 44

💖 ECM(1) 💖

okay bestie, sit DOWN, we're learning ecm — and yes it's from the ECM(1) manual, April 22, 2003, and yes we're doing the whole thing, no skimming, no shortcuts, periodt. 💅

✨ NAME ✨

ecm — integer factorization using ECM, P-1 or P+1 🧚

✨ SYNOPSIS ✨

ecm [options] B1 [B2min-B2max | B2]

✨ DESCRIPTION ✨

So ecm is an integer factoring program, and it's giving main character energy because it can do three whole methods: the Elliptic Curve Method (ECM), the P-1 method, or the P+1 method. 🌸

The sections below walk you through every parameter that matters for these algorithms. No gatekeeping here, we're going through all of it. 🫶

✨ STEP 1 AND STEP 2 BOUND PARAMETERS ✨

🌟 B1

B1 is the step 1 bound. It's mandatory, bestie, you literally cannot skip it. 😤

You can hand it over either as an integer (like 3000000) or in floating-point format (3000000.0 or 3e6, same vibe).

The biggest possible B1 value is 9007199254740996 for P-1, and for ECM and P+1 it's ULONG_MAX or 9007199254740996 — whichever one is smaller.

Every single prime 2 <= p <= B1 gets processed in step 1. All of them. Slay. 🔥

🌟 B2

B2 is the step 2 bound, and it's optional — if you dip out and don't provide it, a default value gets computed from B1, and ngl that default should be pretty close to optimal. ✨

Same deal as B1: integer or floating-point format, your call.

The largest possible B2 value is approximately 9e23, but lowkey it depends on the number of blocks k if you use the -k option.

Every prime B1 <= p <= B2 gets processed in step 2. And heads up: if B2 < B1, then there's no step 2 at all, it just doesn't happen. 💀

🌟 B2min-B2max

Alternatively (yes there's an alternative, we love options 🎀) you can use the B2min-B2max form, which means all primes B2min <= p <= B2max should be processed.

So basically, specifying just B2 alone corresponds to B1-B2.

The values of B2min and B2max can be arbitrarily large — go off — but their difference must not exceed approximately 9e23, and that's subject to the number of blocks k. 🦋

✨ FACTORING METHOD ✨

  • -pm1 — Perform P-1 instead of the default method (which is ECM). Switch it up bestie 💜
  • -pp1 — Perform P+1 instead of the default method (which is, again, ECM). ✨

✨ GROUP AND INITIAL POINT PARAMETERS ✨

  • -x0 x — [ECM, P-1, P+1] Use x (an arbitrary-precision integer or rational) as the initial point. For example, -x0 1/3 is valid — yes, a fraction, we love to see it. 💅 If you don't give it, x gets generated from the sigma value for ECM, or at random for P-1 and P+1.
  • -sigma s — [ECM] Use s (an arbitrary-precision integer) as the curve generator. If you skip it, s is generated at random. 🎲
  • -A a — [ECM] Use a (an arbitrary-precision integer) as the curve parameter. If you omit it, it gets generated from the sigma value. 🌀
  • -go val — [ECM, P-1, P+1] Multiply the initial point by val, which can be any valid expression, and it might contain the special character N as a placeholder for the current input number. Iconic. For example:
ecm -pp1 -go "N^2-1" 1e6 < composite2000

✨ STEP 2 PARAMETERS ✨

  • -k k — [ECM, P-1, P+1] Perform k blocks in step 2. For a given B2 value, increasing k decreases the memory usage of step 2 — at the cost of more CPU time. Trade-offs, bestie, it's giving balance ⚖️
  • -treefile file — Stores some tables of data in disk files to reduce the amount of memory occupied in step 2, at the expense of disk I/O. Data will be written to files file.1, file.2 etc. Heads up though: this does not work with fast stage 2 for P+1 and P-1. 😭
  • -power n — [ECM] Use x^n for Brent-Suyama's extension (-power 1 disables Brent-Suyama's extension entirely). The default polynomial is chosen depending on the method and B2. 🧮
  • -dickson n — [ECM] Use degree-n Dickson's polynomial for Brent-Suyama's extension. ✨
  • -maxmem n — Use at most n megabytes of memory in stage 2. Memory budget era 💸
  • -ntt, -no-ntt — Enable or disable the Number-Theoretic Transform code for polynomial arithmetic in stage 2. With NTT, dF is chosen to be a power of 2, and is limited by the number of suitable primes that fit in a machine word (which is a limitation only on 32-bit systems, so if you're on 64-bit, chill 🧊). The -no-ntt variant uses more memory, but is faster than NTT with large input numbers. By default, NTT is used for P-1, P+1, and for ECM on numbers of size at most 30 machine words.

✨ OUTPUT ✨

  • -q — Quiet mode. 🤫 Found factorizations are printed on standard output, with factors separated by white spaces, one line per input number (and if no factor was found, the input number is simply copied). No drama, just facts.
  • -v — Verbose mode. More information gets printed, and more -v options increase verbosity. With one -v, you get the kind of modular multiplication used, the initial x0 value, step 2 parameters and progress, plus expected curves and time to find factors of different sizes for ECM. With -v -v, the A value for ECM and residues at the end of step 1 and step 2 get printed. More -v prints internal data for debugging. 🐛 Spill the tea, honestly.
  • -timestamp — Print a time stamp whenever a new ECM curve or P+1 or P-1 run is processed. ⏰

✨ MODULAR ARITHMETIC OPTIONS ✨

There are several algorithms available for modular multiplication, and the program tries to find the best one for each input. But if you want to be that girl and force a specific method, these are your options:

  • -mpzmod — Use GMP's mpz_mod function (sub-quadratic for large inputs, but it induces some overhead for small ones). 🫠
  • -modmuln — Use Montgomery's multiplication (quadratic version). Usually the best method for small input. 🥇
  • -redc — Use Montgomery's multiplication (sub-quadratic version). Theoretically optimal for large input. 👑
  • -nobase2 — Disable the special base-2 code (which is used when the input number is a large factor of 2^n+1 or 2^n-1, see -v). 🙈
  • -base2 n — Force use of the special base-2 code. The input number must divide 2^n+1 if n > 0, or 2^|n|-1 if n < 0. ⚠️

✨ FILE I/O ✨

These options let you perform step 1 and step 2 separately — on different machines, at different times, or using different software. And bestie, specifically: George Woltman's Prime95/mprime program can produce step 1 output suitable for resuming with GMP-ECM. 🤝 It can also be useful to split step 2 into several runs, using the B2min-B2max option.

  • -inp file — Take input from file instead of from standard input. 📂
  • -save file — Save the result of step 1 in file. If file already exists, an error is raised. Example: to perform only step 1 with B1=1000000 on the composite number in the file "c155" and save its result in file "foo", use:
ecm -save foo 1e6 1 < c155
  • -savea file — Like -save, but it appends to existing files. 📎
  • -resume file — Resume residues from file, and it reads from standard input if file is "-". Example: to perform step 2 following the above step 1 computation, use:
ecm -resume foo 1e6
  • -chkpoint file — Periodically write the current residue in stage 1 to file. In case of a power failure, etc., the computation can be continued with the -resume option. 💾 (surviving the chaos, we love to see it)
ecm -chkpnt foo -pm1 1e10 < largenumber.txt

✨ LOOP MODE ✨

The “loop mode” (that's option -c n) lets you run several curves on each input number. The following options control how it behaves. 🌀

  • -c n — Perform n runs on each input number (default is one). This option is mainly useful for P+1 (for example with n=3) or for ECM, where n could be set to the expected number of curves needed to find a d-digit factor with a given step 1 bound. This option is incompatible with -resume, -sigma, -x0. Giving -c 0 produces an infinite loop until a factor is found. 😵‍💫 (not me typing -c 0 and forgetting about it, fr fr)
  • -one — In loop mode, stop when a factor is found. The default is to continue until the cofactor is prime or the specified number of runs are done. ✋
  • -b — Breadth-first processing: in loop mode, run one curve for each input number, then a second curve for each one, and so on. This is the default mode with -inp. 🍞
  • -d — Depth-first processing: in loop mode, run n curves for the first number, then n curves for the second one, and so on. This is the default mode with standard input. 🕳️
  • -ve n — In loop mode, in the second and following runs, output only expressions that have at most n characters. Default is -ve 0. ✂️
  • -i n — In loop mode, increment B1 by n after each curve. 📈
  • -I n — In loop mode, multiply B1 by a factor depending on n after each curve. Default is one, which should be optimal on one machine, while -I 10 could be used when trying to factor the same number simultaneously on 10 identical machines. 🖥️🖥️🖥️

✨ SHELL COMMAND EXECUTION ✨

These options (typo in the original, we keep it 💅) allow for executing shell commands to supplement functionality to GMP-ECM. Very collab of them. 🤝

  • -prpcmd cmd — Execute command cmd to test primality of factors and cofactors, instead of GMP-ECM's own functions. The number to test is passed via stdin. An exit code of 0 is interpreted as “probably prime”, a non-zero exit code as “composite”. 🕵️
  • -faccmd cmd — Executes command cmd whenever a factor is found by P-1, P+1 or ECM. The input number, factor and cofactor are passed via stdin, each on a line. This could be used i.e. to mail new factors automatically:
ecm -faccmd 'mail -s “$HOSTNAME found a factor”
                me@myaddress.com' 11e6 < cunningham.in
  • -idlecmd cmd — Executes command cmd before each ECM curve, P-1 or P+1 attempt on a number is started. If the exit status of cmd is non-zero, GMP-ECM terminates immediately, otherwise it continues normally. GMP-ECM is stopped while cmd runs, offering a way for letting GMP-ECM sleep for example while the system is otherwise busy. 😴 (self-care for your CPU)

✨ MISCELLANEOUS ✨

  • -n — Run the program in “nice” mode (below normal priority). 😇
  • -nn — Run the program in “very nice” mode (idle priority). 🥹 (so polite)
  • -B2scale f — Multiply the default step 2 bound B2 by the floating-point value f. Example: -B2scale 0.5 divides the default B2 by 2. 🪄
  • -stage1time n — Add n seconds to stage 1 time. This is useful to get correct expected time with -v if part of stage 1 was done in another run. ⏱️
  • -cofdec — Force cofactor output in decimal (even if expressions are used). 🔢
  • -h, --help — Display a short description of ecm usage, parameters and command line options. 🆘
  • -printconfig — Prints configuration parameters used for the compilation and exits. 🛠️

✨ INPUT SYNTAX ✨

The input numbers can have several forms, and honestly? The range. 🌈

Raw decimal numbers like 123456789. Simple, clean, we love her.

Comments can be placed in the file: everything after “//” is ignored, up to the end of line. 💬

Line continuation: if a line ends with a backslash character “\”, it is considered to continue on the next line. ➡️

Common arithmetic expressions can be used. Example: 3*5+(2+7)^10. 🧠

Factorial: example 53!. ❗

Multi-factorial: example 15!3 means 15*12*9*6*3. ❗❗❗

Primorial: example 11# means 2*3*5*7*11. #️⃣

Reduced primorial: example 17#5 means 5*7*11*13*17. ✂️

🌟 Functions:

  • GCD(a,b): Greatest common divisor — example GCD(120,28) = 4 🫶
  • Phi(n,x): n-th Cyclotomic Polynomial evaluated at x — example Phi(3,5) = 1 + x + x^2 = 31 🌀

and bestie… there's more 💜 (this was only part 1, keep reading)

✨ EXIT STATUS ✨

okay bestie, when ecm finally logs off, its exit status is literally the receipts 🧾 — it reflects the result of the last ECM curve or P-1/P+1 attempt the program performed. The individual bits are giving very specific energy:

  • Bit 0 — 0 if normal program termination, 1 if error occurred
  • Bit 1 — 0 if no proper factor was found, 1 otherwise
  • Bit 2 — 0 if factor is composite, 1 if factor is a probable prime
  • Bit 3 — 0 if cofactor is composite, 1 if cofactor is a probable prime

so thus, the following exit status values may occur:

  • 0 — Normal program termination, no factor found
  • 1 — Error
  • 2 — Composite factor found, cofactor is composite
  • 6 — Probable prime factor found, cofactor is composite
  • 8 — Input number found
  • 10 — Composite factor found, cofactor is a probable prime
  • 14 — Probable prime factor found, cofactor is a probable prime

🐛 BUGS 🐛

Report bugs on <https://gitlab.inria.fr/zimmerma/ecm/>. fr fr, they wanna know 💖

👑 AUTHORS 👑

These absolute icons made ecm happen:

  • Pierrick Gaudry <gaudry at lix dot polytechnique dot fr> — contributed efficient assembly code for combined mul/redc;
  • Jim Fougeron <jfoug at cox dot net> — contributed the expression parser and several command-line options;
  • Laurent Fousse <laurent at komite dot net> — contributed the middle product code, the autoconf/automake tools, and is the maintainer of the Debian package;
  • Alexander Kruppa <(lastname)al@loria.fr> — contributed estimates for probability of success for ECM, the new P+1 and P-1 stage 2 (with P.-L. Montgomery), new AMD64 asm mulredc code, and some other things;
  • Dave Newman <david.(lastname)@jesus.ox.ac.uk> — contributed the Kronecker-Schoenhage and NTT multiplication code;
  • Jason S. Papadopoulos — contributed a speedup of the NTT code
  • Paul Zimmermann <zimmerma at loria dot fr> — is the author of the first version of the program and chief maintainer of GMP-ECM.
Note: email addresses have been obscured, the required substitutions should be obvious.

this iconic manual page is ECM(1), page date 11/03/2023, and the footer also carries April 22, 2003 — slay, we're done bestie 💅✨

📦 where this page comes from