Such a relationship carries information useful in trying to factor the integer n: finding a congruence of squares modulo n is something sought after in integer factorization. There follows from it that
This means that n divides (x+y)(x−y) but not (x+y) or (x−y) alone, so both (x+y) and(x−y) contain factors of n. A simple gcd operation will extract a factor in most cases. The difficulty lies in finding x and y. This, incidentally, is what both the quadratic sieve and number field sieve do: set up a congruence of squares modulo n. This approach to factoring also shows that the problem of factoring can be reduced to the problem of finding square roots modulo n.
A case where a congruence of squares will not yield a factor is when only one of the pairs (x+y) or (x-y) shares a factor with n. This implies that the pair sharing factors with n is either equal to n or a multiple of n. The gcd of that pair and n thus will be n, and the gcd of n and the other pair is 1. In order for the congruence of squares to extract any factors, both pairs (x+y) and (x-y) must each share at least one factor with n.
Here is an example. Say n = 35. A perfect square close to 35 is 36, and, conveniently, 36 ≡ 1 (mod 35). Now 1 is also a perfect square. Thus we have our congruence:
with gcd(6 + 1, 35) = 7 and gcd(6 - 1, 35) = 5. These are the two non-trivial factors of 35.
The algorithm attempts to set up a congruence of squaresmodulo n (the integer to be factorized), which often leads to a factorization of n.
The algorithm works in two phases: the data collection phase, where it collects information that may lead to a congruence of squares; and the data processing phase, where it puts all the data it has collected into a matrix and solves it to obtain a congruence of squares.
The naïve approach to finding a congruence of squares is to pick a random number, square it, and hope the least non-negative remainder modulo n is a perfect square (in the integers).
Feeds |
Contact