Congruence of squares
Encyclopedia
In number theory
, a congruence of squares is a congruence
commonly used in integer factorization
algorithms.
n, Fermat's factorization method
relies on finding numbers x, y satisfying the equality
We can then factor n = x2 − y2 = (x + y) (x − y). However, this algorithm is slow in practice because we need to search many such numbers, and only a few satisfy this strict equation. However, n can also be factored if we satisfy the weaker congruence of squares
.
From here we easily deduce
This means that n divides (x + y) (x − y). However we have required that x ≠ ±y (mod n), so n divides neither (x+y) nor (x−y) alone. Thus (x+y) and (x−y) each contain proper factors of n. Computing the greatest common divisor
s of (x + y, n) and of (x − y, n) will give us these factors; this can be done quickly using the Euclidean algorithm
.
Congruences of squares are extremely useful in integer factorization
algorithms. This congruence is extensively used in, for example, the quadratic sieve
, general number field sieve
, continued fraction factorization
, Dixon's factorization
, and so on. Conversely, because finding square roots modulo a composite number is probabilistic polynomial-time equivalent to factoring that number, any integer factorization algorithm can be used to efficiently identify a congruence of squares.
.
We can thus factor 35 as gcd(6 − 1, 35) = 5 and gcd(6 + 1, 35) = 7.
s to help us find congruences of squares more quickly. Instead of looking for
from the outset, we find many 
where the y have small prime factors, and try to multiply a few of these together to get a square on the right-hand side.
Number theory
Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
, a congruence of squares is a congruence
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
commonly used in integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms.
Derivation
Given a positive integerInteger
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
n, Fermat's factorization method
Fermat's factorization method
Fermat's factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:N = a^2 - b^2.\...
relies on finding numbers x, y satisfying the equality
Equation
An equation is a mathematical statement that asserts the equality of two expressions. In modern notation, this is written by placing the expressions on either side of an equals sign , for examplex + 3 = 5\,asserts that x+3 is equal to 5...
We can then factor n = x2 − y2 = (x + y) (x − y). However, this algorithm is slow in practice because we need to search many such numbers, and only a few satisfy this strict equation. However, n can also be factored if we satisfy the weaker congruence of squares
.From here we easily deduce
This means that n divides (x + y) (x − y). However we have required that x ≠ ±y (mod n), so n divides neither (x+y) nor (x−y) alone. Thus (x+y) and (x−y) each contain proper factors of n. Computing the greatest common divisor
Greatest common divisor
In mathematics, the greatest common divisor , also known as the greatest common factor , or highest common factor , of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.For example, the GCD of 8 and 12 is 4.This notion can be extended to...
s of (x + y, n) and of (x − y, n) will give us these factors; this can be done quickly using the Euclidean algorithm
Euclidean algorithm
In mathematics, the Euclidean algorithm is an efficient method for computing the greatest common divisor of two integers, also known as the greatest common factor or highest common factor...
.
Congruences of squares are extremely useful in integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
algorithms. This congruence is extensively used in, for example, the quadratic sieve
Quadratic sieve
The quadratic sieve algorithm is a modern integer factorization algorithm and, in practice, the second fastest method known . It is still the fastest for integers under 100 decimal digits or so, and is considerably simpler than the number field sieve...
, general number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
, continued fraction factorization
Continued fraction factorization
In number theory, the continued fraction factorization method is an integer factorization algorithm. It is a general-purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties. It was described by D. H. Lehmer and R. E. Powers in 1931,...
, Dixon's factorization
Dixon's factorization method
In number theory, Dixon's factorization method is a general-purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which a run-time bound not reliant on conjectures about the smoothness properties of values of a polynomial is...
, and so on. Conversely, because finding square roots modulo a composite number is probabilistic polynomial-time equivalent to factoring that number, any integer factorization algorithm can be used to efficiently identify a congruence of squares.
Example
We take n = 35. We find that.We can thus factor 35 as gcd(6 − 1, 35) = 5 and gcd(6 + 1, 35) = 7.
Further generalizations
We can also use factor baseFactor base
In computational number theory, the factor base is a mathematical tool commonly used in algorithms involving extensive sieving of potential factors.-Usage:...
s to help us find congruences of squares more quickly. Instead of looking for
from the outset, we find many where the y have small prime factors, and try to multiply a few of these together to get a square on the right-hand side.