서론
시작하기에 앞서 이산 로그 문제(Discrete Logarithm Problem, 이하 DLP)가 무엇인지 알아봅시다.
소수 p와 Z/pZ의 원소 b, n이 주어질 때 다음 식을 만족하는 0 이상 p−1 미만의 정수 x를 찾는 문제가 DLP입니다. bx≡n (mod p) Baby-step Giant-step 알고리즘은 DLP을 O(√plgp)에 해결할 수 있는 알고리즘입니다. 다양한 DLP 알고리즘 중 완전탐색을 제외한 가장 간단한 알고리즘에 해당합니다.
이 글에서는 Baby-step Giant-step 알고리즘이 DLP를 어떻게 해결하는지, 왜 O(√plgp)라는 시간복잡도가 보장되는지에 관해 알아보겠습니다.
Baby-step Giant-step Algorithm
이 알고리즘은다음과 같은 순서로 진행됩니다.
- 1 이상 ⌈√p⌉인 모든 정수 c에 대해 bc mod p를 집합 S에 삽입한다.
- 1 이상 ⌈√p⌉인 모든 정수 k에 대해 bk⌈√p⌉을 계산한다.
- 오일러 소정리에 따라 b−k⌈√p⌉를 구하여 bx−k⌈√p⌉를 계산하고, 이 값을 r이라 하자.
- S에 r≡bc (mod p)을 만족하는 bc mod p가 존재한다면 x≡k⌈√p⌉+c (mod p−1)임을 알 수 있습니다.
타당성 증명
bx−k⌈√p⌉≡bc (mod p)라면, 합동식의 성질에 따라 양변에 bk⌈√p⌉를 곱하여 bx≡bk⌈√p⌉+c (mod p)임을 알 수 있습니다.
이때 0 이상 p−1 미만의 두 정수 α, β에 대하여 bα≡bβ (mod p)라면 α=β이므로 x≡k⌈√p⌉+c (mod p−1)입니다.
효율성 증명
ab mod p를 계산하는 것은 O(lgb)에 가능합니다. 또한, 잘 구현된 집합 구현체는 어떤 원소가 포함되어있는지 O(lgb)에 판별하는 것이 가능합니다.
따라서 (1.)은 ⌈√p⌉번 O(lgb)의 연산을 수행하므로, O(√plgb)의 시간복잡도를 갖습니다.
(2.), (3.), (4.)에서 모듈로 역원을 구하는 과정이나 거듭제곱을 하는 모든 과정은 O(lgb)에 가능하고, 총 ⌈√p⌉번 이 과정을 반복하므로 역시 O(√plgb)에 동작합니다.
따라서 전체 시간복잡도는 O(√plgb)가 됩니다.
결론
Baby-step Giant-step 알고리즘을 활용해 DLP를 해결하는 방법과, 그 타당성 및 효율성의 증명에 관해 이야기해봤습니다. 본 글에서는 Z/pZ 상에서의 DLP만을 다루었지만, 일반적으로 다양한 군에서 DLP와 Baby-step Giant-step 알고리즘을 적용할 수도 있습니다.
더 효율적인 DLP 알고리즘에 대해 알아보고 싶으시다면, 다음 키워드들을 추천드립니다.
- Pollard-rho 알고리즘
- Pohlig-Hellman 알고리즘