Kategorie

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 0      

shor algorithmus

sa sb sc sd se sf sg sh si sj sk sl sm
sn so sp sq sr ss st su sv sw sx sy sz

Shor-Algorithmus

Der Shor-Algorithmus ist ein Algorithmus zur Faktorisierung großer natürlicher Zahlen auf Quantencomputern: Nur auf solchen Geräten ist er effektiv.

Die Bezeichnung ist aber nicht eindeutig, denn Peter W. Shors bahnbrechende Veröffentlichung (aus dem Jahr 1994) enthielt zwei Algorithmen: einen Algorithmus zur Faktorisierung von ganzen Zahlen und einen zur Bestimmung von diskreten Logarithmen.

Allgemein meint die Bezeichnung aber den Algorithmus zur Faktorisierung von großen natürlichen Zahlen: Aus der Zahlentheorie ist bekannt, dass jede natürliche Zahl eine eindeutige Zerlegung in Primfaktoren besitzt. Diese Zerlegung zu finden ist schwierig, aus den Faktoren die Zahl durch Multiplikation herzustellen aber einfach. Diese Asymmetrie ist die Grundlage von modernen Verschlüsselungsverfahren wie RSA. Der Shor-Algorithmus zerstört nun diese Asymmetrie, denn er kann (auf einem Quantencomputer) Zahlen sehr effektiv faktorisieren. Damit stellt er eine Bedrohung für die heutige Kryptografie dar.

Die grundlegende Idee ist, dass man die Faktorisierung auf die Bestimmung der Ordnung zurückführen kann. Und diese Bestimmung lässt sich mit Hilfe der Quanten-Fourier-Transformation effektiv durchführen.

  • Eingabe: Eine zusammengesetzte Zahl .

  • Ausgabe: Ein nichttrivialer Faktor von .

  • Laufzeit: Gatteroperationen.

  • Erfolgswahrscheinlichkeit: O(1).

  • Ablauf:
Wenn gerade ist, gib als Ergebnis zurück.
  • Falls für Zahlen und , gib als Ergebnis zurück.
  • Generiere eine Zufallszahl mit
  • Benutze die Prozedur Bestimmung der Ordnung, um zu erhalten.
  • Wenn gerade ist und , dann berechne und . Wenn dabei ein Faktor von bestimmt wird, dann gib ihn zurück. Wenn nicht, dann ist der Algorithmus fehlgeschlagen (von vorn beginnen)

  • Impressum

    Datenschutzerklärung