1
Miller-Rabin test은 소수를 테스트하기 위해 k 개의 임의의 정수를 사용합니다. CLRS 따르면결정 론적 소수를 테스트하는 Miller-Rabin 수정 버전?
3 RD 판, 페이지 971 :
정리 31.38
N이 홀수 합성 수, N의 compositeness 증인의 다음 번호가 최소 인 경우 (n-1)/2이다. (- 1 N)/2 값과 소수성을 위해 그들을 시험 그리고
왜 우리는 단지 대신 다른를 사용 임의 테스트 시간을 케이 실행하지? 2를 제외한 모든 소수는 이상하고 증인은 최소한 (n - 1)/2가 없으므로 증인이있는 경우 증인을 찾을 수 있습니다.
그러나 여전히'k' 테스트를 사용합니다. 'k'는 정말 작고 숫자의 절반 값입니까? 그 때 사용 된 가치는 무엇입니까? – Existent
@ABHI'k'는 정말 작습니다. 밀러의 원래 테스트는 일반화 된 리만 가설을 필요로하며, k = O (log^2 n)로 설정합니다. –