Einleitung

Einer der Algorithmen, der Quantum Computing auch außerhalb der direkt damit befaßten Forscher bekannt machte, war der Faktorisierungsalgorithmus von Shor, da dieser (wenn er denn einmal realisiert wird) dazu benutzt werden kann, viele heute gängige Kryptosysteme wie z.B. RSA zu brechen.

Die besten heute bekannten klassischen Algorithmen (Number field sieve) zur Zerlegung einer Zahl $n$ in ihre Primfaktoren haben eine Laufzeit von $O(e^{(\log n)^{1/3} (\log \log n)^{2/3}})$, während Shors Faktorisierungsalgorithmus auf einem Quantencomputer nur $O((\log n)^2 (\log \log n) (\log \log \log$ $n))$ (und zusätzlich $O(\log n)$ klassische Nachbearbeitung) benötigt. Er beruht auf folgenden Grundgedanken:

• Man kann mittels eines probabilistischen Algorithmus die Faktorisierung auf die Bestimmung der Ordnung in $\mathbbm{Z}_n$ (Miller 1976) reduzieren.
• Der Funktionsgraph von $a \mapsto x^a \bmod n$, den man zur Bestimmung der Ordnung benötigt, wird durch Quantenparallelismus gewonnen, so daß der aufwendigste Schritt in diesem Verfahren die Eigenschaften des Quantencomputers sehr gut ausnutzt.
• Die Periodenbestimmung dieses Graphen, d.h. das Herausrechnen des durch die Modulo-Operation entstandenen Offsets, wird mittels der auf Quantencomputern ebenfalls effizient durchführbaren diskreten Fourier-Transformation erreicht.

Diese Ausarbeitung des Promseminar-Vortrages beruht hauptsächlich auf [Sho97] (nahezu identisch mit [Sho94]), außerdem wurden einige Hinweise aus [EJ94] und [Ber97] ergänzt.

Betreut wurde ich von Pawel Wocjan, bei dem ich mich dafür herzlich bedanken möchte.