RSA 암호화 프로그램을 만들던 도중, 고민이 생겼다.
소수를 생성할때, 밀러-라빈 소수 판정을 해야 하는데, 몇번 반복해야 하는지를 모르겠다.
그래서 알아보기로 했다.
일반적으로 알고리즘 문제를 풀때는, 다들 대충 이런 공식을 적용하는 것 같다.
검사하는 값이
$2^{32}$보다 작을때 : a값을 [2,7,61]로 함.
$2^{64}$보다 작을때 : a값을 [2, 325, 9375, 28178, 450775, 9780504, 1795265022]로 함.
이 숫자는 miller-rabin.appspot.com/ 여기에도 나와있다.
여기까지는 좋다. 근데 만먁 64비트보다 크다면?
RSA 알고리즘에 적용할 키 값은 당연히 64보다 커야한다. 2048 정도로 생각하는데, 어떻게 해야할까?
내가 개발할때 참고했던 코드에선 아래와 같이 했다.
$2^{1536}$보다 크거나 같을때 : 반복횟수를 3로 함.
$2^{1024}$보다 크거나 같을때 : 반복횟수를 4로 함.
2^{512}$보다 크거나 같을때 : 반복횟수를 7로 함.
나머지 : 반복횟수를 10로 함.
숫자가 커질수록 반복횟수가 줄어든다니? 좀 이상한 것처럼 보였다.
그래서 더 찾아봤더니 구체적인 방법을 StackExchange에서 찾을 수 있었다.
위 문서의 4.22을 보면 9가 아닌 n이 소수가 아닌데도 소수로 판별해주는 a값을 Strong liar(강한 거짓말쟁이)라고 부르는데, 이 값이 최대 $\Phi(n)/4$개씩 나온다는 것이다.
근데, 4.23을 보면 n이 홀수일 땐, 모든 a에 대해서 Strong liar일 확률이 최대 1/4이라고 한다. (최대 $n/a$개)
실제 값은 꽤 적다. k(위의 n)이 100일때, 1번만 판별법을 수행한 경우, Strong liar인 a가 n을 소수라고 판정할 확률이 $2^{-5}$이 나왔다.
이러한 확률을 바탕으로, 4.49에선 $2^{-80}$정도의 오류율이 나오면, 괜찮다고 보았다.
$2^{-80}$는 약 0.0000000000000000000000000827 이다.
(n이 커질 수록 반복횟수가 줄어드는 이유는 딱히 찾지 못했지만, table4.3의 확률을 봤을때 log 형태의 그래프가 그려지지 않을까 싶다.)
