In
number theory
Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Mat ...
, a congruence of squares is a
congruence commonly used in
integer factorization algorithms.
Derivation
Given a positive
integer
An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
''n'',
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.
That difference is algebraically factorable as (a+b)(a-b); if neither factor equals one, ...
relies on finding numbers ''x'' and ''y'' satisfying the
equality
Equality may refer to:
Society
* Political equality, in which all members of a society are of equal standing
** Consociationalism, in which an ethnically, religiously, or linguistically divided state functions by cooperation of each group's elit ...
:
We can then factor ''n'' = ''x''
2 − ''y''
2 = (''x'' + ''y'')(''x'' − ''y''). This algorithm is slow in practice because we need to search many such numbers, and only a few satisfy the equation. However, ''n'' may also be factored if we can satisfy the weaker congruence of squares condition:
:
:
From here we easily deduce
:
:
This means that ''n''
divides
In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a multiple of m. An integer n is divisible or evenly divisible by ...
the product (''x'' + ''y'')(''x'' − ''y''). Thus (''x'' + ''y'') and (''x'' − ''y'') each contain factors of ''n'', but those factors can be trivial. In this case we need to find another ''x'' and ''y''. Computing the
greatest common divisor
In mathematics, the greatest common divisor (GCD) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. For two integers ''x'', ''y'', the greatest common divisor of ''x'' and ''y'' is ...
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 and are extensively used in, for example, the
quadratic sieve The quadratic sieve algorithm (QS) is an integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is consider ...
,
general number field sieve
In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form
:\exp\left( ...
,
continued fraction factorization In number theory, the continued fraction factorization method (CFRAC) 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 ...
, and
Dixon's factorization. Conversely, because finding
square roots
In mathematics, a square root of a number is a number such that ; in other words, a number whose ''square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
E ...
modulo a
composite number
A composite number is a positive integer that can be formed by multiplying two smaller positive integers. Equivalently, it is a positive integer that has at least one divisor other than 1 and itself. Every positive integer is composite, prime, ...
turns out to be probabilistic polynomial-time equivalent to factoring that number, any integer factorization algorithm can be used efficiently to identify a congruence of squares.
Further generalizations
It is also possible to use
factor base In computational number theory, a factor base is a small set of prime numbers commonly used as a mathematical tool in algorithms involving extensive sieving for potential factors of a given integer.
Usage in factoring algorithms
A factor base is a ...
s to help find congruences of squares more quickly. Instead of looking for
from the outset, we find many
where the ''y'' have small
prime
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
factors, and try to multiply a few of these together to get a
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90- degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length a ...
on the right-hand side.
Examples
Factorize 35
We take ''n'' = 35 and find that
:
.
We thus factor as
:
Factorize 1649
Using ''n'' = 1649, as an example of finding a congruence of squares built up from the products of non-squares (see
Dixon's factorization method In number theory, Dixon's factorization method (also Dixon's random squares method or Dixon's algorithm) is a general-purpose integer factorization algorithm; it is the prototypical factor base method. Unlike for other factor base methods, its run- ...
), first we obtain several congruences
:
:
:
of these, two have only small primes as factors
:
:
and a combination of these has an
even
Even may refer to:
General
* Even (given name), a Norwegian male personal name
* Even (surname)
* Even (people), an ethnic group from Siberia and Russian Far East
** Even language, a language spoken by the Evens
* Odd and Even, a solitaire game w ...
power of each small prime, and is therefore a square
:
yielding the congruence of squares
:
So using the values of 80 and 114 as our ''x'' and ''y'' gives factors
:
See also
*
Congruence relation
{{DEFAULTSORT:Congruence Of Squares
Equivalence (mathematics)
Integer factorization algorithms
Modular arithmetic
Squares in number theory