Matematika | Diszkrét Matematika » Radnai András - Rácselmélet alkalmazása a számelméletben

http://www.doksihu Rácselmélet alkalmazása a számelméletben Szakdolgozat Radnai András Témavezet®: Grolmusz Vince Számítógéptudományi tanszék Eötvös Loránd Tudományegyetem Természettudományi Kar http://www.doksihu Tartalomjegyzék Bevezetés 2 1. Rácsalgoritmusok 3 1.1 Deníciók . 1.2 Gram-Schmidt ortogonalizáció, gyenge redukció 1.3 Az LLL algoritmus 3 . 4 . 7 2. Bonyolultságelméleti vonatkozások 11 2.1 CVP: Egy másik alapvet® rácselméleti probléma . 11 2.2 Bonyolultság . 13 2.3 CVP NP-teljes 14 . 3. Kísérletek prímfaktorizálásra 15 3.1 Alapok, Schnorr algoritmusa . 15 3.2 Rácsok . 18 4. Összefoglalás 23 A. Jelölések 23 B. Felhasznált irodalom 23 1 http://www.doksihu Bevezetés A szakdolgozatnak célja összefoglalni

néhány rácselmélettel kapcsolatos eredményt. Maga a rács, melyet általában  L-el (Lattice=Rács) jelölünk, deníció szerint az  n dimenziós valós térnek egy diszkrét additív részcsoportja. Másképpen megfogalmazva néhány független vektor egészegyütthatós lineáris kombinációinak halmaza Ezen vektorok által alkotott rendszert a rács bázisának nevezzük. Mint most is, ezentúl is vektorrendszer alatt kizárólag rendezett halmazra fogunk gondolni. rai tetsz®leges SOn (Z)-beli Egy rács bázisának vekto- transzformáció hatására ugyanannak a rácsnak bázisába mennek át, a fogalom tehát korántsem egyértelm¶. A felmerül® problémák vizsgálatakor legtöbbször olyan bázist keresünk majd, melyben az adott rácsnak egy bizonyos tulajdonsága viszonylag átlátható. Természetesen felmerül a kérdés, hogy milyen hosszú a legrövidebb nem0 vektora egy rácsnak. Erre a Minkowski-tétel ad becslést, viszont nem ad konkrét

rövid vektort. Kérdés marad, hogy van-e polinomiális idej¶ algoritmus, ami megadja a rács legrövidebb vektorát Ez az egyik alapvet® probléma, az SVP.(Shortest Vector Problem) mely a kérdés egyszer¶ségének ellenére meglep®en nehéznek bizonyul: egy sor állítás áll rendelkezésre, mely különböz® feltételek melletti NP-nehézségét bizonyítja a problémának. legrövidebb vektor hosszát a továbbiakban λ (L)-lel A jelöljük majd. A kérdés 2-dimenziós esete már Gauss számára is felmerült, aki teljességgel megoldotta a problémát: az euklideszi algoritmus általánosításának tekinthet® algoritmust adott, mely megtalálja a legrövidebb vektort. A végeredményként kapott bázist Gauss-redukáltnak nevezzük Ez vázlatosan szerepel is az els® fejezetben Három dimenzióra még mindig átjátszható na- gyobb nehézségek nélkül a két dimenziós bázisredukció. Magasabb dimenziókban a Lovász László, Arjen Lenstra és Hendrik

Lenstra által 1982-ben adott LLL-algoritmusnál nem ismert lényegesen jobban közelít® módszer. Látni fogjuk, hogy ennek ellenére a futásidejének polinomialitása egy folyamatosan csökken® potenciál bevezetésével könnyen levezethet® A probléma bonyolultságát mutatja, hogy ez is a dimenzióban exponenciá- 2 http://www.doksihu lis hibakonstanssal dolgozik, mégis a gyakorlatban igen jól használhatónak mutatkozik. [2]-ben több példa is meg említve van az algoritmus felhasználására. Egy egyszer¶bb ilyen feladat például a szimultán approximáció, aminek lényege, hogy adott (az algoritmikusan kezelhet®ség miatt racionális) számokat egyszerre  ε-nál jobban közelítsünk minél kisebb közös nevez®j¶ törtekkel. Alkalmazható a nyilvános kulcsú RSA kódolás feltörésére is (természetesen csak nagyon er®s plusz feltételek mellett). A következ® fejezetben megvizsgáljuk, hogy milyen közeli rácsvektort tudunk adni egy adott

tetsz®leges vektorra a Lovász-redukált bázis segítségével. A legközelebbi rácsvektor keresésének problémáját nevezzük CVP.(Closest Vector Problem)-nek. Ezek után az alapvet® rácselméleti problémák bonyolultságelméleti nehézségér®l teszünk néhány említést A prímfaktorizációval foglalkozó fejezet [4] nyomán egy kísérleti lehet®séget mutat egy adott nagy szám nem-triviális szorzattá bontására. Ennek alapja az ott részletezett Schnorr-algoritmus, aminek m¶ködéséhez szükséges inputot prímrácsokban keresett rövid, illetve közeli vektorok segítségével próbáljuk biztosítani. 1. Rácsalgoritmusok 1.1 Deníciók Rácsnak nevezünk Rm egy független vektorrendszere által kifeszített ad- ditív részcsoportot: 1.11 Deníció Legyenek b1 , b2 , . , bn ∈ Rm ekkor L (b1 , b2 , . , bn ) := ( n X lineárisan független vektorok ) λi bi |∀i λi ∈ Z i=1 Itt n-et a rács rangjának, m-et a dimenziójának,

