밀러 라빈 소수 판별법(Miller-Rabin primality test) 배우기

1. 밀러 라빈 소수 판별법(Miller-Rabin primality test) 어떤 홀수 n이 소수인지 확률적으로 판별해주는 알고리즘 확률적이라는 말은, 합성수를 소수로 잘못 판별할 수 있다는 뜻이다. 주어진 n이 "합성수이다" 또는 "아마도 소수일 것이다"라는 대답을 내놓는다는 의미 2. 핵심 아이디어 알고리즘의 아이디어는 페르마의 소정리에서 시작한다. https://deepdata.tistory.com/573 페르마의 소정리 문제 풀어보면서 익히기 1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이..