Quantum Computing Hartmut Klauck Universität Frankfurt WS 05/06 21.11

Quantum Computing

Hartmut KlauckUniversität FrankfurtWS 05/0621.11.

Bestimmen der Ordnung über ZN

Gegeben seien natürliche Zahlen x, N, x<N

Ordnung r(x) von x in ZN:min. r0: xr =1 mod N

„Periode“ der Potenzen von x

Bestimmen der Ordnung über ZN

Quantenalgorithmus, um r(x) zu bestimmen?

Algorithmus von Shor findet r(x) in Zeit poly(log N)

trivialer klassischer Ansatz: berechne xi für i=1,...,r(x) ist ineffizient, da r(x)=N-1 möglich

Anwendung eines solchen Algorithmus

Faktorisierungsproblem: Gegeben natürliche, zusammengesetzte Zahl N finde einen nichttrivialen Faktor

Kann durch einen Algorithmus zur Ordnungsbestimmung gelöst werden !

Faktorisierung

Wenn ein nichttrivialer Faktor in polynomieller Zeit gefunden werden kann, kann die komplette Primfaktorisierung in polynomieller Zeit gefunden werden, da es zu N höchstens log N Primfaktoren gibt

polynomieller Zeit: in der Länge von N, d.h. log N

Naiver Algorithmus: teste alle Faktoren <N1/2, d.h. exponentielle Zeit

Bester bekannter klassischer Algo: Zeit exp( O ( log1/3 N loglog2.3N ) )

Warum Faktorisierung?

Das Problem [...] zusammengesetzte

Zahlen in ihre Primfaktoren zu

zerlegen ist eines der wichtigsten

und nützlichsten in der ganzen

Arithmetik. Die Würde der

Wissenschaft verlangt, dass

jedes Hilfsmittel zur Lösung solch

eines eleganten Problems kultiviert wird.

Warum Faktorisierung?

RSA-Verfahren [Z. Bsp. SSL im Internet] [Rivest Shamir Adleman] Alice möchte verschlüsselte Nachrichten empfangen Alice veröffentlicht einen öffentlichen Schlüssel,

behält für sich einen privaten Schlüssel Mit dem öffentlichen Schlüssel kann man

Nachrichten verschlüsseln, mit dem privaten entschlüsseln

Es scheint schwer zu sein, verschlüsselte Nachrichten ohne den privaten Schlüssel zu öffnen

RSA wird durch Faktorisierung gebrochen

RSA

Alice zieht zwei “grosse” Primzahlen p,q, berechnet N=pq

Alice wählt e, teilerfremd zu φ(N)=(p-1)(q-1)

Z*N : Gruppe der y aus [1,...,N-1] die

teilerfremd zu N sind, mit Multiplikation Alice berechnet d, das Inverse von e in Z*

N

[das ist einfach, weil Faktorisierung von N bekannt]

Öffentlicher Schlüssel: (e,N) Geheimer Schlüssel: d

RSA

Öffentlicher Schlüssel: (e,N) Bobs Nachricht sei x<N Verschlüsselte Nachricht: y=xe mod N Alices Dekodierung: yd =xed mod N ed=1 mod N, also ed=1+ kφ(N) Ergebnis also x1+kφ(N) =x¢x kφ(N) mod N

x2 Z*N, dann xkφ(N) =1 mod N, und daher

yd =x mod N Sonst: OBDA p teilt x, q nicht

x=0 mod p, also xed= 0 mod p, xq-1=1 mod qxφ(N) =1 mod N und xed=x mod q und mit chin. Restsatz auch xed=x mod N

Wenn ein Angreifer (Eve) faktorisieren kann, kann N in pq zerlegt werden, und d wäre nicht mehr geheim

Reduktion Faktorisierung auf Ordnungsfinden Eingabe natürliche Zahl N

1. Test ob N Primzahl, Ausgabe N2. Test ob N= ab für nat. Zahlen a,b>1,

Ausgabe a3. Test ob N gerade, Ausgabe 24. Wenn nein: N=p1

(1) pm(m) mit

m>1,(j)¸1

Reduktion Faktorisierung auf Ordnungsfinden N=p1

(1) pm(m) mit m>1,(j)¸1

Ansatz: Wenn man eine nichttriviale Lösung zu x2=1

mod N finden kann, dann kann ein Faktor von N berechnet werden

Wenn y aus [1,...,N-1] gezogen wird und teilerfremd zu N ist, dann ist die Ordnung r von y mit hoher Ws. gerade und yr/2 -1 mod N

yr/2 1 mod N Dann erfüllt x=yr/2 die Gleichung x2=1 mod N

und x ist nichttrivial

Reduktion Faktorisierung auf Ordnungsfinden Theorem V.1:

Sei N eine zusammengesetzte Zahl und x eine Lösung von x2=1 mod N mit1 < x < N-1. Dann sind nichttriviale Teiler von N: ggt(x-1,N) ggt(x+1,N)

Theorem V.2:Wenn N=p1

(1) pm(m) Primfaktorisierung, und x

uniform aus Z*N gezogen wird, dann ist

Prob[r(x) ist gerade und xr/2 -1 mod N] ¸ 1-1/2m-

1¸ 1/2

Reduktion Faktorisierung auf Ordnungsfinden Eingabe natürliche Zahl N

1. Test ob N Primzahl, Ausgabe N2. Test ob N= ab für nat. Zahlen a,b>1,

Ausgabe a3. Test ob N gerade, Ausgabe 24. Wenn nein: N=p1

(1) pm(m) mit

m>1,(j)¸1

Reduktion Faktorisierung auf Ordnungsfinden

4. N=p1(1) pm

