암호에 사용하는 소수를 판정하는 방법

소인수분해의 어려움을 이용한 암호

정보의 암호화 방법 중 하나로 RSA 암호가 있습니다. 이것은 '자리수가 큰 소수끼리 곱한 수의 소인수분해는 간단하게 되지 않는다'는 특성을 이용한 암호의 하나로, 인터넷 보안기술에 널리 이용되고 있습니다. RSA 암호를 만들려면 거대한 소수가 필요하지만, 이를 위해서는 먼저 후보인 거대한 숫자가 정말 소수인지를 판정할 필요가 있습니다.

Author : Bananenfalter. https://commons.m.wikimedia.org/wiki/File:Orange_blue_public_key_cryptography_en.svg

소수의 판정은 어렵다!

소수 판정의 가장 소박한 방법은 그 수를 2부터 나누어 나가는 것입니다. 예를 들어, n이 소수인지 여부를 확인하기 위해 루트 n까지 나누어 갑니다만, n이 100자리라면 50자리까지 계산해야 하고, 계산에 엄청난 시간이 걸려버려 실용적이지 않습니다. 그래서 이를 대신할 소수의 판정 알고리즘으로 두 가지 알고리즘(계산 단계)을 소개합니다.

밀러-라빈 소수판별법과 AKS 소수판별법

'밀러-라빈 소수판별법'은 소수라는 것을 거의 확실하게 확인하는 방법입니다. '거의 확실'이라고 표현하는 이유는 100% 판정할 수 있는 것이 아니라는 뜻이지만, 판정에 실패할 확률이 매우 낮은 데다 즉시 판정할 수 있다는 편리성에서 널리 이용되고 있습니다.

100% 정확하고 시간도 적게 걸리는 판정방법을 찾는다는 것이 수학자의 신조이기 때문에, 그런 방법을 찾는 노력은 오랫동안 계속되어 왔습니다. 그리고 금세기 초반 확실한 소수 판정이 가능하며 이론적으로 빠른 'AKS 소수판별법'이라는 방법이 개발되었습니다. 조금 난해한 설명되지만, 이 방법은 리만 가설 등의 가설을 이용하지 않고 결정성 다항식 시간(주어진 자연수 n이 소수인지 여부의 판정 시간이 log(n)의 다항식을 상계로 하는 시간)으로 판정하는 첫 번째 알고리즘입니다. 단, 다항식의 차수가 너무 높아서 기존에 판정이 불가능했던 소수를 고속으로 판정할 수 있게 된 것은 아니어서 여전히 과제가 있습니다.

출처 참조 번역
· Wikipedia
- 暗号に使う素数を判定する方法とは？
https://yumenavi.info/lecture_sp.aspx?%241&GNKCD=g006969