연습문제 1.26은 반으로 나누는 대신 expmod 프로시저를 두 번 호출하기에

결국 Θ(n)이 됩니다.

연습문제 1.27은 카마이클 수(Carmichael number)를 찾는 문제입니다.

찾는 방법은 앞에 있는 코드를 이용하여 만들었습니다.

코드는 위와 같게 만들었습니다.

위와 같이 확인해보았습니다.

제대로 확인이 됩니다.

이 방법은 페르마 방법으로 하면 다시 한 번 확인하는 것이라

소수일 경우에는 계산을 두 번합니다.

따라서 그리 좋지 못합니다.^^;;;;

카마이클 수에 대해 검색하니 일반식이 나온 듯싶네요.

'Carmichael number'

'Carmichael number'

그렇다면 미리 Carmichael number를 구한 다음에

소수를 구할 때 소수라 나오면 미리 구한 값들과 비교만 하면 되겠네요.^^

참조

Structure and Interpretation of Computer Programs 2/E - Page 71

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.