sicp.io
1.2.5 · 소수 검사

빠른 검사를 통과했다는 사실에는 분명한 경계가 있다.

시험한 약수 수를 세고 여러 모듈러 거듭제곱 검사를 실행한 뒤 카마이클 수로 probable-prime 신호와 정확한 인수 분류를 비교합니다.

생각해 볼 질문

각 소수 검사 프로시저는 무엇을 확정하며, true를 반환한 뒤에도 무엇이 결정되지 않은 채 남을까요?

  • 후보 약수가 제곱근 경계를 넘으면 시험 나눗셈 멈추기
  • 시험한 약수 수와 마지막 소수·합성수 답을 따로 기록하기
  • 빠른 모듈러 거듭제곱을 페르마 합동 검사에서 재사용하기
  • 선택한 여러 밑을 하나의 probable-prime 결과로 결합하기
  • 카마이클 수를 순진한 페르마 확신의 반례로 알아보기

시험 나눗셈은 2부터 제곱근 경계까지 어떤 정수가 n을 나누는지 묻습니다. 하나도 없다면 더 큰 비자명 인수도 더 작은 짝 없이 존재할 수 없습니다. 첫 프로그램은 실제로 수행한 약수 검사만 세므로 답과 유한한 작업량을 서로 다른 관찰로 남깁니다.

페르마 프로그램은 선택한 밑마다 a의 n제곱이 n으로 나눈 나머지에서 a와 합동인지 검사합니다. 소수 7은 통과하고 합성수 15는 빠르게 실패하며 합성수 561은 시험 나눗셈으로 인수를 찾을 수 있는데도 서로소인 세 밑을 통과합니다. 화면의 결과는 선택한 페르마 절차에 따른 probable-prime 판정을 기록합니다.

SICP 코드UTF-8 527 / 1,048,576바이트
예제
결과
출력
진단
실행 추적0 / 0 개 이벤트
    실행은 브라우저 안에서 이루어지며 프로그램 결과와 실행 추적을 보여줍니다.
    예상 결과

    시험 나눗셈 프로그램은 ((29 29 #t 4) (35 5 #f 4) (97 97 #t 8))을 반환합니다. 페르마 비교 프로그램은 ((prime-7 #t #t) (composite-15 #f #f) (carmichael-561 #f #t))를 반환합니다.

    실행 추적에서 볼 점

    각 divides? 적용을 세고 candidate의 제곱이 n보다 커지는 지점을 찾으세요. expmod에서는 지수를 절반으로 줄이는 과정과 모듈러 축약을 따라가세요. 561에서는 인수를 찾는 시험 나눗셈 경로와 모두 true를 반환하는 선택한 페르마 경로를 비교하세요. 실행 흐름은 그 유한한 밑만 기록합니다.

    직접 해보기

    프로그램을 수정하고 결과를 비교해 보세요.

    비교 목록에 1105를 추가하고 서로소인 밑을 세 개 이상 골라 페르마 결과와 시험 나눗셈을 비교하세요. 밑을 추가할 때 probable-prime 결과가 어떻게 바뀌고 시험 나눗셈이 어떤 정확한 인수 분류를 제공하는지 설명하세요.

    힌트 보기

    1105도 카마이클 수입니다. 선택한 밑 목록을 소스에 보이게 두고 두 절차의 결과를 따로 보고하세요.

    이 수업 완료하기

    이 장의 총 18개 수업 중 0개 완료0%