수론의 고급 알고리즘
BSGS
이산 로그 문제를 해결하기 위한 알고리즘으로, 주어진 a, b, p에 대해 a^n ≡ b (mod p)를 만족하는 최소의 양의 정수 n을 찾는 데 사용됩니다.
알고리즘 절차
이 문제는 두 가지 경우로 나눌 수 있습니다:
일반 BSGS
a와 p가 서로소(a⊥p)인 경우입니다.
이 경우 a는 역원을 가지며, BSGS는 이 성질을 이용해 제곱근 시간 알고리즘을 설계합니다.
a^n의 주기 길이는 φ ...
6월 22일 23:02에 게시됨