문서:쇼어 알고리즘

[[분류:알고리즘]]
[목차]
== 개요 ==
쇼어 알고리즘(Shor's algorithm)은 다항 시간안에 소인수 분해를 할 수 있는 양자 알고리즘이다. 피터 쇼어(Peter Shor)가 1994년의 논문[* Shor, P. W. (1994). Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science (pp. 124-134). IEEE.]에서 제안한 알고리즘이다.

쇼어 알고리즘이 중요한 이유는 [[RSA 암호화]]와 관련이 있다. RSA 암호화는 큰 소수의 합성수를 소인수로 분해하는 문제는 고전 컴퓨터로 다항 시간에 풀 수 없는 문제로 알려져 있다. 따라서 [[RSA 암호화]] 체계는 소인수 분해의 어려움에 기반하여 설계되어 있다고 할 수 있다. 그래서 쇼어의 양자 알고리즘으로 정수의 소인수 분해 문제를 다항 시간 안에 풀 수 있게 되면, RSA 암호화를 사용하는 모든 서비스가 큰 보안 위협에 처하게 된다. 

== 쇼어 알고리즘의 고전적 구현 ==
쇼어 알고리즘은 합동 관계의 주기성을 이용하여 소인수 분해를 한다. 자세한 원리는 이 [[https://www.youtube.com/watch?v=lvTqbM5Dq4Q|영상]] 참조 따라서 쇼어 알고리즘 자체는 고전 컴퓨터로도 구현할 수 있다. 다만, 고전 컴퓨터로 구현한 쇼어 알고리즘은 여전히 지수적인 시간 복잡도를 가지기 때문에, 다항 시간에 소인수 분해를 하려면 양자 컴퓨터를 이용해야 한다.

>SHOR'S-FACTORING-ALGORITHM:
>Input: 두 개의 소수 p, q의 곱으로 만들어진 합성수 N=p*q
>Output: N의 소인수 p, q 
>Procedure:
>1. 1보다 크고 N보다 작은 정수 a를 임의적으로(randomly) 선택한다. 
>2. 만일 N과 a의 최대공약수 gcd가 1이 아니면, 운이 좋게 소인수 p를 발견한 것이다. 따라서 p=gcd, q=N//gcd를 리턴하고 종료한다.
>3. 함수 f(x)=a^x (mod N)의 주기 r을 찾는다.여기서 찾은 주기 r이 짝수가 아니라면, 1번 단계부터 다시 시작한다.
>4. 주기 r로부터 두 개의 최대공약수 gcd1=gcd(N, a^(r//2)) + 1), gcd2=gcd(N, a^(r//2)) - 1)를 찾는다.
>5. 여기서 찾은 두 개의 수 gcd1, gcd2 중 하나라도 1이라면, 1번 단계부터 다시 시작한다. 아니면, 마침내 소인수들을 찾았으므로 gcd1, gcd2를 리턴하고 종료한다. 

상기한 알고리즘을 파이썬으로 구현하면 다음과 같다. 
{{{#!syntax python
import random 
import math 

def mod_pow(a, x, N):
    y = 1
    while (x > 0):
        if ((x & 1) == 1):
            y = (y * a) % N
        x = x >> 1
        a = (a * a) % N
    return y

def findPeriodByModPow(N, a):
    for x in range(1, N):
        if (mod_pow(a, x, N) == 1):
            return x
    return -1

def factorizeByShor(N):
    while(True):
        a = random.randint(2, N - 1)
        gcd = math.gcd(N, a)
        if (gcd != 1):
            return gcd, N // gcd
        r = findPeriodByModPow(N, a)
        if (r % 2 != 0):
            continue
        gcd1 = math.gcd(N, a**(r//2) + 1)
        gcd2 = math.gcd(N, a**(r//2) - 1)
        if (gcd1 == 1 or gcd2 == 1):
            continue
        return gcd1, gcd2
}}}상기한 쇼어 알고리즘에 대한 상세한 설명과 구현에 대한 해설은 [[https://youtu.be/MEijrZgRlRQ|이 영상]]과 [[https://youtu.be/ZMbw_KGhLD0|이 영상]]을 참고할 수 있다. [* [[https://youtu.be/MEijrZgRlRQ|소인수 분해를 위한 쇼어의 양자 알고리즘]]] [* [[https://youtu.be/ZMbw_KGhLD0|쇼어의 소인수 분해 알고리즘 구현]]]

== 쇼어 알고리즘의 양자 회로 구현 ==
쇼어 알고리즘의 주기 찾기 부분을 양자 회로 부분을 구현하기 위해서는 양자푸리에변환(QFT: Quantum Fourier Transform)과 역양자푸리에변환(I-QFT: Inverse-QFT)을 양자 회로로 구현해야 한다. 

여기에 대한 자세한 설명은 [[https://qiskit.org/textbook/ch-algorithms/shor.html|이 문서]]를 참고할 수 있다. [* [[https://qiskit.org/textbook/ch-algorithms/shor.html|Shor's Algorithm in Qiskit Textbook]]]