Computer Security and Cryptography

13.6 RANDOM FACTORIZATION

We assume that N is both composite and odd. Several factorization methods are based on a simple idea attributed to Dixon [1981]; if integers x and y can be found so that x² = y² (modulo N), then (x − y)(x + y) = 0 (modulo N). If x ≠ ±y (modulo N), then either gcd{N, x − y} or gcd{N, x + y} is a nontrivial factor of n. In fact, the factorizations N = ab are in 1 − 1 correspondence with pairs of integers s, t such that 0 = (t² − s²) (modulo N) in the sense that and [Koblitz, 1987, Proposition V.3.1].

Example 13.8

37² = 7² (modulo 55).

To find pairs (x, y), random values of s in are chosen, and u = s² (modulo N) is computed. If u is a perfect square (modulo N), say u = t² (modulo N), and both 0 ≠ (s − t) (modulo N) and 0 ≠ (s + t) (modulo N), then we find a factor of N.

For example, if N = 55 and s = 13, then

leading to the factorization

Of course, if we have chosen ...