쇼어 알고리즘 문서 원본 보기

{{위키데이터 속성 추적}}
'''쇼어 알고리즘'''(Shor's algorithm)은 [[소인수 분해]]를 빠르게 처리할 수 있는 [[양자 (에너지)|양자]] [[알고리즘]]이다. 수학자 [[피터 쇼어]]가 제안했다.<ref>김용주. [https://n.news.naver.com/mnews/article/030/0002620508?sid=105 양자 시대, 생각보다 빨리 온다]. 전자신문. 2017년 6월 28일.</ref> 쇼어 알고리즘을 사용하면 크기가 <math>N</math>인 수를 소인수 분해할 때 <math>O(\log^3 N)</math>의 시간과 <math>O(\log N)</math>의 저장공간이 필요하다. 쇼어는 이 업적으로 국제수학자회의에서 가우스상을 받았다.

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

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

== 같이 보기 ==
* [[렌스트라의 타원곡선 알고리즘]]
== 각주 ==
<references />

{{수론 알고리즘}}
{{토막글|컴퓨터 과학}}

[[분류:양자 알고리즘]]
[[분류:소인수 분해 알고리즘]]
[[분류:양자정보과학]]
[[분류:양자 후 암호]]