쇼어 알고리즘: 두 판 사이의 차이
내용 삭제됨 내용 추가됨
편집 요약 없음 |
편집 요약 없음 |
||
1번째 줄:
'''쇼어 알고리즘'''(Shor's algorithm)은 [[소인수 분해]]를 빠르게 처리할 수 있는 [[양자 (에너지)|양자]] [[알고리즘]]이다. [[피터 쇼어]]가 제안했다.<ref>김용주. [http://news.naver.com/main/read.nhn?mode=LSD&mid=sec&sid1=105&oid=030&aid=0002620508 양자 시대, 생각보다 빨리 온다]. 전자신문. 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 암호에서 실제로 사용하는 수백자리의 수를 소인수 분해하는 단계까지 이르기에는, 아직도 수많은 연구가 필요하다.
| |||