[정수론](11)[연속제곱법, x^k 합동 구하기]

 

연속제곱법: a^k (mod m) 빨리 계산하기

1. k를 2의 거듭제곱의 합으로 표현
   k = u0*A0 + u1*A1 +...+ ur*Ar
2. 각각의 제곱들을 mod 연산하기
   a ≡ A0 (mod m)
   a^2 ≡ A1 (mod m)
   a^4 ≡ A2 (mod m)
   a^8 ≡ A3 (mod m)
   ...
   a^r ≡ Ar (mod m)
3. 구한 A들을 가지고 연산하기
   A0^u0*A1^u1*...*Ar^ur ≡ a^(u02^0 + u12^1 + ... ur2^r) ≡ a^k (mod m)

 

법 m에 대한 k제곱근 구하기

x^k ≡ b (mod m)에서
gcd(b, m)=1, gcd(k, ϕ(m)) = 1이라면

1. ϕ(m) 계산하기
2. ku-ϕ(m)v = 1인 양의 정수 u, v를 구함
3. b^u를 연속제곱법으로 계산
4. x ≡ b^u (mod m)

• 증명
  x^(ku) ≡ x^(ϕ(m)v + 1) ≡ b^u (mod m)
  오일러 정리에 의해 x*1^v ≡ x ≡ b^u (mod m)