Kvantum‐prímfaktorizáció Gyöngyösi László BME Villamosmérnöki és Informatikai Kar
Támadás kvantumszámítógéppel
Egy klasszikus algoritmusnak egy U unitér transzformáció feleltethető meg. Minden klasszikus algoritmus megvalósítható unitér transzformációval egy kvantumszámítógépben A szuperponált kezdőállapot segítségével pedig párhuzamosan végrehajtható az előírt művelet az összes lehetséges bemenő adatra A műveletvégrehajtás teljes mértékben párhuzamosan történik
A kvantumhálózat működésének elméleti alapjai
A kvantumszámítások során kihasználható kvantumjelenségek: Szuperpozíció Összefonódott
állapotok Hullámfüggvények interferenciája Az elosztott kvantumszámítógép-hálózatban felhasználható jelenségek: EPR
állapotok Kvantum-teleportáció Kvantum-párhuzamosság
Kvantumalgoritmusok
Mennyire kell tartanunk a kvantumszámítógépek támadásától?
Peter Shor prímfaktorizációs algoritmusa
A faktorizációval szemben, az LNKO megtalálására ismert gyors, klasszikus algoritmus Egy olyan szám megtalálását, amelynek a fölbontandó számmal van közös osztója, átfogalmazhatjuk egy függvény periódusának meghatározására Klasszikus rendszerben nehéz feladat, viszont a perióduskeresésre gyors kvantum-algoritmust lehet találni.
Az RSA feltörése egy 1600 klasszikus számítógépből álló hálózatnak 8 hónapig tartott. Ugyanezen feladat egyetlen kvantumszámítógépnek csupán másodperces időt vett igénybe.
Az RSA algoritmus
Az RSA algoritmus Legyen N pq két nagy prímszám szorzata, ahol p és q prímszám hossza is n egyaránt bit. Az így előállított N az RSA modulusa. Napjainkban N átlagos 2 hosszúsága n 1024 bit , ami 309 decimális jegyet jelent. A két prímtényező pedig 512 bit hosszú. Az RSA kezdeti időszakában még az n 128 bites modulus is biztonságosnak bizonyult, majd éppen a támadások és a technika fejlődése hatására, a biztonságot a számok nagyságának emelésével igyekeztek biztosítani. Így lett az RSA modulus hossza 256, 512, majd 1024 bit. Az Euler-Fermat tétel alapján tudjuk, hogy x (N) 1 (mod N) , ahol ( N ) az Euler függvény, ami az N redukált maradékosztályainak számát adja meg, másképpen az N -nél kisebb, N -hez képest relatív prímek számát.
Az RSA algoritmus Ha N két prím szorzata, akkor ( N ) a következőképpen határozható meg:
( N ) ( p 1)(q 1). A nyilvános kulcs egy tetszőlegesen választott e szám lesz, - ami a gyakorlati alkalmazásokban a gyors számíthatóság érdekében általában 216+1=65537,amelyhez meg kell határozni a titkos kulcsként szolgáló multiplikatív inverzét d -t, a mod ( N ) aritmetika használatával:
ed 1 mod ( N ). Az alapul szolgáló nehéz probléma garantálja, hogy a nyilvános kulcs (e), valamint az ismert modulus (N) ismeretében egy harmadik fél nem tudja meghatározni a titkos kulcsot (d), hiszen ehhez ismernie kellene ( N ) értékét, amit viszont N prímfaktorai (p és q) ismeretében tudna csak egyszerűen meghatározni.
Az RSA algoritmus Azonban egy megfelelően nagy egész számot prímtényezőire bontani (p-t és qt meghatározni) nehéz feladat. A gyakorlatban a titkos és nyilvános kulcsok mellett feltüntetjük a modulus értékét is, hiszen ez a kulcs-párra jellemző és szükséges a későbbi számításokhoz is. Így tehát a kulcsok:
Nyilvános kulcs: (e, N ) Titkos kulcs: (d , N ) Ahol e-t nyilvános exponensnek, d-t pedig a privát (titkos) exponensnek nevezzük.
Az RSA algoritmus Kódolás Az elküldeni kívánt üzenetet egy N-nél kisebb egész szám (x) reprezentálja. (ez feltétel az algoritmus működéséhez). Az x üzenetet tehát tekinthetjük egy egész számnak, amelyre teljesül, hogy 0 x N . Abban az esetben, ha a tényleges üzenet ennél hosszabb, akkor az üzenetet blokkokra osztjuk, amelyek teljesítik e feltételt. A kódolt üzenet szintén egy N-nél kisebb egész szám lesz (y). A kódoláshoz a küldő fél a címzett nyilvános kulcsát használja, a kódolt üzenetet a következő képlettel számolja ki:
y x (mod N ). e
Az RSA algoritmus Dekódolás Az üzenet visszafejtéséhez a fogadó fél saját titkos kulcsát használva a következő számítást végzi:
c y =x =x (mod N ). d
ed
Az így kapott c érték pontosan az elküldött üzenet, x lesz, mivel ed 1 mod ( N ) , azaz
cx
.
Az RSA algoritmus A kódolásnál azt is biztosítani kell, hogy x és N relatív prímek legyenek, azaz – mivel N pq , így az x nem lehet osztható sem p-vel, sem q-val. Gyakorlatilag azonban annak az esélye, hogy x beletalál a prímtényezők valamelyik többszörösébe, körülbelül annyi, mintha a titkos kulcsot valaki próbálgatással eltalálná, azaz rendkívül kicsi. (Éppen ezért a gyakorlati életben ezt a kritériumot el szokták hanyagolni.) Az RSA tehát egy egyirányú függvény, amely adott d esetén könnyen invertálható az előzők alapján, azonban a privát kulcs ismerete nélkül ez nagyon nehéz. Az RSA feltörése pontosan arra irányul, hogy d ismerete nélkül kell invertálni az RSA függvényt.
Az RSA algoritmus Kulcsgenerálás A kulcsgenerálás során határozzuk meg mind a titkos-nyilvános kulcspárt, mind a használt modulust. A paramétereket (p, q, e) úgy kell megválasztani, hogy az ismert, speciális esetben működő támadási módszereket kiküszöböljük. Ezeknek megfelelően a választás irányelvei:
p és q legyen nagy; egyenként legalább 512 bitesek (ha van az N-nek lenne kis prímtényezője, akkor létezik hatékony támadás) (p-q) is legyen nagy; legalább 511 bites (ha kicsi, létezik támadás) p és q legyen véletlenül választott e legyen relatív prím ( N ) -hez (ez az algoritmus működéséhez szükséges) e ne legyen kicsi (ha e kicsi, akkor létezik támadás) d ne legyen kicsi (ha d kicsi, akkor létezik támadás) Több kulcs generálása esetén ne használjuk ugyanazon modulust.
RSA példa
Az RSA algoritmus Tegyük fel, hogy az RSA kulcsgenerálás során már megválasztottuk a két prím összetevőt, p-t és q-t, valamint a nyilvános kulcshoz szükséges, kitevőt e-t. A paraméterek ismeretében először meghatározzuk az N modulust, az ( N ) Euler-Fermat függvény értékét, majd a titkos kulcs kitevőjét, d-t:
p 13, q 17, e 101. N ?, ( N ) ?, d ? N modulus meghatározása:
N pq 13 17 221. ( N ) meghatározása:
( N ) ( p -1)( q -1) 12 16 192.
Az RSA algoritmus A d-t úgy kell megválasztanunk, hogy ed 1 mod ( N ) legyen. Ezért az Euklideszi algoritmus segítségével meghatározzuk a ( N ) és e legnagyobb közös osztóját, aminek 1-nek kell lennie, hiszen kikötés, hogy ( N ) és e relatív prímek legyenek. e 192 1 101 91 101 1 91 10
91 9 10 1. Az algoritmus végrehajtásával azonban megkaphatjuk az 1-et, azaz a legnagyobb közös osztót a 101 (e) és a 192 ( ( N ) ) lineáris kombinációjaként, és így már kiszámítható d: Az utolsó sorból kifejezzük az 1-et:
1 91 - 9 10
Az RSA algoritmus A 10 101 - 1 91 behelyettesítésével:
1 = 91 - 9 (101 - 1 91) A 91 = 192 - 1 101 behelyettesítésével:
1 = 10 91 - 9 101 A 91 = 192 - 1 101 behelyettesítésével:
1 = 10 (192 - 1 101) - 9 101 Azaz: 1 = 10 192 - 19 101 . Ha most mindkét oldalnak vesszük a 192-vel ( ( N ) -nel) vett osztási maradékát, akkor azt kapjuk, hogy: 1 -19 101 (mod 192) , ami 192-19 = 173 miatt átírható pozitív számokra: e
1 173 101 (mod 192)
Az RSA algoritmus e Ebből, illetve az ed 1 mod ( N ) összefüggésből, azaz 1 d 101 (mod 192) kifejezésből azt kapjuk, hogy d 173. Tehát a (választott p=13, q=17 prímszámokkal a fenti algoritmus szerint előállított) nyilvános kulcs (N=221; e=101), a titkos kulcs pedig (d=173).
Tegyük fel, hogy az x=70 nyílt üzenetet akarjuk kódolni. Ekkor a kódolás művelete: y = 70101 (mod 221) = 83. Azaz y=83 lesz a kódolt üzenet. A dekódolás: x = 83173 (mod 221) = 70.
Támadási lehetőségek
RSA elleni támadási módszerek
Az RSA elleni támadásokat az alábbi csoportokba fő sorolhatjuk:
Implementációfüggő támadások
Kulcskereséses támadás Számítási idő mérése
Helytelen alkalmazáson alapuló támadások
Közös modulus Kis privát exponens
Új támadási lehetőség becslésével Az RSA támadás a Fermat egyik tételével
A modulus faktorizációján alapuló támadások
Faktorizáció alapú támadás
Az RSA biztonságának kulcsa az, hogy az összetett számok faktorizálása az eddigi tudásunk alapján „nehéz” feladat A faktorizáláshoz szükséges lépésszám a faktorizálandó szám jegyeinek számával exponenciálisan nő, és ez igaz még a leghatékonyabb klasszikus faktorizáló algoritmus esetében is.
Matematikailag azonban nincs bizonyítva az, hogy nem létezik hatékony klasszikus algoritmus, amely a számjegyek számától polinomiálisan függő lépésszámban oldaná meg a faktorizációt.
A jelenleg széles körben használatos nyilvános kulcsú RSA titkosítás két nagy prímszám szorzatának gyors faktorizálásának megoldhatatlanságán alapul. Emiatt igen nagy érdeklődést keltett, amikor 1994-ben Peter Shor közzétett egy olyan kvantumalgoritmust, amely polinomiális idő alatt oldja meg a faktorizációt.
Faktorizáció alapú támadás
Az elméleti RSA támadások legelterjedtebb csoportja tehát ez, amelyben a támadás a publikus kulcs ismeretében (e) az N modulus faktorizálására irányul
N osztóinak ismeretében a támadó könnyen kiszámíthatja ( N ) -t, és ennek ismeretében a privát kulcs is adódik
d e mod ( N ) 1
Faktorizáció alapú támadás
A modulus faktorizációján alapuló támadások műveletigénye a modulus hosszának exponenciális függvénye, így elég nagy modulus esetén, a gyakorlati feltörés irreális időigényű lehet. A jelenlegi leggyorsabb faktorizációs algoritmus az 1993-ban publikált Number Field Sieve algoritmus. Az RSA Security által meghirdetett faktorizációs versenyen is ezzel az algoritmussal érték el a rekordot, ami egy 512 bites szám osztóinak a megkeresése volt.
Faktorizáció alapú támadás
Az RSA feltörése prímfaktorizációs algoritmussal
1) Vegyük az FN ( x) a x mod( N ), ahol x 0,1, 2,... függvényt, amelyben a egy 0 és N közötti tetszőleges természetes szám. Az FN ( x) függvényről tudjuk, hogy periodikus. 2) Miután a FN ( x) függvény periodikus, meghatározzuk az r periodust: FN ( x) FN (b k r ), ahol k 0,1, 2, ... 3) Legyen M1,2 a r /2 1 4) Határozzuk meg N és M 1 legnagyobb közös osztóját (P1 ), valamint N és M 2 legnagyobb közös osztóját (P2 ). 5) P1 és P2 az N prímtényezői lesznek, illetve a prímtényezőinek szorzata.
Szorzattényezőkre bontás A szorzattényezőkre bontás bármilyen függvény esetében végrehejtható. Legyen N=273, ( 7 x39, most 39 nem prím) valamint a értékét válasszuk 23-nak. Ekkor a függvényünk alakja a következő: F273 ( x ) 23x mod(273).
Nézzük meg, hogy egyes értékekre milyen értéket vesz fel a függvény. x
0
1
2
3
4
5
6
7
8
9
10
11
12
13
…
F(x)
1
23
256
155
16
95
1
23
256
155
16
95
1
23
…
A függvény értéke periodikusan ismétlődik
Szorzattényezőkre bontás
A feladat ezután a függvény r periódusának a meghatározása, azaz:
F273 ( x) F273 ( x k r ) mod(273), ahol k 0,1, 2,...
A függvényünk periódusa 6, így
F273 ( x) F273 ( x k 6) mod(273), ahol k 0,1, 2,...
Ahonnan
M1 236/2 1 12168; M 2 236/2 1 12166.
Faktorizáció alapú támadás
Ebből az Euklideszi-algoritmussal: d (12168, 273) 39; d (12166, 273) 7.
Azaz, Így,
P1 39; P2 7.
N P1 P2 273 39 7. A kapott eredmények valóban az N osztói, N P1 P2 , azaz 273 39 7.
Faktorizáció alapú támadás klasszikus rendszer esetén
A végrehajtás kritikus része az r periódus meghatározása. A legnagyobb közös osztók megtalálása az Euklideszialgoritmus alapján pedig polinomiális lépésszámban könnyen elvégezhető.
A periódus keresésének lépésszáma azonban N jegyeinek számával exponenciálisan növekszik, azaz ugyanolyan bonyolultságú, mint más - akár az egyszerű próbálgatásos - faktorizációs algoritmus.
Kijelenthetjük tehát, hogy klasszikus rendszerekben a feltörés gyakorlatilag lehetetlen.
A kvantumtámadás menete
Támadás kvantumszámítógéppel A prímfaktorizációt végző kvantumáramkör
Támadás kvantumszámítógéppel Amíg a prímfaktorizáció klasszikus rendszerekben exponenciális, addig kvantumos rendszerekben négyzetes növekményű végrehajtási időt igényel.
Az algoritmus, a faktorizálandó szám moduláris hatványainak periodicitási tulajdonságát kihasználva – kvantumregisztereken végzi el a prímtényezőkre bontást.
Klasszikus memóriacímzés kvantumbitekkel A klasszikus adatokat (az a moduláris hatványait) tartalmazó memóriacellák megcímzése szuperpozíciós állapotokkal is
Támadás kvantumszámítógéppel Az FN (x)=a x mod(N) függvény megvalósításához a tárolást egy kvantumregiszterrel valósítjuk meg, amely regiszter álljon n darab kvantumbit-ből. A kvantumregiszter jelölése: A - regiszter. Az n darab kvantumbit felhasználásával a kvantumregiszterben állítsuk elő 0 -tól 2n -1 -ig az összes természetes szám szuperpozícióját! A kvantumregiszterben a szuperpozíció előállítását a Hadamard-operátor segítségével tehetjük meg, amely létrehozza a
2n -1
1 n
2
x x=0
állapotot.
Támadás kvantumszámítógéppel Az A-regiszterben tárolt x értékeket felhasználva, hajtsuk végre az FN (x)=a x mod(N) függvénynek megfelelő operációt, a kapott eredményeket tegyük egy újabb kvantumregiszerbe! Miután a művelet elvégzéséhez két regisztert használtunk, így a két regiszter tartalma: 2n -1
x x=0
FN (x) .
Támadás kvantumszámítógéppel A következő lépésben a B - regiszterben eltárolt értékekhez kell valahogyan hozzájutnunk. Erre egyetlen lehetőségünk van: mérést kell végrehajtanunk. A kvantumregiszteren tehát egy mérést kell végrehajtanunk, amely a kvantumelméleti axióma alapján a B - regiszter tartalmát, azaz állapotát véletlenszerűen valamelyik konkrét FN* állapotba viszi.
Támadás kvantumszámítógéppel Az A-regiszterben azonban csak azon x * állapotok szuperpozíciója lehet, amelyekre igaz az, hogy FN ( x * ) FN* , azaz x * b0* k r. ahol k=0,1,2,... , valamint b0* azon legkisebb természetes szám, amelyre FN (x 0* )=FN* . Azaz, a B-regiszeren elvégzett mérés során kapott véletlenszerű FN* érték egy véletlenszerű értéket rendel az x 0* -hoz, azonban az A-regiszerben kialakult szuperponált állapot mindenféleképpen r periódusú lesz.
Támadás kvantumszámítógéppel Az A-regiszteren ezután kvantum Fourier-transzformációt hajtunk végre, amelynek eredménye a keresett r érték lesz. Az r birtokában az N szám osztói, P1 és P2 már meghatározhatóak.
Támadás kvantumszámítógéppel 2.
1.
A kiindulási helyzetben mindét regisztert, azaz az X és Y regisztert értékkel inicializáljuk. A két regiszter kiindulási állapota ekkor: 0, 0
Ezután az X regiszter tartalmát
.
szuperpozíciós állapotba hozzuk
Támadás kvantumszámítógéppel
3.
4.
Az X regiszter tartalmának felhasználásával előállítjuk az
A következő lépésben az X regiszteren végrehajtjuk a Fourier transzformációt.
A Fourier transzformáció végrehajtása után, a y0* mk állapotok esetén, a periódust meghatározó tagok értéke 1 lesz. A tagok összege pedig éppen k.
Azaz, az X regiszteren végrehajtott Fourier transzformáció után megkapjuk k értékét.
f ( x) a x mod( N ) értékeket, és az értékeket az Y regiszterben tároljuk el. A rendszerünk állapota a két regiszter direkt szorzata lesz.
Az Y regiszterből történő kiolvasáshoz mérést kell végeznünk. A mérés után, az X regiszterben csak r periódusú állapotok maradnak, hiszen csak ezen értékekre teljesül a mért f(x) függvény.
A kvantum-Fourier transzformáció előtti állapot Valószínűség
r r t 2 (A regiszter)
r b0
b0 3
r 2t
2t r
a 0
2r b0 ar b0 x b0
Támadás kvantumszámítógéppel 5.
Végül elvégezzük a mérést az X regiszteren.
Az X regiszterben, a Fourier transzformáció után csak olyan értékek maradtak, amelyek k többszörösei:
2n y mk m, ahol k 2n / r. r * 0
Az r birtokában az N szám osztói, P1 és P2 már meghatározhatóak.
A kvantum-Fourier transzformáció utáni állapot
Valószínűség
2t r
1 r
(A regiszter)
2t r
2 2t r
Erőforrásszükséglet
A Kvantum Fourier transzformáció végrehajtása során csak olyan kvantumkapukat használtunk, amelyek transzformációja unitér, így a teljes Kvantum Fourier Transzformáció is unitér.
A transzformáció végrehajtásához szükséges kapuk száma:
1 2 n
n n 1 2
A transzformáció végrehajtása utáni átfordításhoz kell még n/2 darab SWAP kapu.
Erőforrásszükséglet
A kvantum-Fourier transzformáció végrehajtáshoz szükséges kapuk száma nagyságrendileg
O n
2
O log N
2
Klasszikus rendszerben
O n2 n ahol N 2 .
n
O N log N
Erőforrásszükséglet
Példa:
50 bit esetében, egy klasszikus rendszerben elvégzett Fourier transzformáció lépésszáma:
N log N 50 log 50 85
Ugyanez, egy 50 kvantumbites rendszer esetén:
log N
2
log 50 2.8864 3 2
Azaz, egy klasszikus rendszerbeli 2n-1 lépésszámú művelet, egyetlen lépésben elvégezhető egy kvantumrendszer esetében.
A prímfaktorizációs kvantumalgoritmus tulajdonságai
Exponenciális helyett polinomiális időszükséglet
rendszer – Ο 2n lépés 3 Kvantum rendszer – n lépés Klasszikus
Példa: 300 számjegy – 106 év 1000 számjegy – 1025 év
néhány óra
A kvantum Fourier transzformáció
Fourier transzformáció Adatsorok, függvények viselkedésének jellemzésére Fourier-transzformáció egy nagyon hatékony eszköz
a
A Fourier transzformáció elsősorban akkor hasznos igazán, ha a vizsgált függvényünk különböző frekvenciával változó, harmonikus függvények összege. A különböző frekvenciával változó harmonikus függvények szinuszos vagy koszinuszos függvények lehetnek, vagy ahhoz közelítenek. A Fourier transzformáció alkalmazásával az egyes, különböző periódusú komponensek súlyát adhatjuk meg. A Fourier-transzformációra egy egyszerű A Fourier transzformációt számos helyen alkalmazzák a modern, elektronikus kommunikációs eszközökben is
Fourier transzformáció Egy periodikus függvény szinuszos és koszinuszos tagok lineáris kombinációjaként történő felbontását Fourier-sornak nevezzük. Bármilyen periodikus, folytonos függvény felírható szinuszos és koszinuszos tagok lineáris kombinációjaként. A kvantumszámításoknál is alkalmazhatjuk a Fourier sorfejtést: a 0 és 1 egy ortonormált bázist alkot, a szinuszos és koszinuszos tagok pedig az
időtartományban alkotnak ortonormált bázist, a hullámfüggvény esetében. A Fourier sor általános alakja a következő:
a0 f t an sin nt bn cos nt 2 n 1 n 1 Ha egy hullámformát szeretnénk leírni, akkor szükségünk lesz a szinuszos és koszinuszos tagokhoz tartozó a0 , a1 , , an és b0 , b1 , , bn együtthatók értékeire
Fourier transzformáció Tegyük fel, hogy megtaláltuk a következő együtthatókat: a1 0.5, a4 2 és b2 4 , az összes többi együttható értéke nulla. Ebben az esetben a Fourier sor a következőképpen adható meg:
f t 0.5sin t 2 sin 4 t 4 cos 2 t . A függvény alakja a következő:
Fourier transzformáció Az f t függvény egyes alkotórészekre bontva a következő:
Az egyes frekvenciák és amplitúdók elemezéseután :
2sin 4 t
Szinuszos amplitúdó 1 2 2
0
1 2 2
4 cos 2 t
0
4
1
Hullámfüggvény
0.5sin t
Koszinuszos amplitúdó 0
frekvencia
Fourier transzformáció A DFT egy diszkrét, periodikus tk időtartománybeli sorozatból állítja elő a frekvenciatartománybeli diszkrét sorozatot. A DFT függvény által előállított kimenete egy komplex tömb. A tömbben lévő elemek számát a mintavételezési frekvencia, és a hullámforma hossza határozza meg. Azaz, az N darab t0 , , t N 1 komplex szám N darab komplex számmá transzformálódik a f 0 , , f N 1 függvények segítségével, a következőképpen: N 1
f j tk e k 0
2 i jk N
,
ahol j 0, , N -1.
Fourier transzformáció A DFT invertálható mátrixxal rendelkezik, így a DFT inverze is elvégezhető, amelyből megkapjuk az időtartománybeli értékeket. Az inverz Fourier transzformáció alakja:
1 tk N
N 1
fe j 0
j
2 i jk N
,
ahol k 0, , N - 1
A szinuszos és koszinuszos tagokat tehát elő kell állítanunk komplex, exponenciális alakban. A sorozatunk diszkrét, ezért csak bizonyos pontokat mintavételezünk, a mintavételezési frekvencia pedig a mintavételezés pontosságát határozza meg.
Fourier transzformáció A kvantum-Fourier transzformáció a következőképpen adható meg:
1 F: x N
i 2 xy exp y . N y 0 N 1
Ahol x bináris szám, amelynek alakja x x1 2
n 1
x2 2
n2
n
xn 2 2n 1 , és itt 0
l 1
n azon legkisebb egész szám, amelyre igaz, hogy N 2 . n
Ezen x bináris számot n darab kvantumbiten ábrázoljuk, azaz x x1 x2 xn , ezek a vektorok pedig egy N dimenziós tenzori szorzattér bázisvektorai, ez tehát a számítási bázis. A számítási bázisunk ábrázolásához egy n bites kvantumregiszter szükséges. A fenti kifejezés tehát átírható a következőképpen:
F: x
i 2 xy exp n y . n 2 2 y 0
1
2n 1
Fourier transzformáció Ahol tehát xy egy „normál” szorzásnak kvantumregiszterekkel valósítjuk meg:
felel
meg,
amely
szorzást
x xn 1 xn 2 x0 , y yn 1 yn 2 y0 . Az
xk
és
yk
egymástól független kvantumbitek. A kvantum Fourier
transzformáció egy unitér transzformáció, és ez egy szorzatfelbontás révén is igazolható: N 1
N 1
x 0
x 0
F : cx x Mivel
1 c y F cx N
N 1 N 1 1 i 2 xy cx exp y c y y . N y 0 N y 0
i 2 xy exp cx , ahol y 0,1 N 1 , N x 0 N 1
így a kapott eredmény a cx együtthatók Fourier transzformáltja.
A QFT áramkör felépítése
Kvantum Fourier-transzformáció H a Hadamard kapu, R d pedig a fázisfordító kapu, ami ebben az esetben a következőképpen adható meg:
0 1 Rd 0 ei / 2d
.
Ahol d az egyes bementi kvantumbitek indexe közötti távolságot jelenti.
Kvantum Fourier-transzformáció Az áramkör működésének részletezése 1. Az
x2
kvantumbit a Hadamard kapuba lép be elsőként, ennek
eredményeként kialakul a ahol e2 i0, x1 Azaz:
1 2
1
1
e
2 i0, x2 y / 2
1
1
0
e 2 i0, x2 1 , ahol
2 y 0 2 1 , ami attól függ, hogy a bemeneten x2 0 vagy x2 1 volt. 1
e y 0
2 i 0, x2 y /2
1
1 2
1
(1) y 0
y 0, x2
1 .
Ahol (1) y0, x2 értéke attól függően 1 , hogy a bemeneti kvantumbit értéke 0 vagy 1.
Kvantum Fourier-transzformáció A következő lépésben az R1 kapu aktivizálódik, ami a következő transzformációt hajtja végre a bemenetként kapott állapoton:
0 1 R1 . i / 2 0 e Az R1 kapu célbitje, -azaz amelyik kvantumbiten a változtatást végrehajtjukbemeneti kvantumbit x2 , a kontrollbit pedig
x1 . Az R1 kapu tehát a következő
transzformációt hajtja végre:
1 2
0
e
2 i 0, x2
az a
0 1 1 1 i / 2 0 e 2
0
e 2 i0, x2 ei x1 / 2 1 .
Kvantum Fourier-transzformáció Az R1 kapu hatása tehát a következő a bemeneti állapotra, a kontrollbit figyelembevételével:
R1 x1
1 2
0
= x1 = x1
e 1 2 1 2
2 i 0, x2
1 x1
1 2
0
e2 i (0, x2 / 2 0, x1 / 4) 1
0
e2 i (0, x1x2 ) 1 .
0
Felhasználtuk az előzőekben kapott eredményünket: x x 0, xn 1 xn n 1 n , így az egyszerűbb jelölés miatt 2 4 2 i (0, x1 x2 ) -t, a fenti kifejezésben. használtunk a e
e2 i0, x2 ei x1 / 2
Kvantum Fourier-transzformáció A QFT kvantumáramkör következő kapuja az R2 . Kontrollbit: x0 . A transzformáció tulajdonságai nem változtak, azaz ugyanúgy érvényesek az előző pontban felállított feltételek:
0 1 R2 . i / 4 0 e Azaz, a fázisfordítás ezúttal ei / 4 , az előző ei / 2 helyett!!
Kvantum Fourier-transzformáció A teljes rendszer leírásához azonban most nem elég csupán az aktuális kontrollbitet figyelembe venni, mivel az előző transzformáció x0 eredményét adjuk bementként az R2 kapura, ahol viszont a kontrollbit az x1 volt, így:
1
R 2 x0 x1 x0 x1 = x0 x1 = x0 x1
2 1 2 1 2 1 2
0
e
2 i (0, x1 x2 )
Használt jelölés:
1
0
.e 2 i (0, x1x2 ) ei x0 / 4 1
0
e 2 i ( x0 / 8 x1 / 4 x2 / 2 1
0
e 2 i (0, x0 x1x2 ) 1 .
xn 1 xn 0, xn 1 xn 2 4 =
e 2 i (0, x1x2 )
Kvantum Fourier-transzformáció Végül, ismét egy Hadamard transzformáció következik, ami az x0 kvantumbiten kerül végrehajtásra, aminek eredménye:
1
0
2 kvantumrendszerünk végső állapota a következő lesz :
1
x0 1 2
2
0
e
2 i (0, x0 x1 )
0 e 2 i0, x0 1
Ahol 0, xn 1 xn
xn 1 xn = e 2 i (0, x1x2 ) . 2 4
1 1 2
1 2
0
e 2 i0, x0 1 . Így a teljes
e 2 i (0, x0 x1x2 ) 1
0 e 2 i (0, x0 x1 ) 1
1 2
0
e 2 i (0, x0 x1x2 ) 1 .
A kvantum prímfaktorizációs algoritmus lépései
Kvantum prímfaktorizáció
Va x y x a x y
x : A regiszter , t kvantumbit: N2 2t 2N2 , kivétel: ha az r 2 hatványa, t=n is elég y : B regiszter , n kvantumbit mod N: 0 a x y N Rendszerállapotok leírása:
0 5 Kiindulási állapot:
0 0 0 0 0
t
n
Ahol a értéke kisebb, mint N, és relatív prím N-hez
Kvantum prímfaktorizáció 1. A-regiszteren végrehajtjuk a Hadamard transzformációt:
1
2t 1
1 2
t
x
0
x 0
Az A-regiszter kvantumbitjeinek valószínűségi amplitúdó értékei:
1 2t 2. Végrehajtjuk a Va transzformációt:
2 Va 1
2t 1
1 2
t
V x x 0
a
0
2 1 r 1 2t 1 1 1 r x x a b kr t t 2 x 0 2 b0 k 0 ahol 0 k 2t / r és 0 b r 1 t
b a ,
Kvantum prímfaktorizáció 2 Va 1
2t 1
1
V x
2t
x 0
a
0
1 2t
2t 1
x
ax
x 0
2 1 r 1 r 2t 1 b b kr a , ahol 0 k r t 2 b 0 k 0 megj.: a b a kr b , mivel a r 1 mod N t
3. Mérés eredménye legyen: b0
2 1 r r t kr b0 2 k 0 t
3
2 1 1 r kr b0 t 2 / r k 0 t
b0 a
b0 a .
1 és 0 b r 1.
Kvantum prímfaktorizáció 2 1 r r 3 t kr b0 2 k 0 Eredmény : t
1 b0 a t 2 /r
2 1 r kr b0 k 0 t
b0 a .
Periodikus állapotok : b0 , 1r b0 , 2r b0 , 2t r b0 . Feladat : periódus meghatározása: QFT
Kvantum prímfaktorizáció k 0 N 1 : számítási bázis Fourier transzformáció végrehajtása: DFT k
k
1 N
N 1
2 ixk / N e x 0
1 x N
N 1
kx x, x 0
ahol kx e 2 i / N , és k : k 0, , N 1 ortonormált bázis, így : N 1
N 1
k
1 1 1 k x ' x x ' x DFT k k ' k , így : N x 0 N N x 0 1, ha x x ' (ill. k az N többszöröse) . k ' k 0, ha x x ' †
Kvantum prímfaktorizáció Az A-regiszter bemérésének eredménye 2 1 1 r kr b0 t 2 / r k 0 t
az 3
b0 a állapotban, b0 3 és r 8 értékek mellett
2t A vízszintes tengelyen 2 pont látható, a csúcsértékek száma: , periodus: r r r csúcspontokhoz tartozó maximális valószínűség: t 2 t
Kvantum prímfaktorizáció
4. Fourier-transzformáció végrehajtása a 3 állapoton:
4
1 DFT† 3 DFT† t 2 /r 2t 1 r
1 r t 2 k 0 2t
2 1 r kr b0 k 0 t
2t 1
e x 0
b0 a
2 ix b0 kr /2t
b0 x a .
Átrendezés után: 2t t 1 2 ixk 2 1 r t b0 1 1 1 2t / r 2 ixb0 /2 4 e e x a t t r x 0 2 / r 2 / r k 0 2t t 1 2 ixk 2 1 r t b0 1 1 2t / r 2 ixb0 /2 e e x 2t / r a . r x 0 k 0
Kvantum prímfaktorizáció Az e2 ix /7 x 0, , 6 vekorok , N 7 és s 1 esetén: A komplex vektorok összege 0. A szögletes zárójel értéke csak abban az esetben nem nulla, ha x s 2t / r , ahol s 0,, r - 1, ezen x értékek mellett a szögletes zárójelben lévő kifejezés 1: 2t t 1 2 ixk 2 1 r t b0 1 1 2t / r 2 ixb0 /2 4 e x a , 2t / r e r x 0 k 0 2t 2t 1 2 i s 2t / r k 1 r r 1 1 2 i s k 2t / r ekkor: t e e = t 2 / r k 0 2 / r k 0 2t 1 r
b0 1 1 t 1 2 1 2 ixb0 / 2t x a , e 1 2t / r 2 / r 1, így: r 2t / r k 0 x 0 t
Kvantum prímfaktorizáció 1 r 1 2 ixb0 /2t b0 t e x a x s mivel , 2 / r így : r x 0 2t b0 1 r 1 2 i s r 2t s 2t b0 e a r r s 0
4
t r 1 2 i s b b0 s 1 2 0 r e a . r r s 0
Kvantum prímfaktorizáció 1 r 1 2 i rs b0 s 2t b0 5. Az 4 e a állapoton r r s 0 elvégezve a A-regiszter bemérését, a kapott eredmény: s0 2t , ahol s0 tetszőleges érték lehet 0 és r-1 között, r azonos valószínűséggel.
A vízszintes tengelyen 2t pont található. A vízszintes tengelyen r érték található a nem nulla pontokhoz tartozó valószínűség
1 , r a periódusérték pedig mindenhol
2t . r
Kvantum prímfaktorizáció 1 r 1 2 i rs b0 s 2t b0 5. Az 4 e a állapoton r r s 0 elvégezve a A-regiszter bemérését, a kapott eredmény: s0 2t , ahol s0 tetszőleges érték lehet 0 és r-1 között, r azonos valószínűséggel.
Ha s0 0 : r értéke nem állapítható meg, újból futtatjuk az algoritmust s0 2t Ha s0 0 : akkor a kapott eredményt osztjuk 2t vel, r így:
s0 . r
Azonban mind s0 , mind pedig r értéke ismeretlen.
Kvantum prímfaktorizáció Ha s0 relatív prím r-hez: a nevező a megoldás. Ha s0 -nak és r-nek van közös osztója: iteratív eljárással csökkentjük az
s0 r értékét az 1 közös osztó megtalálásáig.
Kvantum-prímfaktorizáció példa
Kvantum prímfaktorizáció A faktorizálni kívánt N legyen N 21 p 7, q 3. Az A regiszterben legyen t 9 kvantumbit, az N 2 2t 2 N 2 összefüggés figyelembevételével. Ekkor t lehetséges legkisebb értéke 9. A B regiszter legyen 5 kvantumbites. a : véletlen érték, relatív prím N-hez, illetve 1 a N , így a 2. Ha a véletlen választott értékünk nem lenne relatív prím N hez, N prímfaktorait könnyen megtalálhatnánk az LNKO(a,N) segítségével.
Cél: r periodus meghatározása, adott a és N értékek mellett. Az algoritmus végén r=6 eredményt kell kapnunk!
Kvantum prímfaktorizáció 1. A rendszer kezdeti állapota :
0 0 0 0 0 . t
n
A Hadamard transzformáció végrehajtása utáni állapot:
1
1 2
t
29 1
1 2
2t 1
9
x 0
x
0
x 0
1 511 x 0 x 0 . 512 x 0
Kvantum prímfaktorizáció 2. Va 1 transzformáció végrehajtása:
2 Va 1 a x 2 x mod N x
511
511
1 1 x 0 512 x 0 512 x 0
1 0 1 1 2 2 4 3 8 4 16 5 11 512 6 1 7 2 8 4 9 8 10 16 11 11 12 1 . A B-regiszter értékei szerint csoportosítva, oszlopok szerint pedig növekvő sorrendbe rendezhetjük.
Kvantum prímfaktorizáció Az átrendezés utáni eredmény ebben az esetben azért nem szimmetrikus, mert a periódus értéke nem kettő hatványa. Így az első két sorban 86 érték található, a többiben pedig 85.
1 512
0
6 12 504 510 1
1 7 13 505 511 2 2 8 14 506 4 3 9 15 507 8 4 10 16 508 16 5 11 17 509 11 .
Kvantum prímfaktorizáció 1 512
0
6 12 504 510 1
1 7 13 505 511 2 2 8 14 506 4 3 9 15 507 8 4 10 16 508 16 5 11 17 509 11 .
Az átrendezést követően az egy sorban lévő értékek száma: 2t / r 512 / 6 86.
Kvantum prímfaktorizáció Bemérjük a B regisztert: A lehetséges függvényértékek a következők lesznek:
F21 ( x) 2 x mod(21). Az F ( x) függvény által felvett értékek: x F(x)
0 1
1 2
2 4
3 8
4 16
5 11
6 1
7 2
A B regiszteren elvégzett mérés eredménye a 1, 2, 4,8,16,11 halmazból kerülhet csak ki!
8 4
9 8
10 16
11 11
12 1
13 2
… …
Kvantum prímfaktorizáció A mérésünk eredménye legyen 2. Ekkor:
1 1 7 13 505 511 86
3
2.
így az előbbi átrendezésnél kapott 2 értékhez tartozó sor lesz a mérés eredménye. Az állapot valószínűségi amplitúdója:
1
1 1 . t 512 2 86 6 6 x F(x)
0 1
1 2
2 4
3 8
4 16
5 11
6 1
7 2
8 4
9 8
10 16
11 11
12 1
13 2
… …
Kvantum prímfaktorizáció
x F(x)
A B regiszteren elvégzett mérés eredménye következtében az A-regiszterben csak azon „sor” maradt, amely az aktuális mérési eredményünknek megfelel. Így, az A-regiszterben csak olyan értékek maradtak, amelyek a mért eredmény állítják elő, tehát egy teljes periódust kaptunk. Ebből az eredményből azonban még nem tudjuk kinyerni az r értékét, ezért a következő lépésben a Fourier transzformáció alkalmazása következik. 0 1
1 2
2 4
3 8
4 16
5 11
6 1
7 2
8 4
9 8
10 16
11 11
12 1
13 2
… …
Kvantum prímfaktorizáció A B-regiszteren elvégzett mérés eredménye 2 , így a b0 2 , azaz b0 1. 85 1 † † 6k 1 2 4 DFT 3 DFT 86 k 0 xk x 2 i 512 1 511 1 85 2 i 6512 e x 2 . e 512 x 0 86 k 0
Mivel 512/6-1=84.3333 85, így kerekítünk.
Kvantum prímfaktorizáció xk 1 85 2 i 6512 e A tag csak abban az esetben nem nulla, ha 86 k 0 x s 2t / r , ahol s 0,, r -1, ezen x értékek mellett a szögletes zárójelben lévő kifejezés 1:
x 0 512 / 6 0 x 1 512 / 6 85 x 2 512 / 6 171 x 3 512 / 6 256 x 4 512 / 6 341 x 5 512 / 6 427
Kvantum prímfaktorizáció x legyen 1 512 / 6 85
4
x 85 2 i 6 1 512/ 6 k 2 i 1 1 512 e e 512 x 2 . 512 x 0 86 k 0
4
t 1 2 1 1 2t / r r x 0
511
2t 1 r
e k 0
1 2 ik s0
b0 2 ixb0 / 2t x a . e
Kvantum prímfaktorizáció Ha s0 : 0 és 5 közötti intervallumból kerül ki, akkor s0 2t s0 512 . r 6 A transzformáció eredménye csak abban az esetben különbözik nullától, ha x s 2t / r s 0, , r - 1. Mekkora a valószínűsége annak, hogy az A-regiszter megmérése során a 0 - 511 közötti intervallumból éppen x értéket fogok kapni ? A keresett P x valószínűség:
P x
1 512 86
85
e k 0
6 xk 2 2 i 512
.
Kvantum prímfaktorizáció A P x valószínűség maximális értékét 512 xs r értékek esetén veszi fel, ekkor: 1 P x 512 86 1 512 86
85
e k 0
85
e k 0
6 xk 2 2 i 512
1 512 86
512 2 6 k 2 i 6 512
85
e
512 2 6s k r 2 i 512
k 0
1 512 86
85
2
2 isk . e k 0
Mivel 2t N 2 : az x beméréséből nagy valószínűséggel kiolvasható az eredmény.
Kvantum prímfaktorizáció 1 P x 512 86
85
e
2 i
6 xk 2 512
.
k 0
A csúcsértékek az x=0,85,171,256,341,427 értékeknél találhatóak. A csúcsértékek pontossága az A-regiszterben található kvantumbitek számától függ.
Kvantum prímfaktorizáció Lehetséges mérési eredmények vizsgálata: x 0 : algoritmus leáll, újra kell futtatnunk, azonban a B regiszteren elvégzett mérés eredményét a 2 t megtartjuk. Csak a B regiszteren elvégzett mérés utáni részeket futtatjuk újra, így annak a valószínűsége, hogy x=0 ismételten:
P 0
1 512 86
85
e
2 i
60 k 2 512
k 0
1 86 2 0.167. 86 512 86 512
Kvantum prímfaktorizáció Ha x 85, az eredményt osztjuk 2t vel : x 2t = s0 / 6, hiszen, ha s0 1, akkor: 85 s0 85 1 . 512 r 512 6 85 85 s0 1 értékéből meghatározni az r periódust. Azaz : ből az érték előállítását 512 r 512 r kell elvégeznünk. Ehhez számláló értékét kell folyamatosan csökkentenünk addig, amíg el nem érte az 1-et, a nevezővel együtt. Cél:
x1 1 . k0 1 x2 k1 1 kp
Kvantum prímfaktorizáció x1 1 k0 . 1 x2 k1 1 kp Az iteráció alkalmazása x 85 esetén: 85 512 512 2 6 1. 512 85 85 85 2 85 1 42 2. 85 2 2 1 2 3. 2 1 STOP. Azaz: 85 1 . 1 512 6 1 42 2
A
85 felbontása: 512
1 42 85 1 1 1 , , , , . 6 42 6 85 6 6 6 6
Kvantum prímfaktorizáció A
85 1 42 85 1 42 85 , , . felbontása: , , 512 6 42 6 85 6 6 253 512
1 42 85 , Mivel r N , így azonelemet választjuk a , halmazból, 6 253 512 1 amelynek nevezője kisebb, mint 21: 6
r=6. Ellenőrzés: 2r 1 mod N 26 1 mod 21 teljesül.
Kvantum prímfaktorizáció Ha a mérés eredménye a 167 x 175 közötti intervallumból kerül ki, akkor: 2 85 2 s0 s0 2. 512 r 1 1 A felbontást elvégezve: 2 . Ekkor tehát nem magát az r periódust, hanem annak egyik 6 3 faktorát kaptuk. Ezen eredményt ellenőrizve : 23 8 mod 21. A keresett periodus r r1r2 . A mérésünk eredménye 3 lett, azonban az ellenőrzésnél kiderült, hogy ez nem lehet a keresett r. Azon r2 értékét keressük, amely az x r1 periódusa. Tudjuk, hogy x r1 23 8, így F21 ( x) 8x mod(21) függvény alapján: x F(x)
0 1
1 8
2 1
3 8
4 1
5 8
6 1
7 8
8 1
9 8
10 1
11 8
12 1
13 8
… …
A kapott periódusérték 2, azaz r2 2. A keresett r periodus tehát:
r r1r2 3 2 6.
Kvantum prímfaktorizáció • A kiinduló adatok az áramkör létrehozásához: – A faktorizálandó szám: N=21. – A függvényhez választott véletlenszám: a=2. – Az A-regiszterben található kvantumbitek száma: t=9.
Kvantum prímfaktorizáció
A szimuláció végeztével a megkapjuk az egyes állapotokhoz tartozó valószínűségi amplitúdók értékét. A szimulációval kapott eredmények közül a legnagyobb valószínűségi amplitúdóhoz tartozó érték adja meg a k értékét, ami 85.
|00101010100010 > 0.337893160338835 + 1.0367950609158057E-8i. A-reg=85
a=2
A legnagyobb valószínűségű x értékek: x 0,85,171, 256,341, 427
Kvantum prímfaktorizáció
A kapott valószínűségi amplitúdó értékből előállítjuk a keresett periódust. Tudjuk, hogy k=85, ebből pedig a 2t 512 k r r ?
összefüggés felhasználásával kapjuk, hogy k 1 85 =0.16. t 2 r 512 1 k értéke így 0.16 r A nevező és a számláló felcserélésével, az előzőekben látott módon, a periódus értéke innen már egyszerűen meghatározható. 2t :ismert, értéke 512
