쇼어 알고리즘

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

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

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

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

이 글은 컴퓨터 과학에 관한 토막글입니다. 여러분의 지식으로 알차게 문서를 완성해 갑시다.