모듈러 역원 계산기

정수 a의 모듈러스 m에 대한 곱셈 역원은 a와 곱한 뒤 m으로 나눈 나머지가 1이 되는 정수 x입니다. 합동식으로는 a 곱하기 x가 모듈러스 m에서 1과 합동이라는 뜻입니다. 이 계산기는 확장 유클리드 알고리즘으로 가장 작은 음이 아닌 역원을 구하고 곱셈 검산을 표시합니다. 모듈러스는 1보다 큰 정수여야 합니다. 역원은 a와 m이 서로소, 즉 최대공약수가 1일 때만 존재합니다. 더 큰 공약수를 공유하면 a가 포함된 모든 곱은 모듈러스 m에서도 그 인수로 나누어떨어져 나머지 1을 만들 수 없습니다. 예를 들어 6은 모듈러스 15에서 역원이 없습니다. 최대공약수가 3이기 때문입니다. 반면 3은 모듈러스 11에서 역원이 4입니다. 3 곱하기 4는 12이고, 11로 나눈 나머지가 1입니다. 확장 유클리드 알고리즘은 최대공약수뿐 아니라 ax 더하기 my가 최대공약수가 되도록 하는 계수 x와 y도 구합니다. 그 공약수가 1이면 x를 모듈러스 m으로 정규화한 값이 역원입니다. x가 음수이면 m을 충분히 더해 합동류를 바꾸지 않고 0부터 m 빼기 1까지의 표준 범위로 옮길 수 있습니다. 모듈러 역원은 모듈러 연산에서 나눗셈을 대신합니다. 서로 다른 정수가 같은 나머지를 나타내므로 잉여류에 일반 나눗셈을 그대로 적용할 수는 없습니다. 모듈러스 m에서 a로 나눈다는 것은 a의 역원이 존재할 때 그 역원을 곱한다는 뜻입니다. 이 방법은 일차 합동식 풀이, 모듈러 분수 정리, 중국인의 나머지 정리 적용, 여러 정수론 알고리즘 유도에 핵심적입니다. 암호학에서도 모듈러 역원을 널리 사용합니다. RSA 키 생성은 오일러 피 함수와 관련된 값을 모듈러스로 하여 지수의 역원을 구하며, 타원곡선 계산은 유한체에서 점 연산 공식을 계산할 때 역원을 사용합니다. 부호 이론, 체크섬, 의사 난수 생성기, 컴퓨터 대수도 효율적인 역원 계산에 의존합니다. 실제 암호 구현은 브라우저의 일반 숫자 연산 대신 신중하게 설계된 큰 정수 및 상수 시간 루틴을 사용하지만, 기반 정수론은 같습니다. 역원은 일반 정수로서가 아니라 모듈러스 m에서 유일합니다. 4가 모듈러스 11에서 3의 역원이라면 15, 음의 7, 그리고 4와 11의 배수만큼 차이 나는 모든 수는 같은 역원 잉여류를 나타냅니다. 계산기는 비교와 재사용이 쉬운 가장 작은 음이 아닌 대표값 4를 표시합니다. 검산하려면 원래 정수와 표시된 역원을 곱한 다음 모듈러스로 나누어 나머지가 1인지 확인하세요. 나머지는 항상 표준 범위로 정규화할 수 있으므로 음수 입력에도 같은 규칙이 적용됩니다. 역원이 없다고 표시되면 최대공약수를 별도로 구해 보세요. 1보다 큰 값이면 역원이 존재하지 않는 이유를 확인할 수 있습니다.