pedig a bázisának nevezzük. 3 b1 , b2 , . , bn vektorokat http://www.doksihu Vegyük észre, hogy egy adott rácsnak több bázisa is lehet. torokból (mint oszlopvektorokból) álló [b1 , b2 , . , bn ]-vel! n × m-es A bázisvek- mátrixot jelöljük B := Nem fog félreértésekhez vezetni ha magát a bázist is egy- szer¶en B-vel jelöljük. Szükségünk lesz még egy fogalomra, a rács determinánsára 1.12 Deníció Az L rács determinánsának a bázisvektorai által meghatá- rozott Gram-mátrix determinánsának gyökét nevezzük: det (L) := Ez az érték megegyezik a bázisvektorok által kifeszített { Pn i=1 p det (B T B) λi bi |∀i λi ∈ [0, 1)} (n-dimenziós) parallelepipedon, az úgynevezett alap blokk térfogatával. Mivel a rács maga mindig benne van egy n dimenziós altérben, ezért nyugodtan áttérhetünk az úgynevezett teljes rangú rácsok vizsgálatára, ahol a dimenzió és a rang megegyezik. Ilyen rácsoknál a

determináns egyszer¶bben felírható: det (L) := |det (B)| Felmerül a kérdés, hogy ez a determináns valóban a rácsra jellemz® mennyisége, vagy esetleg függhet a bázisvektorok választásától. különböz® bázisa a rácsunknak. Legyen B és B két Ez azt jelenti, hogy elemeik kölcsönösen felírhatók a másik elemeinek egész együtthatós lineáris kombinációjaként. itt T és T −1 BT = B 0 ∃T ∈ Zn×n Vagyis mátrixokra áttérve & B 0 T −1 = B Mivel is egész számokból áll, determinánsuk is egész lesz, és tud- juk róluk, hogy reciprokai egymásnak. 0 |det (B)| = |det (B )|, Következésképp det T = ±1, tehát amivel megvan az egyértelm¶ség. 1.2 Gram-Schmidt ortogonalizáció, gyenge redukció Ismert a Gram-Schmidt ortogonalizációs eljárás, melynek lényege, hogy az adott b1 , b2 , . , bn b∗1 , b∗2 , . , b∗n vektorokat csiná- b∗i − bi ∈ hb1 , b2 , . , bi−1 i Ekkor az eredeti bázisból

olyan mer®leges lunk, melyekre igaz, hogy ∀i bázisvektorokat felírhatjuk bi = b∗i + i−1 X j=1 4 µi,j b∗j http://www.doksihu alakban, ahol a ηi,,j (i > j ) Gram-Schmidt együtthatók a következ®ek: µi,,j := bi , b∗j b∗j , b∗j = bi , b∗j b∗j 2 Kiterjesztjük a  µ együtthatók indextartományát a következ® módon: ( µi,j := 1 , ha i = j 0 , ha i < j Ekkor felírhatjuk a következ® mátrix egyenletet: B∗ · G = B, ahol együtthatókból kapott mátrix. Könnyen meggondolható, hogy mind −1 G G a µj,i G, mind olyan fels®háromszögmátrixok, melyek f®átlójában mindenhol egyes van. A következ®kben különböz® olyan megkötéseket próbálunk tenni bázisokra, melyek segítenek áttekinthet®vé tenni a rácsban lév® vektorokat. Egy dimenzióban a bázisunk el®jel erejéig meghatározott. Két dimenzióban deniálhatjuk a Gauss-redukáltságot a következ®képpen: 1.21 Deníció ben kb1 k ≤ kb2

k, Azt mondjuk, hogy a valamint b1 , b2 bázis Gauss-redukált, amennyi- 0 ≤ µ2,1 ≤ 1/2 Ez a deníció azért kényelmes, mert van gyors (és egyszer¶) algoritmus ilyen bázis el®állítására. lesz a rácsnak: Könnyen meggondolható, hogy b2 -nek b1 legrövidebb vektora az ábrán a satírozott területbe kell mutatnia. 5 http://www.doksihu Magasabb dimenziókban nem ismert ilyen er®s és algoritmikusan polinomiális id®ben megvalósítható feltétel. A következ® deníciót az alapján az észrevétel alapján vezethetjük be, hogy két dimenzióban a Gauss-redukáltság π /3 ereje abban rejlett, hogy a vektoraink egymásra és π /2 közötti szöget zárnak be benne. Ennek kiterjesztéseként általában azt követeljük meg, hogy páronként a bázisvektorok egymásra a lehet® legmer®legesebbek legyenek egymásra. 1.22 Deníció Egy b1 , b2 , . , bn ∈ Rn bázist gyengén redukáltnak neve- zünk, amennyiben a Gram-Schmidt

