Introduction

Several C/C++ libraries provide efficient integer factorization: GMP (GNU Multiple Precision Arithmetic Library) for arbitrary-precision arithmetic and basic factoring, FLINT for fast number theory operations, NTL for algebraic number theory, and PARI/GP for comprehensive number-theoretic computations including ECM and MPQS factoring. For cryptographic-scale numbers (100+ digits), Msieve and YAFU implement the most advanced algorithms (GNFS, SIQS).

GMP (GNU Multiple Precision Arithmetic Library)

GMP is the most widely used C library for arbitrary-precision integers. While it does not include built-in factoring functions, it provides the building blocks:

1#include <gmp.h>
2#include <stdio.h>
3
4// Trial division using GMP
5void trial_factor(mpz_t n) {
6    mpz_t factor, remainder;
7    mpz_inits(factor, remainder, NULL);
8    mpz_set_ui(factor, 2);
9
10    while (mpz_cmp_ui(n, 1) > 0) {
11        mpz_mod(remainder, n, factor);
12        if (mpz_cmp_ui(remainder, 0) == 0) {
13            gmp_printf("Factor: %Zd\n", factor);
14            mpz_divexact(n, n, factor);
15        } else {
16            mpz_add_ui(factor, factor, 1);
17        }
18    }
19    mpz_clears(factor, remainder, NULL);
20}
21
22int main() {
23    mpz_t n;
24    mpz_init_set_str(n, "123456789012345678901234567890", 10);
25    trial_factor(n);
26    mpz_clear(n);
27    return 0;
28}
29
30// Compile: gcc factor.c -lgmp -o factor

GMP also provides mpz_probab_prime_p() for primality testing, which is essential for factoring algorithms:

if (mpz_probab_prime_p(n, 25) >= 1) {
    gmp_printf("%Zd is prime\n", n);
}

FLINT (Fast Library for Number Theory)

FLINT builds on GMP and provides optimized number theory functions:

1#include <flint/fmpz.h>
2#include <flint/fmpz_factor.h>
3#include <stdio.h>
4
5int main() {
6    fmpz_t n;
7    fmpz_init(n);
8    fmpz_set_str(n, "1234567890123456789", 10);
9
10    fmpz_factor_t factors;
11    fmpz_factor_init(factors);
12
13    // Factor the integer
14    fmpz_factor(factors, n);
15
16    // Print factors
17    for (slong i = 0; i < factors->num; i++) {
18        fmpz_print(factors->p + i);
19        printf("^%lu ", factors->exp[i]);
20    }
21    printf("\n");
22
23    fmpz_factor_clear(factors);
24    fmpz_clear(n);
25    return 0;
26}
27
28// Compile: gcc factor.c -lflint -lgmp -o factor

FLINT's fmpz_factor() uses a combination of trial division, Pollard's rho, and SQUFOF for efficient factoring of medium-sized integers.

NTL (Number Theory Library)

NTL provides a C++ interface for number theory:

1#include <NTL/ZZ.h>
2#include <NTL/BasicThreadPool.h>
3#include <iostream>
4
5using namespace NTL;
6
7// Pollard's rho algorithm using NTL
8ZZ pollard_rho(const ZZ& n) {
9    ZZ x = RandomBnd(n);
10    ZZ y = x;
11    ZZ c = RandomBnd(n);
12    ZZ d;
13
14    do {
15        x = (x * x + c) % n;
16        y = (y * y + c) % n;
17        y = (y * y + c) % n;
18        d = GCD(abs(x - y), n);
19    } while (d == 1);
20
21    return d;
22}
23
24int main() {
25    ZZ n;
26    n = conv<ZZ>("123456789012345678901234567890");
27
28    // Primality test
29    if (ProbPrime(n)) {
30        std::cout << n << " is prime" << std::endl;
31    } else {
32        ZZ factor = pollard_rho(n);
33        std::cout << "Factor: " << factor << std::endl;
34    }
35    return 0;
36}
37
38// Compile: g++ factor.cpp -lntl -lgmp -lpthread -o factor

PARI/GP

PARI provides the most comprehensive built-in factoring:

1#include <pari/pari.h>
2
3int main() {
4    pari_init(1000000, 2);  // 1MB stack, max prime 2
5
6    // Factor an integer
7    GEN n = strtoi("123456789012345678901234567890");
8    GEN factors = factorint(n, 0);  // 0 = default algorithm
9
10    // factors is a 2-column matrix: [prime, exponent]
11    output(factors);
12
13    pari_close();
14    return 0;
15}
16
17// Compile: gcc factor.c -lpari -o factor

PARI's factorint() automatically selects the best algorithm (trial division, Pollard rho, ECM, MPQS) based on the number's size.

Msieve and YAFU (Advanced Factoring)

For very large numbers (80+ digits), use dedicated factoring tools:

1# Msieve — implements GNFS and SIQS
2./msieve -q 123456789012345678901234567890
3
4# YAFU — automated factoring with multiple algorithms
5./yafu "factor(123456789012345678901234567890)"

These can be called from C/C++ via system() or by linking their libraries directly.

Algorithm Comparison

Installation

1# GMP
2sudo apt install libgmp-dev          # Debian/Ubuntu
3brew install gmp                      # macOS
4
5# FLINT
6sudo apt install libflint-dev
7brew install flint
8
9# NTL
10sudo apt install libntl-dev
11brew install ntl
12
13# PARI
14sudo apt install libpari-dev
15brew install pari

Common Pitfalls

• Using trial division for large numbers: Trial division is O(sqrt(n)), which is impractical beyond 20-digit numbers. For numbers above 10^12, switch to Pollard's rho or ECM. Libraries like FLINT automatically select the appropriate algorithm.
• Not checking primality before factoring: Running a factoring algorithm on a prime number wastes time. Always test with mpz_probab_prime_p() (GMP) or ProbPrime() (NTL) first. If the number is prime, it is its own only factor.
• Memory leaks with GMP types: GMP requires manual memory management — every mpz_init() must have a corresponding mpz_clear(). Forgetting to clear temporaries in loops causes memory leaks. Use mpz_clears() for multiple variables.
• Linking order matters: GMP-dependent libraries must be linked in the correct order. Use -lflint -lgmp (FLINT before GMP), not -lgmp -lflint. The linker resolves symbols left-to-right, so dependent libraries must come first.
• Assuming factoring is fast for any size: Integer factoring is computationally hard — no known polynomial-time classical algorithm exists. A 100-digit number can take hours to factor even with the best algorithms. Set realistic expectations and timeouts for production code.

Summary

• GMP: Foundation library for arbitrary-precision arithmetic; build your own factoring on top
• FLINT: Fast, batteries-included factoring via fmpz_factor() using trial division + Pollard rho + SQUFOF
• NTL: C++ number theory library with GCD, primality testing, and building blocks for custom algorithms
• PARI/GP: Most comprehensive built-in factoring with automatic algorithm selection (ECM, MPQS)
• Msieve/YAFU: Dedicated tools for very large numbers (80+ digits) using GNFS and SIQS
• Choose the library based on number size: FLINT for medium (up to 50 digits), PARI for large (up to 100), Msieve for very large (100+)