Shor, Grove 알고리즘

I. 양자 알고리즘이 현대 암호에 미치는 영향

  • 중첩, 얽힘, 불확정성 양자특성 기반 Shor와 Grove 알고리즘이 현대 암호학에 큰 영향

II. Shor 알고리즘

절차도절차 설명
① 인수분해 대상 N 보다
작은 m 선택하여,
m, N 최대공약수 계산
② m6 mod n 의 주기 P 계산
③ p가 홀수이면 ①로 이동
짝수이면 ④로 이동
④ (mp/2 – 1)(mp/2 + 1)
= m– 1 = 0 mod N
mp/2 + 1 = 0 mod N 시 ①로
⑤ mp/2 – 1와 N 최대공약수
  • 두 번째 단계 ②가 양자 푸리에 변환 사용 단계로, 인수분해 문제가 고전 컴퓨터와 달리 해결 가능

III. Grove 알고리즘




① Hadamard gate(H) 이용 시스템 동일 중첩 상태 만듦
② Quantum oracle이라 불리는 부분 통과해 찾고자 하는 원소에 맞게 시스템 변화
③ diffusion transform 통해 위상이 평균보다 큰 경우 평균보다 낮게 변화, 평균보다 낮은 경우 크게 변화
④ classical measurement로 결과 평가하여 O(1)의 확률로 옳은 값 출력
  • Grover 알고리즘은 정렬되지 않은 데이터베이스 원소를 찾는 양자 알고리즘, 고전 컴퓨터로 N개의 원소 중 하나 찾으려면 O(N) 검색 필요, Grover 알고리즘은 O(N1/2) 검색으로 찾음
4 Comments

콘텐츠 사용 시 출처 표기 부탁 드리고, 댓글은 큰 힘이 됩니다^^