출처 검증됨레벨 4
쇼어 알고리즘
쇼어 알고리즘은 큰 정수를 다항 시간 O((log N)³)에 소인수분해하여, 최선의 고전적 알고리즘에 비해 지수적 속도향상을 제공하고 RSA 암호를 위협합니다.
무슨 뜻인가요
쇼어 알고리즘(1994)은 양자 푸리에 변환을 사용하여 소인수분해를 주기 찾기로 환원하여 다항 시간에 정수 N을 소인수분해합니다.이 알고리즘은 후양자 암호 연구의 동기가 됩니다.일상 비유
복잡한 악곡의 비밀 리듬을 찾는 것과 같습니다.
잠긴 금고의 공명 주파수를 찾는 것으로 생각하세요.
흔한 오해
- 모든 암호를 즉시 해독하는 것은 아닙니다.
- 현재 양자 컴퓨터로는 암호학적으로 의미있는 수를 인수분해할 수 없습니다.
핵심 정리
- O((log N)³)에 정수 인수분해 -- 지수적 속도향상.
- QFT를 사용한 양자 주기 찾기로 환원.
- 후양자 암호학의 동기.
이해했는지 확인해 보세요
쇼어 알고리즘이 정수 인수분해를 어떤 문제로 환원합니까?
- A.행렬 곱셈
- B.주기 찾기
- C.그래프 색칠
- D.정렬
정답 보기
정답: B. 주기 찾기
이유: 쇼어 알고리즘은 정수 인수분해를 QFT로 효율적으로 풀 수 있는 주기 찾기로 환원합니다.
먼저 알아야 할 개념
원 출처: Shor, SIAM J. Comput. 26, 1484 (1997), doi:10.1137/S0097539795293172
Hardware-status sentences ('current quantum computers cannot factor...') are explicitly era-qualified honesty statements protecting against hype; algorithm itself is established mathematics.