együtthatók kielégítik az alábbi feltételt: |µi,j | ≤ 1/2, ahol 1 ≤ j < i ≤ n A feltételnek eleget tev® bázis szintén polinomiális id®ben található egy egyszer¶ algoritmussal. 1.23 Algoritmus Iteráljuk ezt az egy lépést: Ha nincs olyan (i,j) pár, melyekre |µi,j | > 1/2, akkor leállunk. Egyébként pedig vegyük azt a párt, amelyikre i a legkisebb ilyen, és ezen belül  j  maximális. Erre az  i-re és  j -re: bi := bi − dµi,j c · bj 1.24 Állítás Ez az algoritmus polinomiális id®ben véget ér, és gyengén redukált bázist hagy végeredményül tetsz®leges input bázis esetén. Bizonyítás. Az output redukáltsága triviális, amennyiben az algoritmus tényleg lefut. Ehhez azt fogjuk belátni, hogy egy lépésben egy együtthatót legfeljebb 1/2 abszolút érték¶re állítunk, és a korábban kijavítottakat nem rontjuk el. Mivel b1 , b2 , . , bi−1 , valamint b∗1 , b∗2 , . , b∗n nem változnak az

el- járás során, ezért az i-nél kisebb els® index¶ Gram-Schmidt együtthatók szintén változatlanok lesznek. A kérdés, hogy mi történhet egy ahol µi,k számmal, j ≤ k < i. µ0i,k hb0i , b∗k i hbi − dµi,j c · bj , b∗k i hbi , b∗k i hbj , b∗k i := ∗ ∗ = = ∗ ∗ − dµi,j c ∗ ∗ hbk , bk i hb∗k , b∗k i hbk , bk i hbk , bk i 6 http://www.doksihu Itt a bal oldali összeadandó maga µi,k , a jobboldali a j <k feltétel mellett 0, tehát µ0i,k = µi,k j=k esetben hbj ,b∗j i = 1-b®l hb∗j ,b∗j i azt kapjuk, hogy µ0i,j = |µi,j − dµi,j c| ≤ 1/2 1.3 Az LLL algoritmus A Lovász-redukáltság el®tt vezessünk be egy jelölést: adott Rn bázis mellett bármely összegére úgy, hogy a ∈ Rn Egy vektorok & a2 ∈ hb1 , b2 , . , bi−1 i⊥ , ezek direkt kiegészít® alterek. Ekkor jelölje  a (i) az 1.31 Deníció a = a1 + a2 vektor felbontható a1 ∈ hb1 , b2 , . , bi−1 i b1 , b2 , .

, bn ∈ b1 , b2 , . , bn ∈ Rn a2 mivel komponenst! bázist Lovász-redukáltnak neve- zünk, ha egyrészt gyengén redukált, másrészt kbi (i)k2 ≤ 4 kbi+1 (i)k2 3 ahol 1 ≤ i < n A Gram-Schmidt ortogonalizációnál felírt egyenletekb®l itt bi (i) = b∗i bi+1 (i) = b∗i+1 + µi+1,i b∗i 1.32 Állítás Legyen b1 , b2 , . , bn ∈ Rn Lovász-redukált bázisa az L rács- nak. Ekkor teljesül az alábbi három állítás: (1) (2) (3) kb1 k ≤ 2(n−1)/2 λ (L) p kb1 k ≤ 2(n−1)/4 det (L) n Y n kbi k ≤ 2( 2 )/2 det (L) i=1 1.33 Megjegyzés Itt az els® állításban szerepl® 2(n−1)/2 együttható a di- menzióban exponenciális hibakonstans. Meglep®, hogy ennek ellenére az algoritmus jól használható A harmadik állítás azt fejezi ki, hogy a célunk, nevezetesen, hogy minél mer®legesebb bázisvektorokat találjunk, mennyire van biztosítva: a bal oldal minél kisebb Ideális esetben, vagyis ha a vektorok páronként 7

http://www.doksihu mer®legesek egymásra, természetesen ez pont a determinánssal egyenl®. Itt egy n 2( 2 )/2 -es hibataggal tudunk becsülni. Bizonyítás.Legyen b1 , b2 , , bn ∈ Rn Lovász-redukált bázis! Ekkor teljesül az alábbi egyenl®tlenségrendszer kb∗i k2 ≤ 4 ∗ b + µi+1,i b∗i 3 i+1 2 = 4 ∗ b 3 i+1 2 4 4 ∗ + µ2i+1,i kb∗i k2 ≤ b 3 3 i+1 2 1 + kb∗i k2 3 Innen átrendezéssel adódik az alábbi egyenl®tlenség: kb∗i k2 ≤ 2 b∗i+1 2 Amib®l indukcióval látható, hogy kb1 k2 = kb∗1 k2 ≤ 2i−1 kb∗i k2 A bizonyítás során csak ezt fogjuk kihasználni, mint többletet a gyengén redukáltsághoz képest. Az eredeti felírás majd az algoritmus lépésszámának ellen®rzésénél lesz kényelmes. Ezeket az egyenl®tlenségeket összeszorozva i = 1, . , n-re 2n kb1 k n ≤ 2( 2 ) n Y n kb∗i k2 = 2( 2 ) det 2 (L) , i=1 ami bizonyítja (2) állítást. A (3) bizonyításához elég belátnunk, hogy kbi k ≤

