Upload
kasimira-neuberger
View
105
Download
2
Embed Size (px)
Citation preview
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