- Suppose we are told that x2 ≡ 71 (mod 77) has a solution
- How do we find one solution/all solutions?
- Proposition
- if y has a square root mod p, then teh square roots of y mod p are +-x.
- If y has no square root mod p, then -y has a square root mod p, and the square roots of -y are +-x
- Example
- Lets find the square roots of 5 mod 11. Since (P+1)/4 = 3, we compute x ≡ 53 ≡ 4 (mod 11). Since 42 ≡ 5 (mod 11), the square roots of 5 mod 11 are
+-4 or 5,7 mod 11 - Let's try to find the square root of 2 mod 11. Since (p+1)/4 = 3, we compute 23 ≡ 8 (mod 11). But 82 ≡ 9 ≡ -2 (mod 11), so we have found a square root of -2 rather than 2
- Example
- Composite Modulus square roots
- x2 ≡ 71 (mod 77)
- x2 ≡ 71 ≡ 1 (mod 7) and x2 ≡ 71 ≡ 5 (mod 11)
- x ≡ +-1 (mod 7) and x ≡ +-4 (mod 11)
- The chinese remainder theorem tells us that a congruence mod 7 and a congruence mod 11 can be recombined into a congruence mod 77
- m1 = 7, m2 = 11, m = m1m2 = 77
- M1 = m/m1= 11, M2 = m/m2= 7
- M1N1 ≡ 1 (mod m1) => 11 N1 ≡ 1 (mod 7) => 4 N1 ≡ 1 (mod 7) => N1 ≡ 2 (mod 7)
- this will get us results of x ≡ +-15,+-29 (mod 77)
Tuesday, October 22, 2013
Notes - Square Roots Mod n
The following are notes from Introduction to Cryptography with Coding Theory.
Labels:
Cryptography,
Math,
Notes
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment