쇼어 알고리즘
쇼어 알고리즘은 양자 정수 인수분해·차수 탐색 분야에서 사용되는 대표적인 알고리즘이다. 양자 차수 탐색과 고전적 최대공약수 계산 결합을 중심으로 동작하며, 처리 대상은 큰 정수 N과 양자 회로를 위한 산술 연산이다. 주요 활용에는 양자 계산 복잡도·공개키 암호의 안전성 연구이 포함된다.
| 분류 | 양자 정수 인수분해·차수 탐색 |
|---|---|
| 설계 | Peter Shor |
| 공개 | 1994년 발표 |
| 입력 | 큰 정수 N과 양자 회로를 위한 산술 연산 |
| 핵심 구조 | 양자 차수 탐색과 고전적 최대공약수 계산 결합 |
| 성질·전제 | 오류가 수정된 충분히 큰 양자 컴퓨터에서 다항 시간 인수분해 가능 |
| 활용 | 양자 계산 복잡도·공개키 암호의 안전성 연구 |
| 참고 자료 | 논문·공식 문서 |
쇼어 알고리즘은 양자 정수 인수분해·차수 탐색 분야에서 사용되는 대표적인 알고리즘이다. 양자 차수 탐색과 고전적 최대공약수 계산 결합을 중심으로 동작하며, 처리 대상은 큰 정수 N과 양자 회로를 위한 산술 연산이다. 주요 활용에는 양자 계산 복잡도·공개키 암호의 안전성 연구이 포함된다.[1]
쇼어 알고리즘은 양자 계산을 사용해 큰 정수의 인수분해 문제를 효율적으로 해결하도록 설계된 알고리즘이다. Peter Shor가 1994년 발표했으며, 고전 컴퓨터에서 일반적으로 비용이 큰 차수(order) 탐색 부분에 양자 위상 추정과 관련된 변환을 이용하고, 결과를 고전적인 정수 계산과 결합한다. 큰 정수 인수분해의 계산 복잡도를 양자 컴퓨터에서 다항 시간으로 줄일 수 있다는 사실을 보여주는 대표적인 이론적 성과다.
인수분해 대상 N에 서로소인 정수 a를 선택하고 a^r ≡ 1 (mod N)을 만족하는 최소 양의 정수 r을 구하는 문제로 변환한다. 양자 회로는 모듈러 거듭제곱의 주기 정보를 위상 추정으로 추출한다. r이 짝수이고 필요한 조건을 만족하면 gcd(a^(r/2)-1,N)과 gcd(a^(r/2)+1,N)으로 N의 비자명한 약수를 구할 수 있다.
양자 차수 탐색의 결과가 항상 곧바로 성공적인 인수분해로 연결되는 것은 아니므로 무작위 a를 다시 선택하는 반복이 포함된다. 양자 회로에서 모듈러 산술과 오류 수정에 상당한 하드웨어 자원이 필요하므로 이론적 다항 시간 결과가 곧바로 현존 하드웨어로 대형 RSA 키를 해독할 수 있음을 의미하지는 않는다. RSA 등 인수분해에 의존하는 공개키 암호 체계와 양자내성 암호 연구에 큰 영향을 주었다.[2]