쇼어 알고리즘

쇼어 알고리즘(Shor's algorithm)은 소인수 분해를 빠르게 처리할 수 있는 양자 알고리즘이다. 수학자 피터 쇼어가 제안했다. 쇼어 알고리즘을 사용하면 크기가 $N$인 수를 소인수 분해할 때 $O(\log ^{3}N)$의 시간과 $O(\log N)$의 저장공간이 필요하다. 쇼어는 이 업적으로 국제수학자회의에서 가우스상을 받았다.

이 알고리즘의 가장 중요한 점은 이것을 이용하면 공개 키 암호 방식을 쉽게 깰 수 있다는 점이다. 예를 들어 RSA의 경우, 매우 큰 두 개의 소수를 곱한 값을 공개 열쇠 $N$으로 사용한다. 이와 같은 방식이 안전한 이유는 $N$을 빠른 시간 안에 효율적으로 소인수 분해하는 알고리즘이 지금까지 발견되지 않았기 때문이다. 그러나 쇼어 알고리즘을 충분히 큰 수에 대해서 적용할 수 있는 기계가 만들어지면, 오늘날의 공개 키 암호 방식은 모두 무용지물이 된다. 이런 점에서 쇼어 알고리즘은 양자 컴퓨터의 킬러 애플리케이션(killer application)인 셈이다. 그래서 양자암호와 양자 후 암호 기술이 개발되고 있다.

2001년에 IBM의 연구팀이 7개의 큐비트를 이용하여 15를 3과 5로 소인수 분해할 수 있는 양자 컴퓨터를 만들었다. 그러나 RSA 암호에서 실제로 사용하는 수백자리의 수를 소인수 분해하는 단계까지 이르기에는, 아직도 수많은 연구가 필요하다.

같이 보기

• 렌스트라의 타원곡선 알고리즘