Faktorizace cˇ ísel pomocí rˇ etˇezových zlomku˚ Tento text se zabývá algoritmem CFRAC (continued fractions algorithm) pro rozkládání velkých cˇ ísel (typicky souˇcin˚u dvou velkých prvoˇcísel). Nebudeme se zde zabývat základy teorie ˇretˇezových zlomk˚u, pˇri d˚ukazech se bude pˇredpokládat, že je s ní již cˇ tenáˇr obeznámen. D˚uraz bude kladen na implementaˇcní stránku, protože ta je ve vˇetšinˇe text˚u hrubˇe zanedbávána a autoˇri si obvykle vystaˇcí s vˇetou: „Pˇredpokládejme, že máme posloupnost ˇretˇezových zlomk˚u. . . “ Algoritmus CFRAC je historicky prvním algoritmem, který využívá tzv. Newton˚uv faktorizaˇcní algoritmus. Pˇri nˇem se rozkládá velké cˇ íslo N tím, že se hledají dvojice cˇ ísel xi , yi splˇnující xi ≡ y2i (mod N). Až se nalezne dostateˇcné množství takovýchto dvojic, vybere pouze podmnožina I Q index˚u taková, aby souˇcin vybraných xi byl cˇ tverec (neboli i∈I xi = x2 pro nˇejaké x). Q Oznaˇcíme-li y = i∈I yi , dostaneme vztah x2 ≡ y2
(mod N)
a z tohoto vztahu vyplývá (x − y)(x + y) ≡ 0
(mod N).
Pokud byly hodnoty xi a yi a množina I vybrány opravdu náhodnˇe, máme pravdˇepodobnost asi 50 %, že x − y a N mají spoleˇcného vlastního dˇelitele. Tímto se nalezne jeden dˇelitel cˇ ísla N, což obvykle staˇcí, nebot’ v praxi se nejˇcastˇeji potˇrebuje rozkládat souˇcin dvou prvoˇcísel.
ˇ ezové zlomky Retˇ V algoritmem CFRAC se dvojice kongruentních cˇ ísel konstruují tak, že se poˇcítá rozvoj √ cˇ ísla N do ˇretˇezového zlomku, neboli do tvaru √
1
N = a0 +
1
a1 + a2 +
.
1 a3 + · · ·
ˇ Císlo N pochopitelnˇe nesmí být perfekní cˇ tverec, ale v takovém pˇrípadˇe bychom už mˇeli rozklad N pˇrímo. √ pn = [a0 , a1 , . . . , an ] a N = [a0 , . . . , an−1 , αn ]. Koeficienty an lze urˇcitˇe Oznaˇcme qn spoˇcítat pomocí αn = (αn−1 − an−1 )−1 a an = [αn ], ale tento postup vyžaduje použití reálných cˇ ísel, cˇ emuž bychom se chtˇeli vyhnout. Proto je lepším postupem použití následujících posloupností:
1
Tvrzení: Bud’te Pn a Qn posloupnosti celých cˇ ísel definované induktivnˇe: P0 = 0, Q0 = 1 a N − P2n+1 . Pn+1 = an Qn − Pn , Qn+1 = Qn Pak platí √ √ Pn + [ N] Pn + N . αn = a an = Qn Qn D˚: Výše uvedené vztahy platí pro n = 0, pˇredpokládejme nyní, že platí až do nˇejakého n ≥ 0. Máme √ √ Qn+1 Qn+1 ( N − Pn+1 ) N − a n Qn + P n = √ = 2 Qn N − Pn+1 Pn+1 + N √ N + P n a n Qn 1 − = αn − an = = Qn Qn αn−1 Ještˇe potˇrebujeme, že cˇ ísla Pn a Qn jsou celá. Platí N − P2n+1 = N − (an Qn − Pn )2 =
= N − P2n − a2n Q2n + 2an Qn Pn = Qn (Qn−1 − a2n Qn + 2an Pn )
a celoˇcíselnost se snadno dokáže indukcí. Vzorec pro an plyne z an = [αn ] a faktu, že Pn a Qn jsou celá cˇ ísla. ˇ Císla Qn ve dvojici s pn−1 tvoˇrí hledané dvojice pro Newtonovu faktorizaci: Tvrzení: Pro každé n platí p2n−1 − Nq2n−1 = (−1)n Qn . √ ˇ D˚: Císlo N se dá, pro každé n, rozepsat jako √ αn pn−1 + pn−2 . N= αn qn−1 + qn−2 Po dosazení za αn dostaneme √ √ √ N (Pn + N)qn−1 + Qn qn−2 = (Pn + N)pn−1 + Qn pn−2 , což po úpravˇe dává √ √ Nqn−1 + (Pn qn−1 + Qn qn−2 ) N = Pn pn−1 + Qn pn−2 + pn−1 N. √ Tato rovnost je v Q( N) splnˇena právˇe když platí pn−1 = Pn qn−1 + Qn qn−2 a Nqn−1 = Pn pn−1 + Qn pn−2 . Po vynásobení prvního ˇrádku pn−1 a druhého qn−1 a jejich odeˇctení dostaneme p2n−1 − Nq2n−1 = Pn pn−1 qn−1 + Qn pn−1 qn−2 − Pn pn−1 qn−1 − Qn pn−2 qn−2 = (pn−1 qn−2 − pn−2 qn−1 )Qn = (−1)n Qn , což se mˇelo dokázat. 2
Poˇcítání posloupností Pro faktorizaci algoritmem CFRAC využijeme vztah (−1)n Qn ≡ p2n−1
(mod N).
ˇ Císla pn rostou pomˇernˇe rychle, nicménˇe my nepotˇrebujeme znát jejich pˇresnou hodnotu, nám ji staˇcí znát modulo N. Takže m˚užeme poˇcítat pn+1 ≡ an+1 pn + pn−1
(mod N).
Dále potˇrebujeme spoˇcítat cˇ ísla Pn , Qn a an . Vzorce, které jsme uvedli vyžadují provést dvojí dˇelení, a to pˇri výpoˇctu an+1 a pˇri výpoˇctu Qn+1 . Nicménˇe√v obou pˇrípadech se dˇelí cˇ íslem Qn , cˇ ehož se dá pˇri výpoˇctu využít. Oznaˇcíme g = [ N] a pˇrepíšeme vzorec pro výpoˇcet an ve formˇe dˇelení se zbytkem Pn + g = an Qn + rn ,
0 6 rn < Qn .
Pomocí rn se dá Pn vyjádˇrit jednodušeji: Pn+1 = an Qn − Pn = an Qn − (an Qn + rn − g) = g − rn . A zjednoduší se i výpoˇcet Qn : Lemma: Pro všechna n > 1 platí Qn+1 = Qn−1 + an (rn − rn−1 ). D˚: Máme N − P2n+1 = N − (an Qn − Pn )2 = N − P2n − a2n Q2n + 2an Qn Pn
= Qn (Qn−1 − a2n Qn + 2an Pn ) = Qn (Qn−1 + an (Pn + Pn − an Qn )) = Qn (Qn−1 + an (Pn − Pn+1 ))
= Qn (Qn−1 + an (g − rn−1 − g + rn ) = Qn (Qn−1 + an (rn − rn−1 )) z cˇ ehož už plyne tvrzení vˇety.
Nyní shrneme celý výpoˇcet posloupností do struˇcného algoritmu. V praxi se cˇ asto cˇ íslo N násobí malým koeficientem k, aby mˇelo výhodnˇejší vlastnosti (viz níže). Proto se do ˇretˇezového zlomku rozvádí kN místo N. Potˇrebujeme spoˇcítat následující posloupnosti: pn , Qn , Pn , an a rn . Avšak místo Pn je vhodnˇejší pamatovat si cˇ íslo Pn + g. Algoritmus: (i) Urˇcíme malý koeficient k. √ (ii) Položíme Q0 ← 1, p−1 ← 1, r0 ← 0 a g ← [ kN]. (iii) Položíme Q1 ← kN − g2 , (P0 + g) ← g, a0 ← g, p0 ← g a (P1 + g) ← 2g. (iv) Položíme n ← 1 (v) Dˇelením se zbytkem spoˇcteme an a rn jako (Pn + g) = an Qn + rn . (vi) Spoˇcteme pn ← (an pn−1 + pn−2 ) mod N. (vii) Spoˇcteme (Pn+1 + g) ← 2g − rn . (viii) Spoˇcteme Qn+1 ← Qn−1 + an (rn − rn−1 ). (ix) Zvýšíme n o jednu a vrátíme se k bodu (v). 3
Pro výpoˇcty je d˚uležité vˇedˇet, jak velkých hodnot dosahují jednotlivé promˇenné. Je jasné, že pk je menší než N (je poˇcítáno modulo N). Pro ostatní promˇenné platí √ Lemma: Všechny hodnoty Pn + g, Qn , an a rn jsou nezáporné a menší než 2 kN . ˇ D˚: Císlo rn je podle definice nezáporné, takže z bodu (vii) je vidˇet Pn + g 6 2g. Dále pokraˇcujeme indukcí. Pˇredpokládejme, že všechny vztahy platí pro Pn + g a Qn−1 . Protože an je kladné, je i Qn kladné cˇ íslo. Dále z bodu (v) vyplývá an 6 2g a Qn 6 2g. Z definice máme rn < Qn . Takže okamžitˇe dostaneme Pn+1 + g > 0. Ve skuteˇcnosti platí dokonce Pn > 0, ale d˚ukaz tohoto faktu by byl složitˇejší. V algoritmu se provádí dvojí dˇelení – v krocích (v) a (vi). V mnoha pˇrípadech se ale nevyplatí dˇelit, protože cˇ íslo ak je v drtivé vˇetšinˇe hodnˇe malé, velice cˇ asto je dokonce rovno 1. Pak lze dˇelení nahradit odˇcítáním. Pˇríklad: Spoˇctˇeme posloupnosti pro N = 187 a k = 3. n 0 1 2 3 4 5 6 7 8
Pn + g 23 46 32 44 42 29 38 40 40
Qn an rn 1 20 0 32 1 14 15 2 2 8 5 4 25 1 17 21 1 8 16 2 6 17 2 6 16 2 8
pn−1 1 23 24 71 5 76 81 51 183
Qn rozloženo 25 3·5 23 52 3·7 24 17 24
Skombinováním 1. a 3. ˇrádku dostaneme 162 ≡ 1372 (mod 187) a cˇ íslo 137−16 = 121 má netriviálního spoleˇcného dˇelitele se 187, a to 11.
Hledání závislostí Hledáme takové souˇciny cˇ ísel (−1)n Qn , které dají cˇ tverec. To znamená, že mocniny v prvoˇcíselném rozkladu (−1 považujeme také za prvoˇcíslo) takovéhoto cˇ ísla jsou všechny sudé. Když provedeme rozklad každého z cˇ ísel (−1)n Qn na prvoˇcinitele a exponenty zapíšeme modulo 2 do matice, jejíž ˇrádky odpovídají n a sloupce prvoˇcísl˚um, úloha se pˇrevede na úlohu najít mezi ˇrádky matice netriviální kombinaci modulo 2. V praxi nerozkládáme všechna cˇ ísla Qn , dáváme si mez, jaká maximální prvoˇcísla povolíme v rozkladu cˇ ísel Qn . Prvoˇcísl˚um menším než tato mez se ˇríká faktorizaˇcní báze. Vyplatí se zaˇcínat s menší faktorizaˇcní bází a pˇrípadnˇe tuto bázi rozšiˇrovat, pokud se nepodaˇrí N rozložit pomocí malé faktorizaˇcní báze. Když nasbíráme pˇribližnˇe tolik rozložených cˇ ísel, jaká je délka faktorizaˇcní báze, m˚užeme hledat závislosti. Sepíšeme vedle sebe matici exponent˚u a jednotkovou matici
4
a provedeme Gaussovu eliminaci na ˇrádky v našem pˇríkladˇe bychom mˇeli
−32 15 −8 25 −21 16 −17 16
2 1 0 1 0 0 0 0 0
−1 1 0 1 0 1 0 1 0
3 0 1 0 0 1 0 0 0
5 0 1 0 0 0 0 0 0
7 11 13 17 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
2 0 1 0 0 0 0 0 0
3 0 0 1 0 0 0 0 0
4 0 0 0 1 0 0 0 0
5 0 0 0 0 1 0 0 0
6 0 0 0 0 0 1 0 0
7 0 0 0 0 0 0 1 0
8 0 0 0 0 0 0 0 1
což se Gaussovou eliminací pˇrevede na
∗ ∗ ∗ ∗
−1 1 1 0 1 0 0 0 0
2 0 0 0 1 0 0 0 0
3 0 1 1 0 0 0 0 0
5 0 0 1 0 0 0 0 0
7 0 1 0 0 0 0 0 0
11 13 17 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
2 0 0 1 0 0 0 0 0
3 0 0 0 0 1 0 0 0
4 0 0 0 0 0 1 0 0
5 0 1 0 0 0 0 0 0
6 0 0 0 0 0 0 1 0
7 1 0 0 0 0 0 0 0
8 0 0 0 0 0 0 0 1
pˇriˇcemž ˇrádky oznaˇcené ∗ se vynulovaly a matice napravo ukazuje, kombinací jakých ˇ ˇrádk˚u tu nulu dostaneme. Ctvrtý ˇrádek odpovídá již zmínˇené kongruenci 162 ≡ 1372 (mod 187), další ˇrádky kongruencím 52 ≡ 52 (mod 187), 42 ≡ 812 (mod 187) a 42 ≡ (−4)2 (mod 187). Matice, které dostaneme mají velice malou hodnost, protože cˇ ísla, která se dostanou jako Qn se cˇ asto opakují. Takže pokud nenalezneme vhodnou závislost pˇri dvojnásobném poˇctu ˇrádk˚u oproti sloupc˚um, obvykle se vyplatí spíše rozšíˇrit faktorizaˇcní bázi, než pokraˇcovat s tou stávající. √ Nˇekdy se stane, že pro sudé n je Qn cˇ tverec. Pak máme vztah Qn 2 ≡ An−1 (mod N) a m˚užeme rovnou vyzkoušet rozklad. V našem pˇríkladˇe toto nastane pro n = ˇ 4, 6, 8. Ctvrtý a osmý ˇrádek nám nic nedají, ale v šestém dostaneme 42 ≡ 812 (mod 187) a rozdíl 77 má se 187 netriviálního spoleˇcného dˇelitele. Ještˇe je vhodné poznamenat, že je rychlejší provádˇet Gaussovu eliminaci zprava doleva, protože sloupce odpovídající vyšším prvoˇcísl˚um jsou ménˇe zaplnˇeny jedniˇckami.
Malý koeficient Chtˇeli bychom volit faktorizaˇcní bázi tak, aby se co nejvíce cˇ ísel Qn rozložilo. Bohužel nˇekterá prvoˇcísla nemohou v žádném pˇrípadˇe Qn dˇelit. Je dobré je pˇredem odhalit a bud’to zaˇrídit, aby Qn mohla být tˇemito prvoˇcísly dˇelena, anebo tato prvoˇcísla vyˇradit z faktorizaˇcní báze.
5
Tvrzení: Pokud nˇejaké liché prvoˇcíslo p dˇelí nˇejaké cˇ íslo Qn , pak je Legendr˚uv symbol (kN/p) roven 0 nebo 1. D˚: Pˇredpokládejme, že p dˇelí Qn pro nˇejaké n > 1. Pak platí p2n−1 − kNq2n−1 ≡ 0 ˇ (mod p). Císla p2n−1 a q2n−1 jsou nesoudˇelná, takže p nem˚uže dˇelit q2n−1 . Takže máme 2 (pn−1 /qn−1 ) ≡ kN (mod p) a kN je kvadratické reziduum modulo p. Tvrzení: Necht’ 2 nedˇelí kN . Pokud je nˇejaké Qn dˇelitelné 4, respektive 8, pak je kN ≡ 1 (mod 4) respektive (mod 8). D˚: Necht’ j = 4 nebo j = 8. Pak j dˇelí Qn se dá zapsat jako p2n−1 − kNqn−1 ≡ 0 ˇ (mod j). Císla pn−1 a qn−1 jsou nesoudˇelná, takže žádné z nich nem˚uže být dˇelitelné 2. Tím dostaneme p2n−1 ≡ q2n−1 ≡ 1 (mod j) a nutnˇe kN ≡ 1 (mod j). Pˇri faktorizaci relativnˇe menšího N m˚užeme položit k = N mod 4 popˇrípadˇe k = N mod 8, cˇ ímž zajistíme, že cˇ ísla Qn budou moci být dˇelitelná 4 popˇrípadˇe 8, což je výhodné, nebot’ na poˇcítaˇci se dvojkou dˇelí velice snadno. Pˇri faktorizaci vˇetších cˇ ísel m˚užeme vyzkoušet vícero multiplikátor˚u k spoˇcítat Legendrovy symboly pro kN a nakonec si vybrat to k, pro které do faktorizaˇcní báze padne co nejvíce nejmenších √ prvoˇcísel. Musíme mít ale na pamˇeti, že cˇ ím je vˇetší k, tím je vˇetší i kN i kN a tím bude výpoˇcet složitˇejší. Když urˇcíme hodnotu k, vybíráme faktorizaˇcní bázi; do této báze vybíráme pouze ta prvoˇcísla, která mají správný Legendr˚uv symbol. Nesmíme zapomenout na dˇelitele cˇ ísla k – už jsme vidˇeli, že se vyskytují v rozkladu Qn . Velikost faktorizaˇcní báze se obvykle volí takto: ˇ Císlic vN FB ≤ 20 log2 (N) 21, 22, 23 150 24, 25 200 26, 27, 28 300 29, 30 400 31, 32 450 33, 34 500 35, 36 550 37, 38 600 39, 40 650
Literatura [1] H. C: „A Course in Computational Algebraic Number Theory“, Springer, (1993) [2] A. D´: „Teorie cˇ ísel“, text k pˇrednášce [3] M. A. M, J. B: A Method of Fatoring and the Factorization of F7 , Math. Comp., vol. 29, no. 129, (1975), 183–205
6
