나머지는 반복 제곱의 중간값을 모듈러스 안에 둔다.
곱셈할 때마다 나머지를 구하면 모듈러 결과를 유지하면서 반복 제곱으로 지수를 줄여 고정한 밑 하나의 페르마 점검을 실행할 수 있습니다.
모듈러 합동 하나로 후보 수에 관해 무엇을 알 수 있고 무엇은 알 수 없을까요?
- 제곱하거나 곱한 모든 중간값을 모듈러스로 줄이기
- 반복 제곱으로 짝수 지수를 절반으로 줄이기
- 유한한 후보에 고정한 밑의 페르마 합동 계산하기
- 합동 통과와 소수 증명 구분하기
expmod는 빠른 거듭제곱과 같은 방식으로 지수를 줄이지만 제곱하거나 홀수 단계에서 곱할 때마다 remainder를 적용합니다. 줄인 결과는 줄이지 않은 거듭제곱과 모듈러 합동이므로 전체 거듭제곱을 들고 다니지 않아도 마지막 나머지를 보존합니다.
passes-base-2?는 2의 candidate승과 2가 candidate를 모듈러스로 한 합동인지 점검합니다. 17은 통과하고 15는 실패합니다. 3과 11과 17을 곱한 합성수 561도 통과합니다. 실패는 이 합동을 만족하지 않음을 보여 주지만 밑 하나의 통과는 증거일 뿐 후보가 소수라는 증명이 아닙니다.
(begin
(define (square value) (* value value))
(define (expmod base exponent modulus)
(cond ((= exponent 0) 1)
((even? exponent)
(remainder (square (expmod base (/ exponent 2) modulus))
modulus))
(else
(remainder (* base (expmod base (- exponent 1) modulus))
modulus))))
(expmod 7 128 13))- 출력
- —
- 값
- —
- 진단
- —
모듈러 거듭제곱은 3을 반환합니다. 고정한 밑의 점검은 17과 15와 합성수 561에 대해 (#t #f #t)를 반환합니다.
각 짝수 지수가 절반 크기의 호출로 들어간 뒤 그 나머지를 제곱하고 다시 줄이는 과정을 따라가세요. 두 번째 실행에서는 유한한 호출 세 개를 구분하고 반환된 불리언이 밑 2의 합동만 보고한다는 점을 확인하세요. 제한된 실행 흐름은 소수임을 인증하지 않으며 리스펙스 바우치나 권한이 아닙니다.
힌트를 보기 전에 프로그램을 바꿔 보세요.
두 번째 프로그램에 후보 21을 더하세요. 같은 밑 2 점검을 실행한 뒤 거짓 결과는 이 합동을 판정하지만 참 결과도 소수임을 증명하지 못하는 이유를 설명해 보세요.
힌트 하나 보기
점검은 정확한 등식 하나를 묻습니다. 그 등식을 만족해도 561처럼 합성수일 수 있습니다.