이산로그 계산기 (BSGS)

gˣ ≡ h (mod p)를 만족하는 지수 x입니다. 보통의 로그가 실수에서 「몇 제곱해야 이 값이 되는가」를 묻는 것과 같은 물음을, 나머지 연산 위에서 묻는 것입니다. 답이 정수 하나로 정해지지만 구하기는 훨씬 어렵습니다.

x를 x = i·m + j로 두 자리로 쪼개기 때문입니다(m = ⌈√n⌉, n은 g의 위수). gˣ ≡ h를 옮기면 g^j ≡ h·(g^(−m))^i가 되는데, 왼쪽은 i와 무관하고 오른쪽은 j와 무관합니다. 왼쪽 m개를 표에 담아 두고 오른쪽을 옮겨 가며 찾으면 n번 탐색이 약 2√n 걸음으로 줄어듭니다.

있습니다. g가 만드는 부분군 ⟨g⟩ 밖에 h가 있으면 답이 없습니다. 예를 들어 p = 7, g = 2는 {1, 2, 4}만 만들기 때문에 h = 3에는 아무리 곱해도 도달하지 못합니다. g가 원시근(위수가 p−1)이면 모든 h에 해가 있습니다.

그렇습니다. g의 위수가 n이면 gⁿ ≡ 1이므로 x, x+n, x+2n … 이 모두 답입니다. 이 계산기는 가장 작은 음이 아닌 x를 내고, 「모든 해」 줄에 주기를 함께 보입니다.

거듭제곱은 쉬운데 그 역이 어렵다는 비대칭이 디피–헬만 키 교환과 DSA 서명의 근거이기 때문입니다. gˣ mod p는 제곱을 반복해 금방 구하지만, 그 결과에서 x를 되찾는 것은 알려진 방법으로도 대략 √p 이상 걸립니다. 실제 암호가 쓰는 2048비트 p에서는 √p조차 감당할 수 없는 크기입니다.

이 계산기가 g의 위수를 p−1의 약수로 찾아 표 크기를 정하기 때문입니다. 합성수 법에서는 곱셈군의 구조가 달라지고 g가 역원을 갖지 않을 수도 있어, 여기서는 소수만 받습니다.

전송되지 않습니다. 모든 계산은 브라우저 안에서 이뤄지고, 입력값은 이 기기에만 남습니다.