다음 중 문제를 수론(number theory) 문제로 변환한 후 양자… | [법원직 9급 전산·사서 정보보호론] 26년 1회차 기출문제 상세 페이지
1[법원직 9급 전산·사서 정보보호론] 26년 1회차
다음 중 문제를 수론(number theory) 문제로 변환한 후 양자 컴퓨터를 사용하여 큰 정수를 효율적으로 인수분해하도록 설계된 알고리즘은?
1
그로버 알고리즘(Grover’s Algorithm)
2
쇼어 알고리즘(Shor’s Algorithm)
3
야오 법칙(Yao’s Principle)
4
확장 유클리드 알고리즘(Extended Euclidean Algorithm)
해설
큰 정수의 인수분해를 위해 설계된 양자 알고리즘은 쇼어 알고리즘이다.
쇼어 알고리즘은 인수분해를 수론의 주기 찾기 문제로 바꾼 뒤 양자 컴퓨터로 그 주기를 구한다. 그래서 RSA처럼 인수분해의 어려움에 기대는 암호의 위협으로 꼽힌다.
- 그로버 알고리즘은 인수분해가 아니라 정렬되지 않은 데이터의 탐색을 빠르게 하는 양자 알고리즘이다.
- 야오 법칙은 무작위 알고리즘의 복잡도 하한을 분석하는 원리이다.
- 확장 유클리드 알고리즘은 최대공약수와 모듈러 역원을 구하는 고전 알고리즘이다.
오류나 개정된 내용이 보이면 알려주세요