안녕하세요.
A, B가 자연수이고, A가 B의 배수일 때,
(A/B) mod p는 어떻게 구하나요? (mod 는 나머지 연산을 나타냅니다. )
일단, A/B 를 바로 구하기에는 A 값이 무지막지하게 큽니다.
A 가 p 로 나눈 나머지를 쉽게 구할 수 있는 수들에 대한 합과 곱으로 이루어진 식으로 주어지기 때문에,
A mod p 역시 쉽게 구할 수 있습니다.
B, p 가 서로소라면, B의 p에 대한 승산역원 C 를 구해서,
((A mod p) * (C mod p)) mod p 을 구하면, 처음에 구하고자 했던 값이 나오는데요.
문제는 B와 p 가 서로소가 아닐 때는 승산 역원값을 구할 수 없어서, 저 식을 적용할 수가 없는데요.
이럴 경우는 어떤 식으로 풀어야될까요?
글쓰기