온라인 이산 로그 솔버

이산 로그 문제란?

이산 로그 문제는 주어진 g, h, p에 대해 g^x ≡ h (mod p)를 만족하는 지수 x를 찾는 문제입니다. 예를 들어 2^3 = 8이므로 2^3 mod 13 = 8이 되어 x=3이 해가 됩니다.

이 도구의 작동 방식

이 도구는 x=0부터 시작하여 value를 1로 두고, 각 단계에서 value = (value * g) mod p를 계산하며 h와 비교합니다. p가 최대 1,000,000이므로 모든 가능한 지수를 빠짐없이 확인하는 완전 탐색(exhaustive search)을 수행합니다. 이는 교육용으로 설계된 O(p) 알고리즘으로, 실제 암호 해독에 사용되는 고속 알고리즘(예: baby-step giant-step)과는 다릅니다.

입력 제한 및 정규화

g, h, p는 정수여야 하며, p는 2에서 1,000,000 사이여야 합니다. h가 음수이거나 p보다 큰 경우에는 모듈로 p 연산을 통해 나머지 값으로 변환되어 비교됩니다. p가 소수가 아니어도 동작하지만, g와 p가 서로소가 아닌 경우 순환이 짧아질 수 있습니다. 그래도 완전 탐색이므로 해가 존재하면 가장 작은 x를 찾아냅니다.

실제 사용 예시

예를 들어 g=3, h=4, p=7을 입력하면, 3^0=1, 3^1=3, 3^2=2, 3^3=6, 3^4=4이므로 x=4가 반환됩니다. 직접 계산하여 결과를 검증할 수 있습니다.

제한 사항

이 도구는 순수한 교육용 계산기로, 실제 암호화폐 개인키 복구나 보안 평가를 위한 것이 아닙니다. p가 1,000,000을 초과하면 계산이 불가능하며, JavaScript 숫자 연산을 사용하므로 매우 큰 수는 다룰 수 없습니다. 중요한 계산에는 독립적으로 검증하세요.

자주 묻는 질문

Q1: p가 소수가 아니어도 되나요?

네, p는 소수일 필요가 없습니다. 다만 g와 p가 서로소가 아닌 경우에는 생성되는 수열이 짧은 주기를 가질 수 있습니다. 그래도 도구는 p번까지 모든 지수를 검사하므로 해가 존재하면 가장 작은 x를 찾습니다.

Q2: h가 음수이면 어떻게 되나요?

h는 자동으로 모듈로 p로 정규화됩니다. 예를 들어 p=13, h=-5라면 -5 mod 13 = 8로 처리되어 2^3 mod 13 = 8과 같은 결과를 얻습니다.

Q3: 결과가 ‘해 없음’으로 나오는 경우는 언제인가요?

g와 p가 서로소가 아닐 때, h가 생성되는 수열에 포함되지 않으면 해가 없을 수 있습니다. 예를 들어 g=2, p=4일 때 2^x mod 4는 0 또는 2만 나오므로 h=1이면 해가 없습니다. 이 경우 도구는 ‘해 없음’을 표시합니다.

확인 사항

• 입력값이 정수인지 확인하세요.
• p가 2 이상 1,000,000 이하인지 확인하세요.
• 결과를 직접 계산하여 검증하세요.
• 이 도구는 로컬에서 실행되며 서버로 데이터를 전송하지 않습니다.