이차잉여·르장드르 기호 계산기

x² ≡ a (mod n)을 만족하는 x가 있으면 a를 법 n의 이차잉여라고 합니다. 쉽게 말해 그 법 안에서 「제곱수」인 값입니다. 홀수 소수 p에서는 1부터 p−1까지 가운데 정확히 절반이 이차잉여입니다.

1²과 (p−1)², 2²과 (p−2)²처럼 둘씩 짝지어 같은 값이 나오기 때문입니다. p−1개의 수를 제곱하면 서로 다른 값이 (p−1)/2가지만 나옵니다. 그래서 제곱근이 있으면 언제나 두 개이고, 그 둘을 더하면 p가 됩니다.

르장드르 기호는 아래가 홀수 소수일 때만 정의되고, 야코비 기호는 아래가 임의의 양의 홀수일 때로 넓힌 것입니다. 아래가 소수면 두 값이 같습니다. 야코비 기호는 소인수분해 없이 이차 상호법칙만으로 빠르게 계산되지만, 대신 「1이면 제곱수」라는 뜻을 잃습니다.

법이 소수일 때만 그렇습니다. 합성수에서는 −1이 두 번 곱해져 1이 되는 일이 있어서, 기호가 1인데도 제곱수가 아닐 수 있습니다. (2/15) = (2/3)(2/5) = (−1)(−1) = 1이지만 2는 법 15에서 어떤 수의 제곱도 아닙니다. 다만 기호가 −1이면 확실히 제곱수가 아닙니다.

a^((p−1)/2) mod p를 계산해 1이면 이차잉여, p−1이면 아니라고 판정하는 방법입니다. 뜻은 분명하지만 거듭제곱을 해야 합니다. 이차 상호법칙으로 계산하는 야코비 기호는 유클리드 호제법처럼 위아래를 뒤집어 가며 부호만 추적해 훨씬 빠릅니다.

p를 4로 나눈 나머지가 3이면 a^((p+1)/4)가 곧 제곱근이라 한 줄로 끝납니다. 나머지가 1이면 그런 지름길이 없어 톤엘리–섕크스 알고리즘을 씁니다. 이차잉여가 아닌 수를 하나 찾아, 그것의 거듭제곱으로 2의 거듭제곱 부분을 한 겹씩 벗겨 내는 방법입니다.

암호학과 정수론 곳곳에 쓰입니다. 타원곡선 위의 점을 찾을 때, 라빈 암호와 이차 체 소인수분해에서, 그리고 솔로베이–스트라센 소수 판정법에서 야코비 기호가 핵심 도구입니다.

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