2i−1 kb∗i k Ezek szorzata adja az állítást. Ez i = 1-re triviális, nagyobb indexre pedig m¶ködik a következ® érvelés: 2 kbi k = b∗i + i−1 X 2 µi,j b∗j = kb∗i k2 + j=1 i−1 X µ2i,j b∗j 2 ≤ kb∗i k2 + j=1 ≤ 1 1+ 4 i−1 X i−1 X 1 j=1 4 b∗j 2 ≤ !! 2j ≤ 2i−1 kb∗i k j=1 Hogy a legrövidebb vektor hosszára alsó becslést adhassunk, el®ször belátjuk a következ® lemmát: 8 http://www.doksihu 1.34 Lemma A szokásos jelölések mellett λ (L) ≥ min {kb∗i k} 1≤i≤n Bizonyítás.(lemma)Legyen b ∈ L tetsz®leges nem-0 rácsbeli vektor b= k X Ekkor λi bi i=1 valamely λ1 , . , λk ∈ Z számokra, ahol k≤n és λk 6= 0. Másrészt ugyanez a vektor felírható az ortogonalizált bázisban is b= k X λ0i b∗i i=1 alakban, ahol a legnagyobb index¶ együtthatókra teljesül, hogy együtthatómátrix −1 G λk = λ0k (az inverzének az ortogonalizációnál megemlített tulaj-

donságaiból látszik). Így felírható, hogy 2 kbk = k X ,2 ∗ 2 ∗ 2 ∗ 2 λ,2 i kbi k ≥ λk kbk k ≥ kbk k , i=1 ami bizonyítja a lemma állítását. Ezzel   kb1 k2 ≤ min 2i−1 kb∗i k2 ≤ 2n−1 min kb∗i k2 ≤ 2n−1 λ2 (L) 1≤i≤n 1≤i≤n Ahonnan végül gyökvonással kapjuk az (1) állítást. 1.35 Algoritmus (Lovász-Lenstra-Lenstra)Az algoritmusban két lépést haj- tunk végre felváltva: Az els®ben az aktuális bázisunkat átalakítjuk gyengénredukálttá az el®z®ekben tárgyalt módon. A másodikban, ha találunk két szomszédos index¶ bázisvektort, mely megszegi a Lovász-redukáltság feltételét, akkor ezeket felcseréljük 1.36 Állítás Legyen a b1 , b2 , . , bn ∈ Qn bázis által generált rács L. Ekkor az LLL algoritmus polinomiális id®ben el®állít egy Lovász-redukált bázist. 9 http://www.doksihu Bizonyítás.Nyilvánvaló, hogy amennyiben az algoritmus valóban véget ér, egy Lovász-redukált

bázist ad. Az algoritmus lépésszámát egy egyszer¶ potenciálfüggvény bevezetésének segítségével fogjuk felülr®l becsülni. D (b1 , b2 , . , bn ) := n Y kb∗i kn−i i=1 Ez a potenciál felírható az alábbi módon is: D (b1 , b2 , . , bn ) := n−1 Y det (L (b1 , b2 , . , bi )) i=1 Feltehetjük, hogy a kiinduló bázisvektoraink koordinátái egészek: ha nem azok, akkor felszorzunk a nevez®k legkisebb közös többszörösével. Vegyük észre, hogy ekkor az algoritmus végig egész-koordinátás bázisokon mozog. Ha a jobb oldalon szerepl® rács bázisához tartozó mátrixot Bi -vel jelöljük, akkor a determináns deníciójában szerepl® Gram mátrix i×i Z -beli lévén pozitív egész determinánsú, következésképp det (L (b1 , b2 , . , bi )) = q det (BiT Bi ) ≥ 1 minden i-re, azaz a potenciál függvény is mindig ≥1 lesz. Mivel az els® lé- pésünk xen hagyja az ortogonalizált vektorokat, a potenciál csak a

második lépés során változhat, mégpedig a következ® módon csökken: 1.37 Lemma Ha alkalmaznunk kell a második lépést, azaz akad két vektor a bázisban, melyek sértik a Lovász-redukáltság feltételét, akkor ezek megcserélésének hatására az új √ D0 ≤ 23 D D0 = D (b1 , . , bi−1 , bi+1 , bi , bi+2 , , bn ) potenciálra Bizonyítás.(lemma)Legyen bi és bi+1 melyekre sérül a feltétel: kbi (i)k2 > 4 kbi+1 (i)k2 3 A Gram-Schmidt ortogonalizált vektorok közül csak az i-edik és i+1-edik változik. bi (i) és bi+1 (i)vektorok által bezárt szöget jelöljük  α-val. Ekkor 10 http://www.doksihu a potencilok hányadosa D0 kbi+1 (i)kn−i · kbi (i) · sin αkn−i−1 kbi+1 (i)k = < n−i n−i−1 = D kbi (i)k kbi (i)k · kbi+1 (i) · sin αk r 3 4 Adjunk becslést az algoritmus lépésszámára a lemma segítségével! h lépés után: 1 ≤ D (b01 , b02 , . , b0n ) ≤ √ !h 3 D (b1 , b2 , . , bn ) ≤ 2 √ !h

 ( n2 ) 3 max {kbi k} 1≤i≤n 2 Ennek logaritmusát véve: h≤ 2. n 1 max {log kbi k} √ log 2/ 3 2 1≤i≤n Bonyolultságelméleti vonatkozások 2.1 CVP: Egy másik alapvet® rácselméleti probléma Ebben az alfejezetben azt vizsgáljuk, hogy az LLL-algoritmus hogyan tud segíteni egy adott vektorhoz egy adott rácsban viszonylag közeli vektorok keresésében. A ténylegesen legközelebbi vektor megtalálásának problémáját nevezzük CVP.(Closest Vector Problem)-nek Nevezzük el a B bázis vektorai által kifeszített origóba tolt centrumú parallelepipedont: P (B) := ( n X i=1  ) 1 1 λi bi ∀i λi ∈ − , 2 2 Ekkor könny¶ meggondolni, hogy mind egyrét¶en fedik le P (B ∗ ) Rn -t. pontosan egy P (B) + L (B), Ebb®l kifolyólag tetsz®leges L (B)-beli mind P (B ∗ ) + L (B) t ∈ Rn vektorra t+ rácsvektort fog tartalmazni. Azt szeretnénk megmutatni, hogy ez a rács vektor gyors algoritmussal megtalálható, valamint, hogy amennyiben

