아기걸음 거인걸음

아기걸음 거인걸음(영어: baby-step giant-step, 약자 BSGS)은 이산 로그 알고리즘의 하나이다.

아이디어

이산 로그

$\log _{g}h$

를 계산하는 아기걸음 거인걸음의 아이디어는 적절한 (밑의 차수에 의존하는) 양의 정수 $r$를 고른 뒤, 먼저 “아기 걸음”

$1,g,g^{2},\dots ,g^{r-1}$

을 계산하고, 아기 걸음과 겹칠 때까지 “거인 걸음”

$h,hg^{-r},hg^{-2r},\dots$

을 계산하는 것이다. 만약 아기와 거인의 걸음이

$g^{i}=hg^{-jr}$

에서 처음 겹치면, 이산 로그는 $i+jr$이다.

나눗셈 정리에 따라 모든 정수는 $i+jr$의 꼴로 나타낼 수 있으므로 ($0\leq i<r$), 아기걸음 거인걸음은 항상 종료한다. 아기걸음 거인걸음은 ($h$와 겹칠 때까지 $1,g,g^{2},\dots$를 계산하는) 소박한 이산 로그 알고리즘보다 훨씬 적은 시간을 사용한다. $r$를 줄이면 사용하는 공간이 줄어들고, 대신 실행 시간이 늘어난다. 이는 공간-시간 교환의 한 예이다.

정의

아기걸음 거인걸음은 다음과 같은 알고리즘이다.

• 입력: 크기가 $n$인 유한 순환군 $G$의 생성 원소 $g\in G$와 임의의 원소 $h\in G$
• 출력: $g$를 밑으로 하는 $h$의 이산 로그 $\log _{g}h\in \mathbb {Z} /n$

1. (초기화) $r\leftarrow \lceil {\sqrt {n}}\rceil$로 놓는다.
2. (아기 걸음) 각 $j=0,1,\dots ,r-1$에 대하여, $g^{j}$를 계산하고 $(j,g^{j})$를 어떤 표에 저장한다.
3. $g^{-r}$를 계산하고 $k\leftarrow h$로 놓는다.
4. (거인 걸음) 각 $i=0,1,2,\dots$에 대하여,
   1. 만약 $k=g^{j}$인 $j=0,1,\dots ,r-1$가 존재한다면, $i+jr$를 반환한다.
   2. $k\leftarrow kg^{-r}$로 놓는다.

복잡도

아기걸음 거인걸음의 시간 복잡도는 $O({\sqrt {n}})$, 공간 복잡도는 마찬가지로 $O({\sqrt {n}})$이다. 특히, 아기걸음 거인걸음은 (시간 복잡도가 $O(n)$, 공간 복잡도가 $O(1)$인) 소박한 알고리즘보다 훨씬 빠르다.

아기 걸음 수 $r$를 다르게 설정하는 경우, 시간 복잡도는 $O(r+n/r)$, 공간 복잡도는 $O(r)$이다. 즉, $r$를 줄이면 공간 복잡도가 줄어드는 대신 시간 복잡도가 늘어난다. 하지만 시간 복잡도와 공간 복잡도의 곱은 항상 $\Omega (n)$이다.

역사

대니얼 섕크스(영어: Daniel Shanks, 1917~1996)가 허수 이차 수체의 유수를 계산하기 위해 정의하였으며, 《1969년 수론 연구회》(뉴욕 주립 대학교 스토니브룩, 1969년 7월 7일 ~ 8월 1일)에서 처음 발표하였다.

외부 링크

• 류대식 (2019년 3월 19일). “샹크스 알고리즘 증명”. 《생새우초밥집》. 
• Sutherland, Andrew V. (2021). “Lecture 9: generic algorithms for the discrete logarithm problem” (영어) (강의록). 《MIT OpenCourseWare》. Massachusetts Institute of Technology.