파이썬용 소수 판정 함수

Strong Probable Prime Test를 사용한 간단한 소수 판정 함수입니다. 속도도 그럭 저럭 빠른 편이어서 애용(?)하고 있습니다.

code snippet에도 올라 와 있습니다. 이 쪽에서는 간단한 테스트들도 볼 수 있습니다.

def issprp(n, a):
    """Returns True if n is a-SPRP, False otherwise."""
    if n < 2 or n & 1 == 0: return False
    d = n - 1
    while d & 1 == 0:
        d >>= 1
        if pow(a, d, n) + 1 == n: return True
    return pow(a, d, n) == 1

def isprime(n):
    """Returns True if n < 341,550,071,728,321 is prime, False otherwise."""
    if n < 2: return False
    elif n < 4: return True
    elif not issprp(n, 2): return False
    elif n < 2047: return True
    elif not issprp(n, 3): return False
    elif n < 1373653: return True
    elif not issprp(n, 5): return False
    elif n < 25326001: return True
    elif n == 3215031751 or not issprp(n, 7): return False
    elif n < 118670087467: return True
    elif not issprp(n, 11): return False
    elif n < 2152302898747: return True
    elif not issprp(n, 13): return False
    elif n < 3474749660383: return True
    elif not issprp(n, 17): return False
    elif n < 341550071728321: return True
    else: raise ValueError, "cannot test primality of n >= 341,550,071,728,321."

- 토끼군