Lovász-redukált bázisból indulunk 11 http://www.doksihu ki, viszonylag jól megközelíti a  t célvektort. Rögzítsük tehát a t ∈ Rn vektort, és tegyük fel, hogy  B  Lovász-redukált bázis! A rácsvektort amit a t + P (B ∗ ) téglatestben találtunk jelöljük Bx-el, a  t-hez legközelebbit pedig Bb x-al (x, x b ∈ Zn ). Belátjuk, hogy ekkor n x − tk2 . kBx − tk2 < 2 2 kBb Az eltérés-vektorokat felírhatjuk a B∗z & Bb x − t = B ∗ zb.  x tájára teljesülni fog, hogy Minden bázisban: ∃z, zb ∈ Rn Bx − t = deníciója miatt  z  vektor minden koordiná- dzi c = 0. legnagyobb index, ahol eltérés van: 2.11 Lemma B∗ i>s Tegyük fel, hogy x b 6= x, és legyen  s a x bs 6= xs . zbi = zi , indexre és zbi − zi ∈ Z {0} Bizonyítás.(lemma)Vegyük a  G Gram-Schmidt együttható-mátrixot! B = B∗ · G miatt felírhatjuk, hogy B ∗ · Gx − t = B ∗ z; B ∗ · Gb x − t = B ∗ zb. Ezek

különbségét véve kapjuk, hogy B ∗ · G (b x − x) = B ∗ (b z − z) . Mivel B∗ invertálható, ennek következményeképp B ∗ · G (b x − x) = B ∗ (b z − z) .  G tulajdonságaiból (fels® háromszögmátrix, egyesekkel a diagonálisában) következik a lemma állítása. Sz¶kségünk lesz még a lenne igaz, állna, hogy állna azzal, hogy |b zs − zs | ≤ zbi − zi 1 egyenl®tlenségre. amennyiben ez nem 2 |b zs |+|zs | < 12 + 12 = 1, ami ellentmondásban |b zs | ≥ nem-0 egész szám. Ezek alapján 2 ∗ 2 kBx − tk = kB zk = n X i=1 12 kb∗i k2 zi2 = http://www.doksihu = s X zi2 kb∗i k2 + i=1 ≤ zi2 kb∗i k2 ≤ i=s+1 s X 2s−i i=1 n X 4 kb∗s k2 + n X zi2 kb∗i k2 = i=s+1 n X 2s − 1 ∗ 2 = kbs k + zbi2 kb∗i k2 < 4 i=s+1 ! n X < 2s zbs2 kb∗s k2 + zbi2 kb∗i k2 ≤ i=s+1 ≤ 2s n X ! zbi2 kb∗i k2 = i=s+1 2 = 2s kB ∗ zbk ≤ 2n kB ∗ zbk2 = 2n kBb x − tk2 Jelöljük λi -vel a

ht−Bx,b∗i i mennyiséget! hb∗i ,b∗i i A t+P (B ∗ ) téglán belüli rácspont kereséshez vegyük a következ® algoritmust: 2.12 Algoritmus indexre dλi c = 0, Vegyük bemenetként az akkor leállunk. x ∈ Zn vektort! Ha minden Különben pedig vegyük a legnagyobb  i indexet, melyre dλi c 6= 0 2.13 Állítás Ez az algoritmus polinomiális id®ben visszaad egy olyan  x vektort, melyre erre xi := xi + dλi c. Bx ∈ t + P (B ∗ ) tetsz®leges input vektor esetén Bizonyítás.A bizonyítás hasonlóan m¶ködik mint a 123 algoritmus m¶ködésének bizonyítása 2.2 Bonyolultság Lagarias megmutatta, hogy az SVP NP-nehéz k.k∞ normában. Van Embde Boas belátta, hogy a CVP probléma minden p-normában nézve NPnehéz. Hosszú ideje kérdés, hogy az SVP euklideszi normában NP-nehéz-e 1997-ben Ajtai bebizonyította az NP-nehézséget véletlen redukció alatt, az általánosan vett feladat bonyolultságelméleti osztálya viszont még

mindig 13 http://www.doksihu nyitott kérdés. A CVP alapvet®en nem eldöntési kérdés, hanem optimalizálási feladat, azonban könnyen átalakíthatjuk a következ® kérdéssé: van-e a rácsban a célvektorhoz legfeljebb  r  távolságra található vektor. Természetesen, amikor a következ® alfejezetben a CVP NP-teljességér®l beszélünk, ezt a problémát fogjuk visszavezetni más NP-teljes feladatra. 2.3 CVP NP-teljes Ismert, az NP-teljes részhalmaz-összeg(subset-sum) probléma: adott Zn , b, M ∈ Z paraméterekre keresend® az ha, xi ≡ b kielégít® {0, 1} n -beli  x vektor. a∈ (mod M ) kongruenciát Ennek segítségével fogjuk belátni a CVP probléma NP-teljességét. Vegyük a  M a1 · · · an   0  B :=  .  .  0 In        bázis által generált rácsot. Keressük ebben a   b    1/2    t :=  .   .    1/2 vektorhoz legközelebbi rácsvektort. Mivel

