Quoted By:
Example 3.37. We factor N = 914387 using the procedure described in
Table 3.4. We first search for integers a with the property that a2 mod N
is a product of small primes. For this example, we ask that each a2 mod N be
a product of primes in the set {2, 3, 5, 7, 11}. Ignoring for now the question of
how to find such a, we observe that
18692 ? 750000 (mod 914387) and 750000 = 24 · 3 · 56,
19092 ? 901120 (mod 914387) and 901120 = 214 · 5 · 11,
33872 ? 499125 (mod 914387) and 499125 = 3 · 53 · 113.
None of the numbers on the right is a square, but if we multiply them together,
then we do get a square. Thus
18692 · 19092 · 33872 ? 750000 · 901120 · 499125 (mod 914387)
? (24 · 3 · 56)(214 · 5 · 11)(3 · 53 · 113) (mod 914387)
144 3. Integer Factorization and RSA
= (29 · 3 · 55 · 112)
2
= 5808000002
? 1642552 (mod 914387).
We further note that 1869 · 1909 · 3387 ? 9835 (mod 914387), so we compute
gcd(914387, 9835 ? 164255) = gcd(914387, 154420) = 1103.
Hooray! We have factored 914387 = 1103 · 829.
