hong1214   8달 전

밀러 뭐시기가 제가 이해를 제대로 못한

syminisanta   8달 전

37도 넣어야되지않나요?

hemisphere1357   8달 전

밀러 라빈 판정이 불완전한 것 같습니다.

x가 1이거나 P-1이면 통과, 그렇지 않으면 제곱 반복으로 P-1이 나오는지 확인해야 합니다.

ModPow 값이 -1인지를 비교하고 계신데, P-1로 바꿔야 할 것 같습니다.

왜냐하면 양수의 제곱을 양수로 나누어봤자 양수 나머지가 나오기 때문입니다.

그리고 P(입력값)이 바뀌면 안 됩니다.

현재 x가 -1이 아니어서 P가 1씩 증가하게 되는데 이럴 경우 밀러 라빈 로직이 꼬입니다.


codinghoneyjam   8달 전

밀러라빈은 이 문제에서는 좀 오버킬 같고 더 간단한 소수판정으로도 가능하긴 합니다

댓글을 작성하려면 로그인해야 합니다.