About CarmichaelNumbers ¶
암호 알고리즘 중에는 큰 소수를 활용하는 것도 있다. 하지만 어떤 큰 수가 소수인지를 판단하는 것은 그리 쉽지 않다.
페르마 테스트와 같이 빠른 속도로 매우 정확하게 소수 여부를 판단할 수 있는 확률적 소수 테스트 방법이라는 것이 있다. 소수 여부를 판단해야 할 정수 n이 주어졌을 때 a는 2이상 n-1이하의 난수라고 하자. 그러면 다음과 같은 식이 성립하면 n은 소수일 가능성이 있다.
a^n mod n = a
어떤 정수가 이러한 페르마 테스트를 여러 번 통과하면 그 정수는 소수일 가능성이 높다고 할 수 있다. 하지만 안 좋은 소식도 있다. 합성수(소수가 아닌 수) 중에는 그 수보다 작은 모든 정수에 대해 이 페르마 테스트를 통과하는 것도 있다. 이런 수를 카마이클 수라고 부른다.
주어진 정수가 카마이클 수인지 테스트하기 위한 프로그램을 만들어라.
페르마 테스트와 같이 빠른 속도로 매우 정확하게 소수 여부를 판단할 수 있는 확률적 소수 테스트 방법이라는 것이 있다. 소수 여부를 판단해야 할 정수 n이 주어졌을 때 a는 2이상 n-1이하의 난수라고 하자. 그러면 다음과 같은 식이 성립하면 n은 소수일 가능성이 있다.
Input ¶
입력은 여러 줄로 구성되며 각 줄에는 작은 양의 정수 n(2
Output ¶
입력된 각 수에 대해 아래에 있는 출력 예에 나와있는 식으로 그 수가 카마이클 수인지 아닌지를 판단한 결과를 출력하라.
Sample Input ¶
~cpp 1729 17 561 1109 431 0
Sample Output ¶
~cpp The number 1729 is a Carmichael number. 17 is normal. The number 561 is a Carmichael number. 1109 is normal. 431 is normal.
풀이 ¶
| 작성자 | 사용언어 | 개발시간 | 코드 |
| 문보창 | C++ | 3h 30m | CarmichaelNumbers/문보창 |
| 조현태 | C | . | CarmichaelNumbers/조현태 |
