Notes - Square Roots Mod n

The following are notes from Introduction to Cryptography with Coding Theory.

• Suppose we are told that x² ≡ 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 ≡ 5³ ≡ 4 (mod 11). Since 4² ≡ 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 2³ ≡ 8 (mod 11). But 8² ≡ 9 ≡ -2 (mod 11), so we have found a square root of -2 rather than 2
• Example
• Composite Modulus square roots
• x² ≡ 71 (mod 77)
• x² ≡ 71 ≡ 1 (mod 7) and x² ≡ 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
• m₁ = 7, m₂ = 11, m = m₁m₂ = 77
• M₁ = m/m₁= 11, M₂ = m/m₂= 7
• M₁N₁ ≡ 1 (mod m₁₎ => 11 N₁ ≡ 1 (mod 7) => 4 N₁ ≡ 1 (mod 7) => N₁ ≡ 2 (mod 7)
• this will get us results of x ≡ +-15,+-29 (mod 77) 

Back to ToC