In the rational Sieve method why does n = gcd(a-b,n)×gcd(a+b,n) exactly

number theoryprime factorizationsieve-theory

As a quick notation explanation of the basic rational sieve method, a set of primes $P$ that are coprime to a number $n$ tested for primality are chosen randomly as follows(from wikipedia):

Suppose we are trying to factor the composite number $n$. We choose a bound $B$, and identify the ''factor base'' (which we will call $P$), the set of all primes less than or equal to $B$. Next, we search for positive integers $z$ such that both $z$ and $z+n$ are $B$-smooth number — i.e. all of their prime factors are in $P$. We can therefore write, for suitable exponents $a_k$,
$$z=\prod_{p_i\in P} p_i^{a_i}$$
and likewise, for suitable $b_k$, we have
$$z+n=\prod_{p_i\in P} p_i^{b_i}$$.
But $z$ and $z+n$ are congruent modulo $n$, and so each such integer $z$ that we find yields a multiplicative relation Modular arithmetic|(mod $n$) among the elements of $P$, i.e.
$$\prod_{p_i\in P} p_i^{a_i} \equiv \prod_{p_i\in P} p_i^{b_i} \pmod n$$
(where the $a_i$ and $b_i$ are nonnegative integers.)
When we have generated enough of these relations (it's generally sufficient that the number of relations be a few more than the size of $P$), we can use the methods of linear algebra to multiply together these various relations in such a way that the exponents of the primes are all even. This will give us a congruence of squares of the form $a^2\equiv b^2 \pmod n$, which can be turned into a factorization of $n$, $n$ = Greatest common divisor $\mathrm{gcd}(a-b,n)\times \mathrm{gcd}(a+b,n)$. This factorization might turn out to be trivial (i.e. $n=n\times1$), in which case we have to try again with a different combination of relations; but with luck we will get a nontrivial pair of factors of $n$, and the algorithm will terminate.

Why does $n = \mathrm{gcd}(a-b,n)\times \mathrm{gcd}(a+b,n)$ rather than just divide $(a-b)(a+b)$ according to Euclid's lemma? Couldn't primes be chosen such that $(a-b)$ and $(a+b)$ contain duplications of factors from $n$, for instance $1$ in each of a single prime contained in $n$?

Best Answer

Expanding $\,(n,a\!-\!b)(n,a\!+\!b) = n\,(\overbrace{\color{#c00}{n,a\!-\!b,a\!+\!b},(a^2\!-\!b^2)/n}^{\large =\ 1\ \rm by\ below}) = n$

since $\,p\mid \color{#c00}{n,a\!-\!b,a\!+\!b}\,\Rightarrow\, p\mid n,2a,2b,\,$ contra $\,n\,$ coprime to $\,2,a,b\,$ (wlog)

Remark $ $ The factorization $\,n = (n,a\!-\!b)(n,a\!+\!b)\,$ is proper when $\,n\nmid a\pm b,\,$ so then $\!\bmod n\!:\ b^2\equiv a^2\,$ but $\,b\not\equiv \pm a,\,$ i.e. $\,b\,$ is a nontrivial square root of $\,a^2,\,$ so the quadratic $\,x^2-a^2$, has more than $\:\!2\:\!$ roots (assuming wlog $\,n\,$ is odd).

Generally we can quickly split $\,n>1\,$ into two nontrivial factors given any nonzero polynomial with more roots $\!\bmod n\,$ than its degree - see here.

Related Question