qkqhxla1   1달 전

다 잘 나오는것 같은데 바로 틀렸다고 나오네요... 일단 mod처리에 이상있는것 같긴 합니다.....

zlzmsrhak   1달 전

19번째 줄에서 나머지 연산으로 처리된 값을 나눌 때는 매우 조심해야 하는데, 

12 = 2 (mod 10) 이지만, 6 != 1 (mod 10) 이기 때문입니다.


그래서 보통 나머지에서 나눗셈을 할 때는 ax = b (mod P)에서 a, b, P가 주어져 있을 때의 x값을 구하는 문제와 같은데,

P가 소수인 경우 x는 항상 존재하며, 구하는 방법에는 두 가지 정도가 있습니다.

1. P가 소수인 경우만 성립하는, 페르마 소정리에 의해 x = a^(P-2)일 때 성립합니다.

2. 확장 유클리드를 사용하면, ay + Pt = gcd(a, P) = 1인 (y, t) 쌍을 구할 수 있고, 양변에 b를 곱하면 a(by) = b (mod P)가 성립해서 x = by입니다.

qkqhxla1   1달 전

복잡하네요;;; 찾아가면서 천천히 읽어야 될 글인것 같습니다. 답 감사합니다

댓글을 작성하려면 로그인해야 합니다.