az dinátásak a t-t®l való távolság legalább pn 4 L (B) elemei mind egész koor- . Tegyük fel, hogy a részhalmaz-összeg problémánk kielégíthet®, találtunk x ∈ Zn -et és y ∈ Z-t, melyekre ha, xi = b − yM . Ekkor ! ! 2 ! 2 y ha, xi + yM − b 0 B −t = = x x − 1/2 x − 1/2 ! y azaz B  t-t®l minimális távolságra van. x olyan 14 2 = n , 4 http://www.doksihu A másik irányhoz tegyük fel, hogy a rácsunk egy adott B y ! x vektora n -nél közelebb van a célvektorhoz. Ekkor felírható, hogy 4 n ≥ B 4 Itt az x − 1/2 y 2 ! −t x = (ha, xi + yM − b)2 + kx − 1/2k2 . vektor hossza akkor minimális, ha  x valóban egy 0-1 ka- rakterisztikus vektor. Ekkor a hossz-négyzete n . Ilyenkor az egyenl®tlenség 4 továbbalakítható: 0 ≥ (ha, xi + yM − b)2 ⇒ ha, xi + yM − b = 0, ami azt jelenti, hogy  x megoldása az adott részhalmaz-összeg kérdésnek. 3. Kísérletek prímfaktorizálásra 3.1 Alapok, Schnorr

algoritmusa Ebben a fejezetben az lesz a f® célunk, hogy polinomiális id®ben megtaláljuk egy adott N ∈N szám faktorait. Módszerünk alapját az képzi, hogy ha az x2 ≡ y 2 kongruenciára találunk ahol x 6≡ ±y (mod N ) (x, y) ∈ Z × Z (mod N ), akkor N | (x − y) (x + y) miatt (x + y, N )  N -nek nem-triviális megoldást, azaz olyat & N - (x ± y) valódi faktora lesz. Míg ha  N  prím szám, minden megoldás triviális, a következ® állítás azt mutatja, hogy összetett szám esetén reménykedhetünk abban, hogy egy véletlenszer¶en vett megoldást felhasználhatunk 3.11 Állítás 2 Z Tegyük fel, hogy  N  páratlan összetett szám, és az N-el külön-külön relatív prím számpár kielégíti a kongruenciát. legalább 1/2 valószín¶sséggel teljesül, hogy 15 x 6≡ ±y (mod N ) (x, y) ∈ Ekkor http://www.doksihu Bizonyítás.Bontsuk fel  N -et: N = P · Q, ahol (P, Q) = 1. Rögzítsük a megoldásból 

x-et. Ekkor a két triviális megoldáshoz (±x), mutatunk két nem-triviálisat. A kínai maradéktétel szerint a y≡x (mod P ) y ≡ −x (mod Q) rendszernek  y -ra pontosan egy megoldása van (mod N ). Ekkor (x, ±y) két nem-triviális megoldása lesz az els®nek (minden feltétel könnyen ellen®rizhet®). Vezessünk be néhány jelölést! 3.12 Deníció Nevezzünk K-simának (K-smooth) az N természetes szá- mot, amennyiben N mentes a K-nál nagyobb prímfaktoroktól. Jelölje pi az  i-edik prímszámot! 3.13 Algoritmus (Schnorr) (1) Bemenetként vegyük az N számot, amit faktorizálni szeretnénk. (2) Állítsuk be a  d dimenziót, és a között szerepel a p1 , p2 . , pd C > 1 konstanst. Ha N faktorai prímek valamelyike, akkor adjuk vissza, és álljunk le. Ellenkez® esetben vegyük a  d és  C  értékekhez tartozó (a kés®bbiekben részletezend®) Sp rácsot, majd egészítsük ki az els® darab prímet tartalmazó

listánkat a (3) Keressünk d+2 darab p0 := −1-el. (ui , ki ) ∈ N × Z számpárt, ahol ui pd -sima, teljesül az |ui − ki N | ≤ pd egyenl®tlenség. Faktorizáljuk az ui = d Y ui , valamint az a pj i,j , ai,0 = 0 j=0 ui − ki N = d Y j=0 16 d pbi,j j ui − ki N számokat: és http://www.doksihu (4) Vegyük az N aj,i , (d+1)×(d+2) valamint a bj,i , kitev®k által generált  A, illetve  B  -beli mátrixokat (j a sor-, i az oszlopindex) (5) Tekintsük az (A + B) c ≡ 0 c ∈ {0, 1}d+2 egyenlet egy (mod 2) megoldását. (6) Vegyük az x := d Y ((A+B)c)j /2 pj i=0 és y := d Y (Ac)j pj i=0 számokat. x 6= ±y Amennyiben (x + y, N )-et. (mod N ), adjuk vissza értékként Különben pedig próbálkozzunk meg az 5. lépésben lév® egyenlet egy másik megoldásával. 3.14 Megjegyzés Els® ránézésre nem biztos, hogy világos a  c vektor szerepe. Ž egy karakterisztikus vektor: kiválasztja, hogy mely

