Editing Difference of two squares (section)

===Factorization of integers===

Several algorithms in number theory and cryptography use differences of squares to find factors of integers and detect composite numbers. A simple example is the [[Fermat factorization method]], which considers the sequence of numbers <math>x_i:=a_i^2-N</math>, for <math>a_i:=\left\lceil \sqrt{N}\right\rceil+i</math>. If one of the <math>x_i</math> equals a perfect square <math>b^2</math>, then <math>N=a_i^2-b^2=(a_i+b)(a_i-b)</math> is a (potentially non-trivial) factorization of <math>N</math>.

This trick can be generalized as follows. If <math>a^2\equiv b^2</math> mod <math>N</math> and <math>a\not\equiv \pm b</math> mod <math>N</math>, then <math>N</math> is composite with non-trivial factors <math>\gcd(a-b,N)</math> and <math>\gcd(a+b,N)</math>. This forms the basis of several factorization algorithms (such as the [[quadratic sieve]]) and can be combined with the [[Fermat primality test]] to give the stronger [[Miller–Rabin primality test]].