For each part, use the data provided to find values of a and b satisfying a2 ≡ b2 (mod N), and then compute gcd(N, a − b) in order to find a nontrivial factor of N, as we did in Examples 3.37 and 3.38. (c) N = 198103 11892 ≡ 27000 (mod 198103) and 27000 = 23 · 33 · 53 16052 ≡ 686 (mod 198103) and 686 = 2 · 73 23782 ≡ 108000 (mod 198103) and 108000 = 25 · 33 · 53 28152 ≡ 105 (mod 198103) and 105 = 3 · 5 · 7
For each part, use the data provided to find values of a and b satisfying a2 ≡ b2 (mod N), and then compute gcd(N, a − b) in order to find a nontrivial factor of N, as we did in Examples 3.37 and 3.38.
(c) N = 198103
11892 ≡ 27000 (mod 198103) and 27000 = 23 · 33 · 53
16052 ≡ 686 (mod 198103) and 686 = 2 · 73
23782 ≡ 108000 (mod 198103) and 108000 = 25 · 33 · 53
28152 ≡ 105 (mod 198103) and 105 = 3 · 5 · 7
Here is an example of a similar problem solved in the book:
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)
= (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
Trending now
This is a popular solution!
Step by step
Solved in 3 steps with 1 images