ui számok szor- zata legyen az  y  szám: y= d Y (Ac) pj j = d+2 Y uci i ≡ Ez alapján máris megvan, hogy 2 x = d Y ((A+B)c)j pj ci (ui − ki N ) ≡ i=1 i=1 i=0 d+2 Y = i=0 (Bc)j pj (mod N ) . i=0 (x, y) d Y d Y megfelel az els®dleges célunknak, azaz (Ac) pj j i=0 · d Y (Bc)j pj ≡ y2 (mod N ) i=0 Az algoritmus m¶ködéséhez persze kell, hogy a 3. lépésben megfelel® számpárokat találjunk Valójában ez a lépés viszi el majdnem a teljes futásidejét az algoritmusnak. A következ®kben ilyen jelleg¶ számpároknak az észlelhet®ségéhez fogunk feltételt adni Az |ui − ki N | ≤ pd feltételt általánosítva vehetjük a következ® problémát: 17 http://www.doksihu 3.15 Probléma Legyen d≥1 rögzített állandó, és  N  legfeljebb (u, v, k, γ) toroktól mentes természetes szám. Keresend® d+2 darab gyes, ahol  u és  v  γ ∈ N+ , pd -sima pd fak- számné- egészek,  k  és  N  relatív

prímek, valamint amelyek teljesítik a következ® feltételt: u = v + kN γ (1) 3.2 Rácsok Adleman prím-rácsa az alábbi  √ p ln p1     Ap :=     Ap mátrix (oszlopai) által generált rács. 0 0 0 0  0 0 0 √ p ln pd 0         0 √ p ln p2 0 0 0 . 0 0 0 . 0 C ln p1 C ln p2 · · · C ln pd C ln N Ekkor a rács elemeit felírhatjuk √ z1 p ln p1 √ z2 p ln p2      Ap z =       . . . √ zn p ln pn C P d i=1 zi ln pi + zd+1 ln N           alakban. A rácsvektorok hossza: kAp zkpp = d X |zip | ln pi +C p i=1 3.21 Tétel Legyen C >1 d X p zi ln pi + zd+1 ln N i=1 konstans és z ∈ Zd+1 nem-0 utolsó koordiná- tával, ahol az utolsó koordinátának abszolútértékét jelöljük γ := |zd+1 |-val. Ekkor amennyiben találunk a rácsban megfelel® rövid kA1 zk1 ≤ 2 ln C + 2σ ln pd − γ ln N,

tudunk mutatni ehhez a  z vektorhoz tartozó megfelel® |u − kN γ | ≤ pσd 18 (2) u, k számokat, hogy http://www.doksihu Bizonyítás.El®ször zd+1 is feltehetjük, hogy az utolsó koordináta negatív, ellenkez® esetben vehetjük a vektorunk additív inverzét. Legyenek az u, k, γ számok a következ®ek: Y u := pzi i , i, zi >0 |z | Y k := pi i i, zi <0 γ := |zd+1 | Célunk belátni, hogy ezek eleget tesznek az állításnak. Az áttekinthet®ség érdekében nevezzük el a (2) egyenl®tlenség jobb oldalát: ε := 2 ln C + 2σ ln pd − γ ln N Ezek alapján kA1 zk1 = ln u + ln k + C |ln u − ln (kN γ )|p < ε Vegyük észre, hogy ez az egyenl®tlenség szimmetrikus u ≥ kN γ , ezért feltehetjük, hogy u-ban és kN γ -ban, így elhagyhatjuk az abszolút értéket, és átrendezve az egyenl®tlenséget ezt kapjuk: γ kN ≤ u ≤ k Tehát u − kN γ C−1 C+1 ·N Cτ C+1  · exp ε C +1  értékét felülr®l

becsülhetjük ezzel a különbséggel: γ u − kN ≤ k Vegyük ezt az értéket, mint C−1 C+1 k ·N Cτ C+1  · exp ε C +1  − kN γ függvényét és vizsgáljuk, hogy hol veheti fel a maximumhelyét, vagyis, hogy hol nulla a k szerinti deriváltja:  C −1 C +1  · − 2 k0 C+1 ·N Cτ C+1  · exp ε C +1  − Nγ = 0 −1   τ C −1 ε C+1 = ·N · exp − C +1 C +1 C+1   ε C −1 2 − τ2 k0 = · N · exp C +1 2 − 2 k0 C+1 (3)  19 http://www.doksihu Behelyettesítve (3)-be u − kN γ ≤  ≤ C −1 C +1  C−1 2 ·N τ (C−1) − 2(C+1)  C −1 C +1  ε (C − 1) 2 (C + 1) · exp  C+1 2 τ · N − 2 · exp ! ·N Cτ C+1  · exp ε C +1  − ε Nγ = 2   C−1  ε   C − 1  C+1 ε 2 τ τ C −1 2 · N 2 · exp · N 2 · exp = − = C +1 2 C +1 2   C−1 ε  2  τ C −1 2 · N 2 · exp · C +1 2 C +1 − 3.22 Lemma  C > 1 =⇒ C −1 C +1   C−1 2 2 C +1  ≤ 1 C

