In
number theory, a congruence of squares is a
congruence commonly used in
integer factorization algorithms.
Derivation
Given a positive
integer ''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 elite ...
:
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 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 divisors 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,
general number field sieve,
continued fraction factorization, and
Dixon's factorization. Conversely, because finding
square roots modulo a
composite number 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 bases 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 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), 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 wh ...
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
In abstract algebra, a congruence relation (or simply congruence) is an equivalence relation on an algebraic structure (such as a group, ring, or vector space) that is compatible with the structure in the sense that algebraic operations done wi ...
{{DEFAULTSORT:Congruence Of Squares
Equivalence (mathematics)
Integer factorization algorithms
Modular arithmetic
Squares in number theory