쇼어 알고리즘

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색


쇼어 알고리즘 (Shor's algorithm)은 소인수분해를 빠르게 처리할 수 있는 양자 알고리즘이다. 피터 쇼어가 제안했다.

쇼어 알고리즘을 사용하면 크기가 N인 수를 소인수분해할 때 O(\log^3 N)의 시간과 O(\log N)의 저장공간이 필요하다.

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

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