Skip to content

FactorInteger

Status: Stable

documented, exercised by the test suite and/or worked examples, with no known limitations recorded.

Description

FactorInteger[n] gives a list of the prime factors of the integer n, together with their exponents.

Examples (8)

Every input below was run against the current Mathilda build and its output recorded.

Basic examples (4)

In[1]:= FactorInteger[12]
Out[1]= {{2, 2}, {3, 1}}

In[2]:= FactorInteger[-12]
Out[2]= {{-1, 1}, {2, 2}, {3, 1}}

In[3]:= FactorInteger[3/4]
Out[3]= {{2, -2}, {3, 1}}

In[4]:= FactorInteger[100, 1]
Out[4]= {{2, 2}}

Applications (4)

In[5]:= FactorInteger[60]
Out[5]= {{2, 2}, {3, 1}, {5, 1}}

In[6]:= FactorInteger[2^67 - 1]
Out[6]= {{193707721, 1}, {761838257287, 1}}

In[7]:= FactorInteger[20!]
Out[7]= {{2, 18}, {3, 8}, {5, 4}, {7, 2}, {11, 1}, {13, 1}, {17, 1}, {19, 1}}

In[8]:= FactorInteger[1000000000000066600000000000001]
Out[8]= {{1000000000000066600000000000001, 1}}

Implementation notes

Algorithm. builtin_factorinteger drives the recursive factorize_mpz, which factors a working mpz_t (mutated in place) and accumulates {prime, exponent} pairs. The Automatic cascade is: GMP Miller–Rabin primality (mpz_probab_prime_p, 25 rounds) returns the number itself if prime; trial division by the first 25 cached primes strips small factors; then Pollard rho (Brent's improved variant with batched GCDs, pollard_rho_brent_mpz) splits a composite cofactor; finally, if rho fails, the vendored GMP-ECM library (ecm_factor, src/external/ecm/) is run with a ladder of increasing B1 bounds {2000, 11000, ..., 1.1e7}, also serving as Pollard p−1 (ECM_PM1) and Williams p+1 (ECM_PP1) when those methods are requested. Each split recurses on both cofactors. The Method option can force a specific algorithm: trial, rho, ECM, p−1, p+1, Fermat (fermat_factor_mpz), CFRAC (cfrac_factor_mpz), Dixon (dixon_factor_mpz), SQUFOF (squfof_factor_mpz), or a random-by-difference probe (rbd_factor_mpz). When all bounded attempts fail, the residual is recorded as a single (assumed-prime) factor.

Data structures. A fixed FactorMpz array of {mpz_t p, int64 count}; add_factor_mpz merges repeated primes by bumping the exponent. The final list is qsort-ed by mpz_cmp (compare_factors_mpz) and emitted as a List of two-element {p, e} Lists. A sieve-built prime table (pi_primes, Eratosthenes up to MAX_PRIME_LIMIT = 10^6) backs trial division and is shared with PrimePi/EulerPhi.

Complexity / limits. Trial division catches tiny factors cheaply; Pollard rho finds a factor p in expected O(p^{1/2}) iterations; ECM's expected time is subexponential in the size of the smallest factor (L_p[1/2, sqrt 2]), making it effective for moderate factors of large composites. The ECM B1 ladder and rho iteration caps bound work, so a hard semiprime with two large factors may be returned partly unfactored as a single composite "factor".

  • Listable, Protected.
  • Supports negative integers (includes {-1, 1}).
  • Supports rational numbers (denominator factors have negative exponents).
  • Perfect powers are reduced before the general search: n = base^m is peeled to a primitive base, factored once, and the exponents scaled by m. This is what makes prime powers of a large prime (e.g. (2^61-1)^2) factor correctly rather than being mislabelled as prime — Pollard rho and ECM alone cannot split such powers.
  • FactorInteger::nofac: under the default Automatic method, a hard composite (e.g. a semiprime of two large distinct primes) that survives trial division, Pollard rho and ECM within the search bounds is returned unfactored with exponent 1 — which looks like a prime factor. A warning is emitted to make that compromise explicit rather than silent. It is suppressed inside routines that mute arithmetic warnings (numeric integration, Limit, Series, …).

Attributes: Listable, Protected.

References

See also: Limit, Series

  • J. M. Pollard, "A Monte Carlo method for factorization", BIT 15 (1975).
  • R. P. Brent, "An improved Monte Carlo factorization algorithm", BIT 20 (1980).
  • J. M. Pollard, "Theorems on factorization and primality testing", Proc. Cambridge Phil. Soc. 76 (1974) (p−1 method).
  • H. W. Lenstra Jr., "Factoring integers with elliptic curves", Annals of Mathematics 126 (1987).
  • D. Shanks, square forms factorization (SQUFOF).
  • M. A. Morrison and J. Brillhart, "A method of factoring and the factorization of F_7", Math. Comp. 29 (1975) (CFRAC).
  • Source: src/facint.c
  • Specification: docs/spec/builtins/number-theory.md
  • Tests: tests/test_bigint.c
  • Tests: tests/test_core.c
  • Tests: tests/test_partitionsp.c
  • Tests: tests/test_power_integer_radical.c

Notes & additional examples

Notes

FactorInteger[n] returns {prime, exponent} pairs. 2^67 - 1 reproduces F. N. Cole's celebrated 1903 factorisation of the Mersenne number M₆₇ into 193707721 × 761838257287, demonstrating the vendored GMP-ECM backend on a hard semiprime. The exponent vector of 20! is exactly Legendre's formula applied to each prime ≤ 20. The thirty-one-digit "Belphegor prime" 10^30 + 666·10^14 + 1 is returned as a single factor, i.e. it is certified prime.