Class note for met cs789
Let x2 = y2 in Ζ× , where n = pq . (x = ±y are the obvious two of the total of four square roots of y2 ). If we find a square root, x , such that x ≠ ±y (that is, x ≠ ±ymodn), then we can find the factorization of n.
Proof:Letx2=y2inΖ× thatis,x2≡y2modn.Thenx2−y2=knor n (x − y)(x + y) = kn and, therefore, (x − y)(x + y) is divisible by n . But x − y is not divisible by n , otherwise x − y = k1n or x ≡ y mod n and x + y is not divisible by n either, otherwise x + y = k2 n or x ≡ − y mod n . Since n = pq , either x − y is divisible by p and x + y is divisible by q or vice versa. Either way, x − y has a common divisor with n , which is either p or q , and we can use the Euclidean Algorithm to find p or q and, therefore, find the factorization of n.
Example: Consider Ζ× = {1,2,4,7,8,11,13,14} and the equation x 2 = 4 in Z × 15. The obvious solutions are ± 2 or 2 and 13. We can easily see that 72 = 4 and 7 ≠ ±2. Thus, (7 − 2)(7 + 2) = 15 ⋅ k ⇒ 5 ⋅ 9 = 15 ⋅ k , so we can say that the gcd(5,15) = 5 and the gcd(9,15) = 3. Thus, 5 and 3 are the factors of 15 .