아무런 제한이 없을 때의 밀러-라빈 판정법은 매번 base를 독립 랜덤으로 뽑아서 사용하는 것이 기본이고 100% 성공을 보장하지 않습니다. 하지만 판정하려는 수가 특정 값 이하 등 추가 조건이 있으면 특정 base 값들만 시도해 봐도 충분하고 그런 base 값의 목록들이 많이 알려져 있습니다.
4134번 - 다음 소수
아무런 제한이 없을 때의 밀러-라빈 판정법은 매번 base를 독립 랜덤으로 뽑아서 사용하는 것이 기본이고 100% 성공을 보장하지 않습니다. 하지만 판정하려는 수가 특정 값 이하 등 추가 조건이 있으면 특정 base 값들만 시도해 봐도 충분하고 그런 base 값의 목록들이 많이 알려져 있습니다.
댓글을 작성하려면 로그인해야 합니다.
legoha2011 11달 전
제가 정수론을 몰라서 질문이 있습니다
소수 판별법에 대해 알아보는 중 밀러-라빈 소수 판별법의 정확도는 100%가 아니라고 되어있는데
테스트 횟수가 높을수록 정확도가 높다는건 이해했습니다
비교 테스트값은 다음과 같이 7bases로 했는데
이 테스트 값이 달라지면 테스트 횟수가 같아도 정확도가 달라지는건가요?