곱셈 암호 이해하기!!
곱셈의 역원 (모듈러 역원) 일반적으로 곱셈의 역원이라 하면, 곱해서 1이 되는 수를 의미한다. 따라서 a의 곱셈의 역원은 1/a 이라고 할 수 있다. 하지만, 여기서 우리가 구하는 역원은 나머지 연산의 곱셈의 역원, 즉 모듈러 역원이다. 모듈러 역원은 a, b 두 수가 있을 때, a의 n 배수를 b와 나누면 그 나머지가 1인 수를 말한다. an (mod b) ≡1 a와 b가 최대공약수가 1인 서로소라면 이는 모듈러 역원이라고 할 수 있다. 유클리드는 싫지만 곱셈의 역원은 구해야해 ㅠ 만약 유클리드를 쓰지 않고 곱셈의 역원을 구하고 싶다면 .. 약간의 잔꾀를 써라. (노가다는 해야할 수도 있다. 그렇지만 급하면 무조건 가져가라) 만약 3의 곱셈의 역원을 구해야 한다면, 3 * x (m..
2024.03.24