Diskussion:Shor-Algorithmus

aus Wikipedia, der freien Enzyklopädie

Inhaltsverzeichnis 1 Analogie zum Quadratischen Sieb 2 Fermatsche Pseudoprimzahlen 3 Noch nicht vollständig, aber ein sehr sehr guter Einstieg! 4 Fehler beim ersten Schritt des Quantenteils? 5 Warscheinlichkeit ein x mit ggT ungleich 1 zu finden (2. Schritt klassich) 6 Klassisch

[Bearbeiten] Analogie zum Quadratischen Sieb

Shor Algorithmus kann in gewisser Weise als Spezialfall eines anderen bekannten Faktorisierungsverfahrens dem Quadratischen Sieb betrachtet werden. Denn der Shor Algorithmus beruht wie das Quadratischen Sieb auf der Bestimmung von Zahlen a,b mit der Eigenschaft

a² = b² (mod n).

Beim Shor Algorithmus sind die Werte a,b wie folgt gewählt.

a = x^{r / 2} (mod n)

b = 1

[Bearbeiten] Fermatsche Pseudoprimzahlen

Der Shor Algorithmus kann - in leicht abgewandeter Form - angewendet werden, falls n eine Fermatsche Pseudoprimzahl ist. Dazu muss jedoch die Randbedingung, dass r die kleinste Zahl mit

x^r = 1 (mod n)

ist aufgegeben werden. Falls n eine Pseudoprimzahl ist, gibt es ein x, so dass für die Wahl r = n-1 gilt:

x^r = 1 (mod n)

Franz Scheerer

Der entscheidende Punkt fehlt leider noch in diesem Artikel Nopherox 14:58, 25. Feb 2005 (CET)

In der Diskussion zu diesem Artikel aber leider auch. Schluddi 22:41, 14. Mär 2005 (CET)

Ich schmeiß mich weg, darf man den unsinnigen Kram hier einfach löschen? Entweder Nopherox äußert sich da noch mal ein wenig konkreter oder aber diese Beiträge enthalten Null Informationen.

Entschuldigung für die Unklarheit. Ich habe den Artikel auf Überarbeiten gesetzt in der Hoffnung, dass jemand, der sich damit auskennt, darauf anspringen und den Artikel verbessern würde. Ich habe momentan zu wenig Zeit dazu und der Algorithmus ist ja nicht trivial. Die Diskussion kann doch einen unvollständigen Artikel nicht ersetzen. Vielleicht übersetzt mal jemand den englischen Artikel. Obwohl der (mir) an einigen Stellen auch nicht ganz verständlich ist, enthält er doch alle wichtigen Schritte.

Zur Frage, was noch fehlt: Der Algorithmus besteht aus einem klassichen Teil und einem Quanten-Teil. Der Quanten-Teil nutzt das Superpositionsprinzip von Quantenzuständen und deren Wahrscheinlichkeitsinterpretation zur möglichst wahrscheinlichen angenäherten Lösung einer periodischen Funktion. Das ist der springende Punkt, fehlt im Artikel aber vollständig. Dazu muss ein Haufen komplexer Arithmetik und Fourier-Transformation getrieben werden und man muss die Operatoren auf Quantenzuständen erklären. Von all dem wird lediglich in Punkt 4 des klassichen Teils wird eine Prozedur "Bestimmung der Ordnung" erwähnt, an der Stelle, wo der Quantencomputer gestartet werden müsste. Abgesehen davon erscheint mir auch der klassische Teil nicht ganz komplett. Man könnte nämlich mit klassichen Methoden zwischen Punkt 3 und 4 feststellen, ob die Zufallszahl x ein Teiler von N ist. Aber ich bin mir nicht sicher, ob das wesentlich ist. Nopherox 11:04, 20. Mai 2005 (CEST)

---

Wie schnell ist der Algorithmus? Polynomialzeit? --Matthäus Wander 15:20, 26. Jul 2005 (CEST)

[Bearbeiten] Noch nicht vollständig, aber ein sehr sehr guter Einstieg!

Ich finde den Artikel gut, auch wenn er nicht alle Fragen über die "Ordnung" r oder die "Quantenfouriertransformation" beantwortet. Der Link auf das Paper von Shor nützt nichts, weil man dort im Abstract weniger liest als hier. Das Original ist nicht downloadbar. Nehme daher an, daß der Verfasser dieses Wikipediaartikels das Original des Artikels zur Hand hatte. Die normale, gewöhnliche Fouriertransformation wird oft eingesetzt, um mit Differentialgleichungen einfacher zu rechnen. Es wird zwischen Funktionenräumen hin- und hergesprungen um mal für die eigentlichen, mal für die fouriertransformierten Fkt. bestimmte Rechen- operationen leichter ausführen zu können. "Ordnung" deutet auf zahlentheoretische Begrifflichkeit und hat eventuell mit Exponenten zu tun, wie oft man sie mit sich multiplizieren muss, um modulo -1 oder +1 Ergebnisse zu erhalten? Vielleicht die Anzahl der Elemente eines Orbits? Spekulieren dürfte man hier, ob die Überlagerung (Superposition) von quantalen Zuständen eventuell mit Integralen errechnet wird, die so ähnlich wie die Fouriertransformation aussehen und daher bestimmte "integrale Überlagerungen" sich einfacher berechnen lassen, weil sie in den Operationen der Quantenwelt schon zu Basisoperationen zählen und man durch geschicktes Nutzen dieser Verschränkung ein NP-hartes Problem von vielen Seiten gleichzeitig angehn könnte? Naja ich weiß es auch erst, wenn ich den Originalartikel irgendwie lesen konnte!

[Bearbeiten] Fehler beim ersten Schritt des Quantenteils?

Gehört beim ersten Schritt des Quantenteils nicht statt ? Ich bin kein Krypto-Spezialist, kann mich also auch irren. Aber es steht ja auch, dass q als Potenz von 2 bestimmt werden soll.

[Bearbeiten] Warscheinlichkeit ein x mit ggT ungleich 1 zu finden (2. Schritt klassich)

Ich seh auch nach mehrfachen vor- und zurückknobeln leider nicht ein, warum die Wahrscheinlichkeit ein passendes x für gegebenes n zu finden, mindestens 1/2 sein soll. Insbesondere nehme man eine große Zahl aus zwei Faktoren p und q (hier als Beispiel p * q = 17 * 23 = 391): Wenn man von 2 an versucht eine passende Zahl zu finden und nur die schon bekannten (woher auch immer) Primzahlen versucht, so bräuchte man trotzdem 2 -> 3 -> 5 -> 7 -> 11 -> 13 -> 17, also 7 Versuche bis zu einem passenden x. Jeder mag nun für zB n ~ 2^1000 selbst rechnen...

Sprich irgendwas an dieser Stelle ist nicht OK in der Beschreibung.

[Bearbeiten] Klassisch

Dass der von mir gesetzte Link auf 'klassische' Algorithmen geändert wurde, erscheint mir durchaus sinnvoll, jedoch ist der Begriff 'klassisch' im physikalischen Sinne als 'nicht-quantentheoretisch' ebenfalls angebracht. Diese Doppeldeutigkeit ist m.E. zumindest erwähnenswert. Allerdings weiß ich nicht, wie ich sie klug im Artikel untergebringen kann. -- R. Möws 19:35, 5. Jul 2006 (CEST)