= Integer factorization
{title2=$N=\prod_p p^{v_p(N)}$}
{wiki}
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\cdot11$ is a <semiprime>, whereas $231=3\cdot7\cdot11$ 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\equiv13^2\pmod{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. https://crypto.stanford.edu/pbc/notes/crypto/factoring.html[Ben Lynn, Factoring and Discrete Logarithms: congruent squares and the linear-algebra step]{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.
Back to article page
