Past exam of the mathematics course of the University of Cambridge / 2009 / ii / Paper 2 / 4H (Coding and Cryptography)

The supplied congruence is a congruence of squares, since $25=5^2$. HenceA nontrivial square root modulo a product of two odd primes may agree with $+5$ modulo one prime and $-5$ modulo the other. Taking greatest common divisors separates these factors. The Euclidean algorithm givesFor example the successive remainders for the first computation are $1072,737,335,67,0$; for the second they are $1062,767,295,177,118,59,0$. ThereforeBoth numbers are prime by trial division by primes at most their square roots. More generally, given $a^2\equiv b^2(\mathrm{mod}N)$ with $a\not\equiv \pm b(\mathrm{mod}N)$, computing $\gcd (N,a-b)$ often produces a proper factor. The method requires no prior knowledge of which prime gives which sign, and is the basic factor-extraction step in congruence-of-squares algorithms.