aks-소수-판별-알고리즘

AKS 소수 판별 알고리즘: Python 구현과 개요

AKS(Agrawal–Kayal–Saxena) 알고리즘은 모든 자연수에 대해 다항 시간에 소수 여부를 판별할 수 있는 알고리즘으로, 수학 및 컴퓨터 과학에서 중요한 진전을 이룬 알고리즘이다. 특히 이 알고리즘은 주어진 수 $n$이 소수인지 합성수인지를 결정하는 최초의 다항 시간 알고리즘으로 주목받았다.

이 글에서는 AKS 알고리즘의 원리와 Python을 사용한 간단한 구현 방법을 설명한다. AKS 알고리즘은 여러 단계를 통해 최종적으로 소수 여부를 판별하며, 그 주요 단계는 다음과 같다.

AKS 알고리즘의 단계 요약

1. 거듭제곱 확인: 주어진 수 $n$이 특정 값 $a$와 $b$에 대해 $n = a^b$ 형태라면, 이는 합성수임을 의미하므로 소수 판별에서 제외한다.
2. 특정한 값 $r$ 찾기: 모듈러 연산을 효율적으로 수행하기 위해 주어진 $n$에 대해 특정한 값 $r$을 찾아낸다. 이는 $n$의 오일러 피 함수의 성질을 이용하여 $r$을 계산하는 과정이다.
3. 최소 공약수 검사: $r$을 찾은 후, $a$가 $n$보다 작으면서 $\gcd(a, n) > 1$인 값이 존재한다면, $n$은 합성수로 판정할 수 있다.
4. 다항식 조건 검증: 최종적으로 $$(x - a)^n \equiv x^n - a \ (\text{mod} \ n)$$라는 다항식 조건을 확인하여, 이 조건이 만족되면 $n$을 소수로, 만족되지 않으면 합성수로 판별한다.

Python 구현 예제

AKS 알고리즘을 Python으로 구현할 때, 위의 각 단계를 함수로 나누어 정의할 수 있다. 구현 예시는 다음과 같다.

from math import isqrt, gcd

def is_power(n):
    for b in range(2, int(n ** 0.5) + 1):
        a = round(n ** (1 / b))
        if a ** b == n:
            return True
    return False

def find_r(n):
    max_k = int((n ** 0.5) * (2 * (n ** 0.25)))
    for r in range(2, n):
        all_different = True
        for k in range(1, max_k + 1):
            if pow(n, k, r) == 1:
                all_different = False
                break
        if all_different:
            return r
    return n

def aks_primality(n):
    if n <= 1:
        return False
    if n in (2, 3):
        return True
    if is_power(n):
        return False

    r = find_r(n)
    for a in range(2, min(r, n)):
        if gcd(a, n) > 1:
            return False

    for a in range(1, isqrt(r * (n - 1)) + 1):
        if pow(a, n, n) != a % n:
            return False

    return True

# 테스트 예제
n = 97
print(f"{n}는 소수인가요? {aks_primality(n)}")

구현 설명

1. is_power 함수: $n$이 특정 거듭제곱 형태인지 확인하여, 만약 거듭제곱 형태라면 합성수로 판정한다.
2. find_r 함수: 주어진 $n$에 대해 특정 값 $r$을 찾아, 이 값으로 다항식 조건을 효율적으로 검사할 수 있도록 한다.
3. aks_primality 함수: AKS 알고리즘의 주요 함수로, 주어진 $n$에 대해 소수 여부를 판별한다.

AKS 알고리즘과 일반적인 소수 판정법 비교

일반적인 소수 판정법으로는 에라토스테네스의 체나 밀러-라빈 테스트와 같은 확률적 및 결정적 방법이 있다. 에라토스테네스의 체는 작은 수들에 대해 매우 효율적이지만, 큰 수에서는 메모리와 시간 효율이 떨어지는 단점이 있다. 밀러-라빈 테스트는 빠르고 큰 수에도 적합하지만 확률적 알고리즘이므로 아주 큰 수에서는 오류 가능성을 배제할 수 없다.

이에 반해 AKS 알고리즘은 확률적 접근이 아닌 결정적 접근 방식으로 모든 경우에 대해 다항 시간 안에 정확한 결과를 보장한다는 점에서 큰 차이가 있다. 그러나 실제로는 밀러-라빈 테스트 등보다 구현이 복잡하고 실행 시간이 길기 때문에 일반적인 소수 판정에 바로 사용되기에는 다소 비효율적이다. 그럼에도 불구하고 AKS 알고리즘은 수학적으로 소수 판정 문제에 대해 **“Primes in P”**를 증명했다는 점에서 중요한 의의가 있다.

https://ko.wikipedia.org/wiki/AKS_%EC%86%8C%EC%88%98%ED%8C%90%EB%B3%84%EB%B2%95

AKS 소수판별법 - 위키백과, 우리 모두의 백과사전