밀러라빈 소수판별 알고리즘1 [암호학] Miller-rabin test를 통한 소수판별 밀러-라빈(miller-rabin) test를 통한 prime 판별 이번 포스팅에서는 강력한 소수 판별 기법 중 하나인 밀러라빈 소수판별법에 대해서 알아보겠습니다. 밀러라빈 테스트를 요약해서 말한다면, Fermat test와 Fermat factorization을 통해 소수를 판별하는 기법이라고도 할 수 있습니다. Fermat test란 ? 페르마의 소정리(Fermat Little Theorem)를 이용해서, 소수를 판별하고자 하는 것입니다. 페르마의 소정리란 다음과 같습니다 이때 이 역과정을 이용해서 만약 위의 식을 만족하는 p가 존재한다면, p는 소수라고 할 수 있을까? 라는 아이디어를 가지고 소수를 판별한 것입니다. 결과적으로, Fermat test만을 가지고 소수를 판별하는 것을 불가능합니다. F.. 2021. 6. 22. 이전 1 다음