Bizonyítás. (C − 1) · C +1 C −1 + (2C) · 1 = (C + 1) · 2 2 Ezért felírhatjuk a logaritmus függvényre az alábbi (súlyozott) Jensen-esgyenl®tlenséget: ln (C − 1) · C −1 C +1 + ln(2C) · 1 ≤ ln (C + 1) · 2 2 (C − 1) C−1 2 · 2C ≤ (C + 1) C+1 2 Amib®l átrendezve kapjuk a lemmánk állítását. Ezt felhasználva az egyenl®tlenséget tovább alakíthatjuk: u − kN γ ≤ Ebbe visszaírva ε-t, ε τ 1 · N 2 · exp C 2 pont a bizonyítandó állítást kapjuk. 20 http://www.doksihu 3.23 Megjegyzés hogy megfelel® Ha a tételben szerepl®  σ  paraméter 1, az garantálja, pd -sima u, v := u − kN γ számokat kapunk, melyek így meg- oldását adják (1) egyenletnek. Viszont amennyiben nem lényegesen nagyobb mint 1, még mindig reménykedhetünk benne, hogy teljesülni fog a pd -simaság. Ez alapján a következ® lehet®ségünk adódik a faktorizálásra : 1-es normában rövid vektorokat keresünk az A1 rácsban, majd

ellen®rizzük, hogy az ezek se- gítségével legyártott számok valódi megoldását adják-e (1)-nek egészen addig, míg legalább d+2 ilyen össze nem gy¶lik. Ha ezt sikerült elérni, akkor tudjuk alkalmazni a Schnorr-algoritmust ezek segítségével. 3.24 Megjegyzés A tétel segíthet annak vizsgálatában, hogy van-e d+2 darab megoldás a (1) egyenl®ségre a Minkovski-tétel felhasználásával, ami explicit becslést ad a legrövidebb vektor hosszára. 3.25 Megjegyzés Mivel a rácsalgoritmusok többsége euklideszi normával dolgozik, hasznos lenne egy az el®bbiekhez hasonló tétel, mely k.k2 -ban mérve kis vektorokból indul ki. Egy másik hasonló útként vegyük a következ® Sp mátrix (oszlopai) által ge- nerált rácsot(Sperner prím rácsa ).  √ p     Sp :=     ln p1 0 √ p 0 0 ln p2 0 0 0 0 C ln p1 C ln p2  0      t :=     0         0 C ln N 21

     .  . 0  √ 0 p ln pd   · · · C ln pd 0 A rácsvektorok között keressünk a . . . 0 0 http://www.doksihu vektorhoz közel lév®ket. A  t-t®l való távolságvektor: √ z1 p ln p1 √ z2 p ln p2      Sp z − t =      kSp z − tkpp = d X . . . √ zn p ln pn C P d i=1 zi |zip | ln pi +C ln pi − ln N p d X i=1 3.26 Tétel Legyen C>1            p zi ln pi − ln N i=1 konstans és a rácsban  t-hez elegend®en közeli S1 z z ∈ Zd , Ekkor amennyiben találunk vektort: kS1 z − tk1 ≤ 2 ln C + 2σ ln pd − ln N, tudunk mutatni ehhez a  z vektorhoz tartozó u, k számokat |u − kN | ≤ pσd Bizonyítás.A tétel és a bizonyítás egy az egyben az Adleman rácsára vo- natkozó megfelel®je a γ=1 3.27 Megjegyzés N faktorizálásához itt  t-hez közeli esetben. S1 -beli rácsvektoro- kat kell keresnünk. Adleman

módszerének megvan az az el®nye, hogy nagyobb területen van esélye vektorokat találni. A gyakorlat azonban azt mutatja, hogy az így megtalált valóban használható megoldások - amelyek kielégítik az (1)hez tartozó feltételeket - pont azok, amelyeket Schnorr megközelítése ad. 3.28 Megjegyzés Csakúgy mint az el®bbiekben, ennek a tételnek euklide- szi normával számoló megfelel®je is segítene a gyakorlatban. 22 http://www.doksihu 4. Összefoglalás A. B. Jelölések log 2-es alapú logaritmus (a, b) az  a és  b természetes számok legnagyobb közös osztója bxe az  x valós szám kerekített értéke Z az egész számok halmaza Q a racionális számok halmaza R a valós számok halmaza pi az  i-edik prím szám λ (L) Az  L rácsban a legrövidebb nem-nulla vektor hossza Felhasznált irodalom Hivatkozások [1] J.-Y Cai Some Recent Progress on Complexity of Lattice Problems In Proc of FCRC, 1999. [2] Kajtár M. Cons

Grolmusz V Lattice Theory in Cryptography, 2008 [3] Lovász L. An Algorithmic Theory of Numbers, Graphs and Convexity a CBMS-NSF Regional Conference Series in Applied Mathematics, SIAM, Philadelphia, 1986. [4] D. Micciancio, A Yannakopoulos and N Segerlind Lattices in Cryptography and Cryptanalysis Lecture 10, CSE 291, 1999 [5] C. P Schnorr Factoring integers and computing discrete logarithms via diophantine approximation. In Advances in Computational Complexity Theory, J.-Y Cai, Ed, vol 13 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science. AMS, 1993 23 http://www.doksihu [6] A. I Vera A Note on Integer Factorrization Using Lattices CACAO Project, INRIA Nancy Grand-Est, 2010 24