이산 로그

• 영어 명칭: Discrete-Log
• 속도 향상: 초다항적
• 구현 코드: Classiq, Qrisp

임의의 $s$에 대하여 $b=a^s\mathrm{mod}N$을 만족하는 $n$비트 정수 $a$, $b$, $N$이 주어져 있다고 하자. 이 알고리즘은 $s$를 찾는다. 쇼어(Shor)가 보였듯이 [82], 이는 양자 컴퓨터에서 $\mathrm{poly}(n)$ 시간에 찾을 수 있다. 알려진 가장 빠른 고전 알고리즘은 $n$에 대해 초다항 시간이 걸린다. [82]에서 보인 비슷한 방법을 이용하여 양자 컴퓨터로 타원 곡선상의 이산 로그 문제를 풀 수 있음에 따라 타원 곡선을 이용한 암호 방식을 무력화시킬 수 있다.[109, 14]. 쇼어 알고리즘에서 최적화를 가한 알고리즘은 [385, 432]에 설명되어 있다. 이 초다항적 속도 향상은 반군 상의 이산 로그 문제에 대해서도 확장 되어있다 [203, 204]. 아벨 숨은 부분군을 참고.