쇼어 알고리즘

쇼어 알고리즘(Shor's algorithm)은 양자 컴퓨터에서 큰 정수의 소인수분해와 이산대수 문제를 다항 시간에 푸는 양자 알고리즘으로, 1994년 피터 쇼어가 발표했다.

개요

고전 컴퓨터에서 소인수분해와 이산대수는 입력 크기가 커질수록 풀이 시간이 급격히 늘어나는 어려운 문제로 여겨지고, RSA·디피-헬만·타원 곡선 암호 같은 공개키 암호가 그 어려움에 안전성을 기댄다. 쇼어는 양자 컴퓨터에서는 두 문제가 모두 다항 시간에 풀린다는 것을 보였다. 그는 논문에서 디지털 컴퓨터가 어떤 물리적 계산 장치든 다항식 배의 시간 증가만으로 흉내 낼 수 있다는 통념이 양자역학을 고려하면 성립하지 않을 수 있다고 적고, 정수 인수분해와 이산대수에 대한 효율적인 양자 알고리즘을 제시했다.

동작 원리

쇼어 알고리즘은 소인수분해를 차수 찾기(order finding, 주기 찾기) 문제로 바꾸어 푼다. IBM 의 양자 알고리즘 강의도 위상 추정으로 차수 찾기를 풀고, 차수 찾기의 효율적인 풀이가 곧 정수 인수분해의 풀이가 된다고, 즉 인수분해를 차수 찾기로 환원한다고 설명한다.

1. 인수분해할 수 N 과 서로소인 수 a 를 고른다
2. a 를 거듭제곱해 N 으로 나눈 나머지가 처음으로 1 이 되는 지수 r(a 의 차수)을 찾는다. 이 단계만 양자 컴퓨터가 맡는다. 중첩 상태의 여러 입력에 대해 함수 값을 한꺼번에 계산한 뒤 양자 푸리에 변환으로 주기를 뽑아낸다
3. r 이 짝수이면 a 의 r/2 제곱에서 1 을 빼거나 더한 값과 N 의 최대공약수를 구한다. 이 값이 N 의 인수가 된다
4. 실패하면 다른 a 로 다시 한다. 나머지 단계는 고전 컴퓨터로 한다

암호에 미치는 영향

• RSA 는 소인수분해, 디피-헬만·DSA·ECC 는 이산대수 문제에 기대므로 충분히 큰 양자 컴퓨터가 나오면 모두 깨진다
• AES 같은 대칭키 암호와 해시 함수는 쇼어 알고리즘의 대상이 아니다. 이쪽은 탐색 속도를 제곱근 수준으로 줄이는 그로버 알고리즘이 위협이며, 키 길이를 늘려 대응한다
• 이 위협에 대비해 격자·부호·해시 기반의 양자 내성 암호로 옮겨 가고 있다
• 실제로 RSA 를 깨려면 오류가 정정된 논리 큐비트가 매우 많이 필요하다. 지금의 양자 컴퓨터는 잡음이 커서 양자 오류 정정이 선결 과제이다

양자 컴퓨터에 대한 흔한 오해와 구별하기

진술	판단
쇼어 알고리즘은 소인수분해를 차수 찾기 문제로 바꾼다	맞다
양자 컴퓨터는 중첩을 이용해 여러 입력에 대한 함수 값을 한 번에 계산한다	맞다(양자 병렬성). 다만 측정하면 결과 하나만 얻으므로 간섭으로 원하는 답의 확률을 높이는 알고리즘이 필요하다
중첩 상태의 큐비트를 측정하면 상태가 바뀐다	맞다. 측정하면 중첩이 무너지고 0 또는 1 중 하나로 정해진다
큐비트는 저장·전송 중 오류가 생기지 않는다	틀렸다. 큐비트는 주변 환경과의 상호작용(결어긋남)에 매우 약해 오류가 잦다

같이 보기

• 양자 컴퓨터
• 양자 오류 정정
• 양자 내성 암호
• 소인수분해
• 이산대수