10. 밀러-라빈 소수 판별법

근 거의 2달을 트래픽 제어에 열중(이 아닌 속박)하며 살다보니 블로깅을 거의 망각하다시피 살고 있었다... 취준을 위한 공부라지만 할 건 너무 많아 뭐부터 해야되나라는 안일하기 그지없는(?) 고민을 하다가 원래 할 게 많으면 좋아하는 것부터 하라고 했으니 그럼 알고리즘부터 해야지! 라고 생각하며 백엔드를 공부하는 나날이다.

요즘은 스프링 시큐리티를 다시 능숙까진 아녀도 개념을 이해하며 다루는 연습을 겸하며 도커와 레디스 등 이것저것 다뤄보는 데에 노력을 다하고 있다. 얼른 포폴 하나 더 쌓아서 취업하고 싶어라...

백준 알고리즘 문제 중에서 수학과 관련된 문제를 발견했다가 피보고 알고리즘 공부에 잠시 열중하게 한 놈이 있었다. 원래 알고리즘 공부를 하면서 수학을 써먹을 일은 없나... 싶었는데, 수학을 쓰려면 제대로 본격적으로 써먹어야 할 줄 알아야 한다는 진리를 깨우쳐준 문제였다.

1) 전제 개념

전제 개념이 상당히 많은 편이다. 단순 소수의 정의는 물론이고, 모듈러 연산과 페르마의 소정리, 정수론까지 딥하게 다뤄야 하는 알고리즘이지만 나는 지금 수학을 공부하는 게 아니므로 전제되는 개념들에 대해서 간략하게만 짚고 바로 구현 단계로 넘어갈 예정.

(1) 소수

수학, 그 중 정수에서 가장 난해한 개념이 소수다. 소수란 1과 자기 자신만을 약수로 가지는 수를 뜻한다. 이를 달리 말하면 합성수가 아니며, 소인수분해가 되어도 인수가 1 또는 자기 자신만 나오며, 그 과정에서 지수가 1이고 거듭제곱이 되지 않는 수를 뜻한다.

(2) 모듈러 연산

이 부분은 간단하게 개념만 짚고, 컴퓨터에서는 어디에 쓰이는지 확인하고 넘어갈 예정이다. 모든 정수는 나눗셈을 했을 때, 나머지가 존재한다. 약수를 제수로 삼으면 그건 곧 나머지가 0인 셈이다.

이 나머지 값의 특징은, 제수를 넘지 못한다는 것이다. 정수가 무한정 커지면 소프트웨어 입장에서는 감당할 수 있는 용량을 넘길 수 있고 이는 오버플로우로 이어져 예외를 반환할 수 있다. 이 때 쓰이는 게 특정 정수로 나눠서 나머지 값 범위 내에서만 수가 돌아가도록 한정할 수 있다.

${\displaystyle a=q\times d+r}$

이 원리는 일전에 봤던 해시 알고리즘 등에서도 쓰이고 있다.
이와 관련돼서 mod라는 키워드가 나오는데, 이것과 관련돼서 합동 기호가 쓰이는 수식 표현이 존재한다.

$a ≡ b\;(\,mod\; N\,)$

a를 N으로 나눈 나머지와 b를 N으로 나눈 나머지가 같다

(3) 페르마의 소정리

이걸 입증하고 이해하는 건, 정수론을 다뤄야 함을 전제하고 나 역시 그 정도 수준이 안 되는 게 자명(...)하기 떄문에 정말 간단하게 밀러-라빈 알고리즘에서 쓰이는 개념만 간단히 짚고 도망갈 예정.

소수 p와 정수 a에 대하여 다음을 만족한다

• a^p ≡ a (mod p)
• a ^ (p-1) ≡ 1 (mod p) if a % p != 0
  --> a를 p-1번 곱한 수를 소수 p로 나눈 나머지 == 1

추가 보조정리는 아래와 같다.

• 소수 p에 대하여 x^2 ≡ 1 (mod p) 이면, x ≡ -1 (mod p) or x ≡ 1 (mod p)
  --> x^2 - 1이 p의 배수이므로, x-1 또는 x+1이 p의 배수가 된다.

(4) 고속 거듭제곱 알고리즘

어떤 정수 a를 n번 거듭제곱하는 것을 단순 while 문 등으로 반복 처리하는 것은 빅오엔 계산법에 의해 O(N)이 나오게 된다.

long long 범위의 큰 지수의 거듭제곱을 계산하는 것은 비효율적이므로, 이것을 병합 정렬에서 썼던 방식으로 계산하면 O(log N) 범위 내에서 빠르게 계산할 수 있게 된다.

# a의 b제곱을 구하기
def power(a, b):

    result = 1

    while b > 0:
        # b가 홀수일 경우
        if b % 2 != 0:
            # result에 밑 한 번 더 곱하기
            result = result * a

        # 제곱한 만큼 b는 2로 나눠주고
        # 홀수, 짝수 상관없이 a는 제곱
        b = b // 2
        a = a * a

    return result

2) 밀러-라빈 소수 판별 알고리즘 구현

참고로 알아둬야 할 것은, 이 알고리즘은 이 수가 소수다!라고 판별하는 알고리즘이 아닌, 소수일 가능성이 높다!라고 판별하는 알고리즘이다. 그렇기 때문에 대수의 법칙에 의해 여러 번 반복 테스트를 수행해야 실제 소수인지 판별 결과의 신뢰도가 높아지게 된다.

테스트를 수행함에 있어서 필요한 것은 기준 수가 되는 소수를 선택하는 것이다. 위에서 언급한 반복 테스트에서 달라지는 부분은 이 기준 수가 달라지기 때문에 이 부분을 반복문 등으로 처리해서 여러 번 테스트를 수행했을 때, 항상 true가 나오는 지를 확인하는 추가 구현 작업이 필요하다.

구현 링크는 아래와 같다.

https://github.com/kimD0ngjun/algorithm_structure/blob/main/src/algorithm/math/MillerRabin.py