모듈러 역원

시간 제한1초메모리 제한128 MB

요약

x와 m이 주어질 때, x*n을 m으로 나눈 나머지가 1이 되는 0 < n < m인 n을 찾고, 없으면 없다고 출력한다.

문제

많은 암호학 응용에서 모듈러 역원(modular inverse)은 핵심적인 개념이다. 이 문제에서는 주어진 수의 모듈러 역원을 구한다.

정수 $x$ 와 $m$ 이 $0 < x < m$ 을 만족한다고 하자. $x$ 의 모듈러 역원은 $x \times n$ 을 $m$ 으로 나눈 나머지가 $1$ 이 되는 유일한 정수 $n$ ( $0 < n < m$ )이다.

예를 들어 $4 \times 13 = 52 = 17 \times 3 + 1$ 이므로 $52$ 를 $17$ 로 나눈 나머지는 $1$ 이고, 따라서 $13$ 은 $17$ 을 법으로 하는 $4$ 의 역원이다.

첫째 줄에 정수 $x$ 가, 둘째 줄에 정수 $m$ 이 주어진다.

$x$ 의 $m$ 에 대한 모듈러 역원 $n$ 을 출력한다. 그러한 정수 $n$ 이 존재하지 않으면 No such integer exists.를 출력한다.