Integer factorization ($N={\prod }_p{p}^{v_p(N)}$)

Integer factorization seeks the prime factorization of a positive integer $N$. For $N>1$, this means identifying its prime factors and their multiplicities; one has the empty prime factorization. Finding one proper divisor $1<d<N$ is useful progress, but need not finish the job: factor $d$ and $N/d$ further until all factors are prime numbers.

For example, $77=7\cdot 11$ is a semiprime, whereas $231=3\cdot 7\cdot 11$ has three prime factors. Primality testing asks whether a proposed integer is prime; it need not return a factor when the answer is no. Trial division is a direct factoring method: try division by small prime numbers until a divisor is found. More elaborate methods obtain a proper divisor through a greatest common divisor of $N$ with a specially constructed integer.

The beautiful trick in congruence of squares is that two integers with equal squares modulo $N$ can reveal different factors through their sum and difference. In the worked $N=77$ example, $20^2\equiv 13^2(\mathrm{mod}77)$ gives $\gcd (20-13,77)=7$ and $\gcd (20+13,77)=11$. Computing those greatest common divisors uses the Euclidean algorithm; it does not require trying every potential factor. A factor base supplies a systematic way to construct useful equal-square relations. ^[ref].

This connection is useful in cryptography because recovering the factors of an RSA cryptosystem modulus defeats the factoring assumption behind its construction. That application concerns large, carefully chosen inputs; the small examples here explain the arithmetic mechanism and are not benchmarks or estimates of present cryptographic security.

For an integer $n$ to be factored, John Pollard's method chooses an integer $a$ coprime to $n$ and an exponent $M$ divisible by many small prime powers. Compute $d=\gcd (a^M-1,n)$ by modular exponentiation and the Euclidean algorithm. If $1<d<n$, it is a proper factor. If a prime divisor $p$ of $n$ has $p-1\mid M$, Fermat's little theorem ensures $p\mid d$; success requires some other prime divisor not to divide $a^M-1$. Common choices are $M=B!$ and $M=\mathrm{lcm}(1,\dots ,B)$. The method exploits a smooth $p-1$, rather than a small factor $p$ itself.

A general-purpose classical integer factorization algorithm combining polynomial relations, arithmetic in number fields and sparse linear algebra to construct congruent squares modulo the input. Its familiar general-input complexity estimate is heuristic and subexponential in the input's value, roughly $\exp (O(n^{1/3}(\log n{)}^{2/3}))$ for $n$ input bits. This is not polynomial in the bit length. Special input structure, small factors and preprocessing can make other algorithms preferable.

An ordered factorization of a positive integer $n>1$ is an ordered list of factors greater than one whose product is $n$. For example, $6$, $2\cdot 3$, and $3\cdot 2$ are the three ordered factorizations of $6$. Taking successive partial products gives a bijection with strictly increasing divisor chains from $1$ to $n$.

An integer factorization algorithm that iterates a simple map such as $x\mapsto x^2+c\mathrm{mod}n$ and searches for a nontrivial greatest common divisor of $n$ and the difference of two iterates. A collision modulo an unknown prime factor can reveal that factor before a collision modulo $n$. A cycle detection schedule such as Floyd's cycle-finding algorithm limits the number of stored iterates. Unsuccessful choices of seed or map can be retried.

A factor base is a finite set of small prime numbers over which selected auxiliary integers are completely factored. Some methods also record a sign coordinate for $-1$, which is not a prime number. A positive integer supported entirely on the chosen factor base gives an exponent vector; reducing that vector modulo two records which prime exponents are odd integers. The product is a square of a number precisely when every prime exponent is an even integer.

For the original toy $N=77$, use factor base $\{2,3,5\}$ and the two relationsThe residues have exponent vectors $(0,1,1)$ and $(2,1,1)$ in the order $(2,3,5)$. Adding the two vectors modulo two gives $(0,0,0)$, so multiplying the residues gives $15\cdot 60=900=30^2$. Consequentlyand $\gcd (X-Y,77)=7$ and $\gcd (X+Y,77)=11$. Neither individual residue was a square; combining the relations made all exponents even.

In a larger collection, choose relations $x_i^2\equiv r_i(\mathrm{mod}N)$ with positive residues $r_i={\prod }_{j=1}^B{p}_j^{e_{ji}}$. If a nonempty selection $I$ has an even sum in every exponent coordinate, setThen $X^2\equiv Y^2(\mathrm{mod}N)$. Finding such a selection is a linear dependence problem over the finite field ${\mathbb{F}}_2$: the indicator vector of the chosen relations belongs to the kernel of a linear map given by the parity matrix. This is why a problem about prime factors recruits linear algebra. The final congruence of squares may still be trivial, so another selection can be needed. ^[ref].

