Shor-Algorithmus
Der Shor-Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Restklassenringe innerhalb der Zahlentheorie, der Mittel der Quanteninformatik benutzt. Er berechnet einen nichttrivialen Teiler einer zusammengesetzten Zahl und zählt somit zur Klasse der Faktorisierungsverfahren. Er ist einer der wichtigsten Quantenalgorithmen.
Der Algorithmus wurde 1994 von Peter Shor veröffentlicht, der damals bei den AT&T Bell Laboratories beschäftigt war. Die Arbeit trägt den Titel Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. Darin wird auch noch ein zweiter Algorithmus zur Berechnung des diskreten Logarithmus beschrieben, der ebenfalls als Shor-Algorithmus bezeichnet wird. Im Allgemeinen wird diese Bezeichnung jedoch für das Faktorisierungsverfahren verwendet.
- ↑ Peter W. Shor: Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. In: SIAM Journal on Computing. 26/1997, S. 1484–1509, arxiv:quant-ph/9508027