Faktorisierung einer Zahl mit Hilfe des Shor-Algorithmus


Bekanntlich beruhen moderne Verschlüsselungsverfahren wie RSA oder auch elliptische Kurven auf der Schwierigkeit, eine (sehr große) Zahl effektiv (d.h. in angemessener Zeit) in ein Produkt aus zwei echten Faktoren zu zerlegen. Vornehmlich (wegen der oben genannten Verschlüsselungsverfahren) für ein Produkt aus zwei verschiedenen Primzahlen gedacht, kann es aber auch als allgemeines Faktorisierungsverfahren eingesetzt werden.

Der  

Shor-Algorithmus vom amerikanischen Mathematiker und Informatiker Peter Shor (*1959) in den 1990er Jahren entwickeltes (Quanten-)Verfahren zur Faktorisierung einer Zahl
ist dazu in der Lage, setzt aber für eine effektive Berechnung eines Teilschrittes den Einsatz eines Quantencomputers voraus. Letztendlich ist er auch eine Spielart der Faktorisierungsmethode von Fermat. Letztere nutzt die Darstellung der Zahl N als Differenz zweier Quadrate, die allerdings nur für ungerade N in jedem Fall terminiert. Auch der Shor-Algorithmus terminiert für gerade N nicht in jedem Fall.

Es handelt sich beim Shor-Algorithmus um einen  

probabilistischen Algorithmusnutzt wie z.B. Monte-Carlo-Methoden zufällige Zwischenergebnisse für die Berechnung - im Gegensatz zu deterministischen Verfahren
. Sei N die in die Faktoren p und q zu zerlegende Zahl. Der Algorithmus lässt sich dann wie folgt beschreiben:


Shor-Algorithmus

  1. Wiederhole
  2.         Wähle eine zufällige Zahl 1<a<N
  3.         Gilt ggt(a,N)>1, dann Abbruch     (denn dann hat man schon einen Teiler gefunden)
  4.         Bestimme die Periodenlänge r von a Modulo N
  5. bis (ggT(a,N)=1) und (r gerade) und (ggT(ar/2+1,N)=1)
  7. p = ggT(ar/2-1,N)
  9. q = ggT(ar/2+1,N)

Erläuterung:

Bildet man eine Folge von Potenzen von a, also a0, a1, a2, a3 usw, und bestimmt deren Reste bzgl. einer zu a teilerfremden Zahl N, zeigt sich, dass die Reste eine periodische Folge bilden. Die Länge dieser Periode ist die zu bestimmende Periodenfolge r mit r < N.

Ein Beispiel: Sei N = p ⋅ q = 55 und a = 12

ggt(12,55)=1, also 12 teilerfremd zu 55.

Reste bestimmt man mit der modulo-Funktion.

12k 12k mod 35
120 = 1 1
121 = 12 12
122 = 144 34
123 = 1728 23
124 = 20736 1

Daraus erhält man die Periodenlänge r = 4. Außerdem gilt: die Periode beginnt immer mit 1 (wegen a0 = 1).

r ist kleinste Zahl (größer Null), für die gilt: ar ≡ 1 mod N.

Dann ist ar - 1 durch N teilbar   (denn ar-1 ≡ 0 mod N).

Demnach: ar - 1 = n ⋅ N = n ⋅ p ⋅ q     (n natürliche Zahl)

Außerdem ist ar - 1 = (ar/2 + 1) ⋅ (ar/2 - 1)    (3. binomische Formel)

Deshalb gilt: ar - 1 = (ar/2 + 1) ⋅ (ar/2 - 1) = n ⋅ N = n ⋅ p ⋅ q

Man erkennt, dass p ein Teiler von ar/2 + 1 und q ein Teiler von ar/2 - 1 ist. Mit Hilfe des euklidischen Algorithmus lassen sich p und q dann als Teiler von N und (ar/2 + 1) bzw. (ar/2 - 1) bestimmen.
Der Fall, dass einer einer der Faktoren (ar/2 + 1) oder (ar/2 - 1) durch das Produkt p ⋅ q teilbar ist, kann nicht eintreten. Einerseits ist ar/2 - 1 < ar - 1 und r ist die kleinste Zahl mit ar - 1 ≡ 0 mod N. Andererseits wird durch die Bedingung ggT(ar/2+1,N)=1 ausgeschlossen, dass der zweite Faktor durch das Produkt p ⋅ q teilbar ist.

Die Bestimmung der Periodenlänge ist mit heutigen Computern sehr (zeit)aufwendig, kann aber mit Quantencomputern effektiv gestaltet werden. Das Prinzip ist ähnlich der Fourier-Analyse in der Physik. Dort geht es um die Verwandlung eines akustischen (also zeitabhängigen) Signals in ein frequenzartiges Signal. Das Signal wird in eine Grundschwingung sowie deren Oberschwingungen zerlegt.


Simulation:


Produkt zweier (Prim)Zahlen: N =