There is a tradeoff: a small factor base gives a smaller parity matrix, but fewer auxiliary integers factor completely over it. A larger factor base accepts more relations but makes the linear algebra larger. Negative auxiliary values need an additional sign coordinate, and a selected product needs even sign parity as well as even prime exponents. Pomerance's account explains this balance and the historical development of combining smooth relations; the toy example omits algorithm-specific sieving and running-time claims. ^[ref].

Relative to an ordered factor base $(p_1,\dots ,p_B)$, a positive integer $r={\prod }_j{p}_j^{e_j}$ has exponent vector $(e_1,\dots ,e_B)$. Multiplication of such integers adds their exponent vectors. Reducing every coordinate modulo two gives the parity vector used to find congruences of squares. The ordering and any sign coordinate must be used consistently across all rows.

The odd part of a positive integer $n$ is the unique odd positive integer $d$ obtained by repeatedly dividing $n$ by two. The process terminates because the positive integers decrease. If $2^{r}d=2^{s}e$ with $d,e$ odd, then $r>s$ would make $e$ even and $s>r$ would make $d$ even; hence $r=s$ and $d=e$. Two positive integers have the same odd part exactly when their ratio is an integral power of two. The odd positive integers therefore give representatives for the resulting equivalence classes.

A congruence of squares says that two integers $a,b$ have the same square modulo a positive integer $N$. Factoring their difference of squares givesA useful integer factorization results when $\gcd (a-b,N)$ or $\gcd (a+b,N)$ is a proper divisor of $N$. Divisibility of a product does not generally force divisibility of either factor by all of $N$: different prime factors of $N$ can divide different parts of that product.

For $N=77$, $20^2-13^2=231=3\cdot 77$. ThereforeThus $77=7\cdot 11$. The prime seven divides the difference, while eleven divides the sum. These computations already give a complete prime factorization because seven and eleven are prime numbers.

The Chinese remainder theorem explains the hidden sign choices. The four congruence classes solving $z^2\equiv 15(\mathrm{mod}77)$ have representatives $13,20,57,64$. Modulo seven each is $1$ or $-1$; modulo eleven each is $2$ or $-2$. Two independent sign choices produce four roots. The inputs thirteen and twenty agree modulo seven and disagree by sign modulo eleven, allowing their sum and difference to separate the two prime factors.

For distinct odd prime numbers $p,q$, $N=pq$ and $\gcd (b,N)=1$, a solution $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv b$ and $a\not\equiv -b$ modulo $N$ yields both proper factors by the two greatest common divisors. For a general composite integer, a proper divisor need not itself be prime; further factoring can remain. If $a\equiv b$ or $a\equiv -b(\mathrm{mod}N)$ in the coprime case, the two calculations return $N$ and one instead. A factor base helps generate relations, but does not ensure every resulting relation is useful.

For historical context, Pomerance describes Kraitchik's 1920s enhancement of the difference-of-squares approach associated with Fermat: seek a difference that is a multiple of $N$, rather than exactly $N$. His account also notes antecedents in Gauss and Seelhoff, so this is not an attribution of the whole idea to a single inventor. ^[ref].

For an odd integer $N>1$, a nontrivial square root of unity modulo $N$ is a residue $z$ with $z^2\equiv 1(\mathrm{mod}N)$ and $z\not\equiv \pm 1(\mathrm{mod}N)$. Then both $\gcd (z-1,N)$ and $\gcd (z+1,N)$ are proper divisors. For $N=77$, $z=34$ works: $34^2\equiv 1(\mathrm{mod}77)$, $\gcd (33,77)=11$, and $\gcd (35,77)=7$.

A congruence of squares with $\gcd (b,N)=1$ converts to this form by $z\equiv a{b}^{-1}(\mathrm{mod}N)$, using a modular multiplicative inverse. In the $a=20,b=13$ example, $13^{-1}\equiv 6(\mathrm{mod}77)$, so $z\equiv 20\cdot 6\equiv 43(\mathrm{mod}77)$. It yields $\gcd (42,77)=7$ and $\gcd (44,77)=11$. Nontriviality requires mixed sign choices across prime factors, which an odd prime number modulus cannot provide.