아기걸음 거인걸음

아기걸음 거인걸음(, 약자 BSGS)은 이산 로그 알고리즘의 하나이다.

 아이디어 
이산 로그

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

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

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

에서 처음 겹치면, 이산 로그는 이다.

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

 정의 
아기걸음 거인걸음은 다음과 같은 알고리즘이다.
 입력: 크기가 인 유한 순환군 의 생성 원소 와 임의의 원소 
 출력: 를 밑으로 하는 의 이산 로그 
 (초기화) 로 놓는다.
 (아기 걸음) 각 에 대하여, 를 계산하고 를 어떤 표에 저장한다.
 를 계산하고 로 놓는다.
 (거인 걸음) 각 에 대하여,
 만약 인 가 존재한다면, 를 반환한다.
 로 놓는다.

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

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

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

 참고 문헌 

 외부 링크 



분류:수론 알고리즘