1
Miller-Rabin 테스트가 최대 10¹8의 모든 숫자에 대해 올바른 것으로 보이는 증인 세트는 무엇입니까? 증인 N OEIS에 따르면 < 341550071728321.Rabin-Miller 테스트에 필요한 증인은 최대 10¹8의 숫자입니까?
A
답변
2
까지 번호를 충분 7 SPRP 기준 : {2, 325, 9375, 28178, 450775, 9780504, 1795265022}은 결정 성 테스트에 적어도 n = 2^64 (> 10^19) 이상이면 충분합니다.
0
충분하다 나는 17까지 소수의 사용을 알고, 최대 23 증인의 사용은 this 기록 페이지의 설정에 따라 3825123056546413051
0
Miller-Rabin 테스트 대신 Baillie-Wagstaff 테스트를 기꺼이 사용한다면 최대 2^64까지의 소수를 분류하는 데 오류가 없음이 인증되었습니다. 코딩 작업은 훨씬 복잡하지 않으며,이 기능은 Miller-Rabin 테스트보다 더 빨리 실행되며 분류에 대한 알려진 오류가 없습니다.
이것은 답변이 아니라 주석이어야합니다. – kinokijuf