(m) mit m>1,(j)¸1

5. Bestimme zufälliges x aus [1,...,N-1]. Wenn ggt(x,N) 1, dann Ausgabe ggt(x,N)

6. Bestimme Ordnung r von x in ZN

7. Wenn r gerade ist, und xr/2 -1 mod N, dann berechne ggt(x-1,N) und ggt(x+1,N)

8. Wenn nicht, dann wiederhole 5.-7.

Analyse:

Schritt 1 [Primzahltest] deterministisch in Zeit poly(log N) [AKS02][Test, ob ab für nat. Zahlen a,b; Test ob Primzahl]

Schritt 5: ggt(y,N) kann in Zeit O(L3) berechnet werden, Euklidischer Algorithmus

Schritt 6: per Reduktion Schritt 7: mit Wahrscheinlichkeit 1/2 Schritt 8: erwartet O(1) Wiederholungen

Bemerkung

Finden der Ordnung von x in ZN ist tatsächlich per Polynomialzeit-Reduktionen äquivalent zum Faktorisierungsproblem

Shors Algorithmus löst Ordnungsfinden bezüglich einer als Black Box gegebenen Potenzierungsfunktion

Theorem V.1

Theorem V.1:Sei N eine zusammengesetzte Zahl und x eine Lösung von x2=1 mod N mit1 < x < N-1. Dann sind nichttriviale Teiler von N: ggt(x-1,N) ggt(x+1,N)

Beweis:

x2=1 mod N ) (x-1)(x+1)=0 mod NN teilt (x-1)(x+1), x-1<x+1<N, daher 1<ggt(x-1,N)<N und 1<ggt(x-1,N)<N

Theorem V.2

Theorem V.2:Wenn N=p1

(1) pm(m) Primfaktorisierung

[alle pj 2] und x uniform aus Z*N gezogen

wird, dann istProb[r=r(x) ist gerade und xr/2 -1 mod N]¸ 1-1/2m-1

Hilfsmittel

Sei φ(N)=| Z*N|. Für jedes x2Z*

N gilt xφ(N)=1 mod N[Euler]

φ(p) ist gerade, wenn p prim Chinesischer Restsatz

Sei N=p1(1) pm

(m)

Für x1,...,xm gibt es genau eine Lösung x zux=xi mod pi

i) für alle i x zufällig ziehen entpricht x1,...,xm ziehen x2 Z*

N , xi2 Z*N(i) für alle i [N(i)=pi

(i)] ri sei Ordnung von xi in Ni

ri teilt r [Ordnung von x in ZN]: xr=1 mod N ) xi

r=xr=1 mod Ni

Theorem V.2

Lemma 1:Sei N=p, p2 prim. Sei φ(N)=| Z*

N|. D sei maximal so dass 2D Teiler von φ(N). Mit Wahrscheinlichkeit =1/2 teilt 2D die Ordnung r(x) eines zufälligen Elementes von Z*

N. Beweis: Z*

N zyklisch [weil p2], d.h. es gibt 1<g<N, so dass {gj mod N, j=1,..., φ(N)}= Z*

N Jedes x0 ist gk mod für ein k x zufällig ) k zufällig, gerade/ungerade mit

Wahrscheinlichkeit 1/2 k ungerade:

gkr(x)=xr(x)= 1 mod N ) φ(N) teilt kr(x), 2D teilt kr(x), teilt r(x)

k gerade: xφ(N)/2=gkφ(N)/2=(gφ(N))k/2=1k/2=1 mod N [Euler] ) r(x) teilt φ(N)/2 und somit teilt 2D nicht r(x)

Theorem V.2

N=p1(1) pm

(m) Primfaktorisierung. Mit Chinesischem Restsatz ist Wahl von x äquivalent zu Wahl von x1,...,xm aus Z*

N(i) für N(i)=pi

(i)

x=xi mod pi(i)Ordnung ri=r(xi) in ZN(i) teilt r

d maximal so dass 2d Teiler von r, analog di für ri

Lemma 2:Wenn r=r(x) ungerade oder r gerade und xr/2=-1 mod N, dann di=d für alle i.

Beweis: I) r ungerade nur, wenn alle ri ungerade, d.h. alle di=0 II) r gerade, aber xr/2 = -1 mod N

) xir/2 = -1 mod Ni

d.h. ri kein Teiler von r/2,ri Teiler von r, d.h. 2d teilt ri, somit di=d

D.h. 2d grösster Zweierpotenzteiler von r(xi) für alle i

Theorem V.2

Theorem V.2:Wenn N=p1

(1) pm(m) Primfaktorisierung [alle pj 2], und x uniform

aus Z*N gezogen wird, dann ist

Prob[r=r(x) ist gerade und xr/2 -1 mod N]¸ 1-1/2m-1

Beweis: Mit Chinesischem Restsatz ist Wahl von x äquivalent zu Wahl von

x1,...,xm aus Z*N(i) für N(i)=pi

(i)

x=xi mod pi(i)Ordnung ri=r(xi) in ZN(i) teilt r

di maximal so dass 2di Teiler von ri

Berechne Gegenwahrscheinlichkeit. Mit Lemma 2 sind alle di gleich Wahrscheinlichkeit ·1/2m-1 nach Lemma 1:

Setze d=d1. Für alle i=2,...,m sei Di max Zweierpotenzteiler von φ(Ni)Drei Fälle:

Di>d, dann di=Di mit Ws. 1/2 und dann auch did Di=d, dann di= d mit Ws. 1/2 Di<d, dann di = d niemals

Jedesmal [2,...,m] ein Faktor ·1/2 zur Gesamtwahrscheinlichkeit