[알고리즘] 기본 개념 정리 (11) - 확률적 알고리즘을 이용한 문제 해결

확률적 관점에서의 소수 판별

Q. 자연수 n을 입력받아서, n이 소수인지 아닌지 판단하는 프로그램에서,

• 결정론적 알고리즘에 대응되는, 무작위 알고리즘의 개념
  • Deterministric Algorithm
    • 동일한 입력에 대하여, 매번 동일한 결과를 출력하는 형태의 알고리즘으로, 확률과 무작위성이 개입하지 않음
    • ex. 자연수 N이 소수인지 판별하기 위해, 2,3,4, - - - 루트N까지의 수로 나눠봄
  • Randomized Algorithm
    • 확률과 무작위성이 개입함으로써 동일한 입력에 대해서도 다른 결과가 나타날 수도 있는 형태의 알고리즘
    • ex. Miller-Rabin 소수 판별법, Pollard-Rho 알고리즘을 이용한 소인수분해

오일로 정리로 얻을 수 있는 소수의 특성

→ Miller-Rabin 소수 판별법

Miller-Rabin 소수 판별법

결론은 반드시 성립함!

++ 조건이 성립하지 않음 → 반드시 합성수, 조건을 만족하면 소수일 가능성이 있는 것

1. N에 1을 뺀다.
2. 원하는 밑의 제곱으로 표현한다. → s와 d를 구할 수 있음
3. 위 결론의 1,2 조건을 확인한다.

def MR_prime(N, a):
    if N <= 1: return 'DEFINITELY NOT PRIME'
    if N == 2: return 'Maybe Prime'
    if N % 2 == 0: return 'DEFINITELY NOT PRIME'

    # N-1을 d * 2^s로 표현
    s = 0
    d = N - 1
    while d % 2 == 0:
        s += 1
        d //= 2

    # a^d ≡ 1 (mod N)인지 확인
    if pow(a, d, N) == 1:
        return 'Maybe Prime'

    # a^(d*2^r) ≡ -1 (mod N)인지 확인 (0 ≤ r < s)
    for r in range(s):
        if pow(a, 2**r * d, N) == N - 1:
            return 'Maybe Prime'

    return 'DEFINITELY NOT PRIME'

약수 탐색과 소인수분해 문제

• RSA Cryptosystem - 소인수분해 문제의 난해함에 기반
• Diffie Hellman Protocol - 이산로그 문제의 난해함에 기반

Pollard-Rho Algorithm

• 나머지 연산을 이용해 얻은 N에 대한 순환 그래프에서 출발
• 순환 그래프의 난수 사이 차를 D라고 할 때 GCD(D,N)을 계산
  • 최대공약수가 1보다 클 경우 그것을 약수로 취함

def GCD(a,b):
    if (a == 0) :
        return b
    if (b == 0) :
        return a
    if (a >= b) :
        return GCD(a%b, b)
    else:
        return GCD(a, b%a)

def g(x):
    return (x**2 + 1)

def PR(N, x1, x2):
    while (1):
        x1 = g(x1) % N
        x2 = g(g(x2)) % N
        if (x1 == x2):
            return 'FAIL'
        check_gcd = GCD(abs(x1-x2), N)
        if (check_gcd >1):
            return check_gcd

생일 문제와 무작위성

Q. 교실에 N명의 학생이 있을 때, 생일이 같은 경우가 존재할 확률은?

• 집단 내 원소 수가 적더라도, 생일이 같은 충돌 쌍을 쉽게 찾을 수 있음
  • 해싱 등 암호 체계에서의 생일 공격 가능성
• 1에 가까운 확률을 반복적으로 곱하는 과정에서 급격히 0에 가까워지는 확률
  • 틀릴 가능성이 높은 알고리즘도 반복적으로 시도한다면? → 맞을 확률을 높일 수 있음

무작위화를 이용한 문제 해결

경우를 찾기 위해 너무 많은 경우의 수 탐색이 필요한 경우,

→ 틀릴 가능성이 높은 알고리즘도, 반복적으로 시도하면 높은 확률로 정답을 도출해낼 수 있음

1. 무작위로 조건의 일부를 만족하는 경우를 찾고
2. 해당 경우가 전체 조건을 만족시키는지 확인