Alapveto˝ polinomalgoritmusok
• Maradékos osztás • Euklideszi algoritmus • Bovített ˝ euklideszi algoritmus • Alkalmazás: Véges testek konstrukciója
Irodalom: Iványi Antal: Informatikai algoritmusok II, 18. fejezet.
Maradékos osztás
Számítsuk ki a (2x 4 + 3x 2 − 1)/(x 2 + x + 1) hányadost: 2x 4 + 3x 2 − 1 = (2x 2 − 2x + 3)(x 2 + x + 1) + (−x − 4). • Hányados: 2x 2 − 2x + 3 • Maradék: −x − 4
Maradékos osztás
Számítsuk ki a (2x 4 + 3x 2 − 1)/(x 2 + x + 1) hányadost: 2x 4 + 3x 2 − 1 = (2x 2 − 2x + 3)(x 2 + x + 1) + (−x − 4). • Hányados: 2x 2 − 2x + 3 • Maradék: −x − 4
Maradékos osztás polinomokkal A továbbiakban F egy test.
Theorem (Maradékos osztás tétele) Legyenek f , g ∈ F[x] legfeljebb n-edfokú polinomok és legyen g 6= 0. Ekkor egyértelmuen ˝ léteznek q, r ∈ F[x] melyekre: (i) f = qg + r és (ii) r = 0 vagy deg r < deg g. A fenti q és r polinomok O(n2 ) aritmetikai muvelet ˝ segítségével kiszámíthatók.
Bizonyítás. Létezés: deg f szerinti indukció. ˝ Ha deg f < deg g akkor Ha f = 0 akkor q = r = 0 megfelelo. ˝ q = 0 és r = f megfelelo.
Maradékos osztás polinomokkal A továbbiakban F egy test.
Theorem (Maradékos osztás tétele) Legyenek f , g ∈ F[x] legfeljebb n-edfokú polinomok és legyen g 6= 0. Ekkor egyértelmuen ˝ léteznek q, r ∈ F[x] melyekre: (i) f = qg + r és (ii) r = 0 vagy deg r < deg g. A fenti q és r polinomok O(n2 ) aritmetikai muvelet ˝ segítségével kiszámíthatók.
Bizonyítás. Létezés: deg f szerinti indukció. ˝ Ha deg f < deg g akkor Ha f = 0 akkor q = r = 0 megfelelo. ˝ q = 0 és r = f megfelelo.
Maradékos osztás polinomokkal Bizonyítás (folytatás). Legyen f = α0 + α1 x + · · · + αk x k és g = β0 + β1 x + · · · + βm x m ahol αk , βm 6= 0 és k > m. Legyen q ∗ = (αk /βm )x k −m és legyen f1 = f − q ∗ g. Ekkor deg f1 < deg f és alkalmazható az indukciós feltevés: f1 = q1 g + r1
ahol r1 = 0 vagy deg r1 < deg g.
Kapjuk, hogy q1 g + r1 = f1 = f − q ∗ g ⇒ f = (q ∗ + q1 )g + r1 . A fenti felbontás jó.
Maradékos osztás polinomokkal Bizonyítás (folytatás). Egyértelmuség: ˝ Legyen f = q1 g + r1 = q2 g + r2 két megfelelo˝ felbontás. Ekkor (q1 − q2 )g = r2 − r1 A jobboldali polinom foka legfeljebb deg g − 1. Ha q1 6= q2 akkor a baloldali polinom foka legalább deg g. Ezért q1 = q2 és r1 = r2 . Költség: egy lépés költsége O(n) aritmetikai muvelet. ˝ Legfeljebb n lépést kell végrehajtani, így a költség O(n2 ) aritmetikai muvelet. ˝
Maradékos osztás polinomokkal Bizonyítás (folytatás). Egyértelmuség: ˝ Legyen f = q1 g + r1 = q2 g + r2 két megfelelo˝ felbontás. Ekkor (q1 − q2 )g = r2 − r1 A jobboldali polinom foka legfeljebb deg g − 1. Ha q1 6= q2 akkor a baloldali polinom foka legalább deg g. Ezért q1 = q2 és r1 = r2 . Költség: egy lépés költsége O(n) aritmetikai muvelet. ˝ Legfeljebb n lépést kell végrehajtani, így a költség O(n2 ) aritmetikai muvelet. ˝
Euklideszi algoritmus polinomokra Legyenek f , g ∈ F[x] \ {0}. Legyen f0 = f , f1 = g, és képezzük a qi is fi polinomokat maradékos osztással: f0 = q1 f1 + f2 f1 = q2 f2 + f3 .. . fk −2 = qk −1 fk −1 + fk fk −1 = qk fk + fk +1 , ahol fk +1 = 0. Mivel deg fi < deg fi+1 az eljárás véges sok lépésben véget ér. Könnyu˝ látni: fk = gcd(f , g).
Euklideszi algoritmus: Példa Legyen f = f0 = 2x 4 + 3x 2 − 1, g = f1 = x 2 + x + 1 ∈ Q[x]. Euklideszi algoritmus: 4 3x 2 − 1} = (2x 2 − 2x + 3) (x 2 + x + 1) + (−x − 4) |2x + {z | {z }| {z } | {z } f0
q1
f1
f2
2
13 x + 1} = (−x + 3) (−x − 4) + |{z} |x +{z | {z } | {z } f1
q2
f2
f3
−x − 4/13) · |{z} 13 + |{z} 0 | {z− 4} = ((−1/13)x | {z } f2
q3
f3
Tehát fk = f3 = gcd(f , g) = 13 ∼ 1 (asszociáltak!).
f4
˝ Bovített euklideszi algoritmus Ha f , g ∈ F[x], deg f , deg g 6 n akkor léteznek F , G ∈ F[x] melyekre deg F , deg G 6 n és Ff + Gg = gcd(f , g). Valóban, az euklideszi algoritmus szerint, f2 = f0 − q1 f1 = f − q1 g f3 = f1 − q2 f2 = f1 − q2 (f0 − q1 f1 ) = (1 + q1 q2 )g − q2 f .. . Tehát minden i ∈ {2, . . . , k } esetén létezik Fi , Gi ∈ F[x] melyre Fi f + Gi g = fi teljesül.
˝ Bovített euklideszi algoritmus Legyen Fi = qi g + Fi∗ és Gi = si f + Gi∗ , ahol deg Fi∗ < deg g és deg Gi∗ < deg f . Mivel Fi f + Gi g = fi , Fi∗ f + Gi∗ g = (Fi − qi g)f + (Gi − si f )g = = Fi f − qi fg + Gi g − si fg ≡ Fi f + Gi g = fi mod fg. Mivel a kongruencia mindkét oldalán a polinomok foka kisebb mint deg f + deg g, Fi∗ f + Gi∗ g = fi . Speciálisan: Fk∗ f + Gk∗ g = fk = gcd(f , g).
˝ Bovített euklideszi algoritmus Theorem Legyenek f , g ∈ F[x] legfeljebb n-edfokú polinomok. Ekkor léteznek F , G ∈ F[x] legfeljebb n-edfokú polinomok, melyekkel Ff + Gg = gcd(f , g). Továbbá gcd(f , g), F és G meghatározhatók legfeljebb O(n3 ) aritmetikai muvelettel. ˝
Bizonyítás. Az fi , Fi∗ és Gi∗ polinomok O(n2 ) aritmetikai muvelettel ˝ ˝ kiszámíthatók (ellenorizzük). Mivel legfeljebb n lépést kell végezni, a gcd(f , g), F , G polinomok O(n3 ) muvelettel ˝ meghatározhatók.
˝ Bovített euklideszi algoritmus Theorem Legyenek f , g ∈ F[x] legfeljebb n-edfokú polinomok. Ekkor léteznek F , G ∈ F[x] legfeljebb n-edfokú polinomok, melyekkel Ff + Gg = gcd(f , g). Továbbá gcd(f , g), F és G meghatározhatók legfeljebb O(n3 ) aritmetikai muvelettel. ˝
Bizonyítás. Az fi , Fi∗ és Gi∗ polinomok O(n2 ) aritmetikai muvelettel ˝ ˝ kiszámíthatók (ellenorizzük). Mivel legfeljebb n lépést kell végezni, a gcd(f , g), F , G polinomok O(n3 ) muvelettel ˝ meghatározhatók.
˝ Bovített euklideszi algoritmus: Példa Legyen f = f0 = 2x 4 + 3x 2 − 1 és g = f1 = x 2 + x + 1. Euklideszi algoritmus: 1 · (2x 4 + 3x 2 − 1) − (2x 2 − 2x + 3) (x 2 + x + 1) |−x{z− 4} = |{z} | {z } | {z }| {z } ∗ F2 =F2
f2
f
G2 =G2∗
g
13 = (x 2 + x + 1) − (−x + 3)(−x − 4) = = (x 2 + x + 1) − (−x + 3)((2x 4 + 3x 2 − 1)− − (2x 2 − 2x + 3)(x 2 + x + 1)) = = −(−x + 3) (2x 4 + 3x 2 − 1) + (−2x 3 + 8x 2 − 9x + 10) (x 2 + x + 1) {z } | {z }| {z } | {z } | F3 =F3∗
f
G3 =G3∗
g
Tehát 13 = −(−x +3)(2x 4 +3x 2 −1)+(−2x 3 +8x 2 −9x +10)(x 2 +x +1) és 1 = −((−1/13)x + 3/13)(2x 4 + 3x 2 − 1)+ + ((−2/13)x 3 + (8/13)x 2 − (9/13)x + 10/13)(x 2 + x + 1)
Polinommuveletek ˝ költsége
(i) Összeadás: O(n) (ii) Szorzás: O(n2 ) (Schönhage-Strassen: O(n log n log log n)) (iii) Maradékos osztás: O(n2 ) (iv) gcd, F és G melyekkel Ff + Gg = gcd(f , g): O(n3 ) A fenti muveletek ˝ költsége n-ben polinomiális, tehát a fenti ˝ muveletek ˝ hatékonynak tekinthetok.
Alkalmazás: Véges testek
Egy kommutatív egységelemes gyur ˝ uben ˝ az invertálható elemeket egységeknek nevezzük. F[x]-ben a skalárok (nulladfokú polinomok) az egységek. f ∈ F[x] esetén mik az egységek F[x]/(f )-ben?
Invertálás F[x]/(f )-ben
1 = −((−1/13)x + 3/13)(2x 4 + 3x 2 − 1)+ + ((−2/13)x 3 + (8/13)x 2 − (9/13)x + 10/13)(x 2 + x + 1) Moduló 5 átírva, F5 [x]-ben kapjuk: 1 = (2x + 4)(2x 4 + 3x 2 + 4) + (x 3 + x 2 + 2x)(x 2 + x + 1) Tehát F5 [x]-ben (x 3 + x 2 + 2x)(x 2 + x + 1) ≡ 1 mod 2x 4 + 3x 2 + 4. Azaz x 3 + x 2 + 2x + (2x 4 + 3x 2 + 4) inverze x 2 + x + 1 + (2x 4 + 3x 2 + 4).
Invertálható elemek faktorgyur ˝ ukben ˝ Lemma Legyenek f , g ∈ F[x]. Ekkor f + (g) ∈ F[x]/(g) egység, akkor és csakis akkor, ha gcd(f , g) = 1. Ha F , G ∈ F[x] melyekkel Ff + Gg = 1, akkor (f + (g))−1 = F + (g). ˝ Tehát az f + (g) elem inverze a bovített euklideszi algoritmussal meghatározható.
Bizonyítás. f invertálható moduló g ⇔ létezik s ∈ F[x] mellyel fs ≡ 1 (mod g) ⇔ létezik s, t ∈ F[x] mellyel sf + tg = 1 ⇒ gcd(f , g) = 1. Ha gcd(f , g) = 1, akkor léteznek F , G ∈ F[x] melyekre Ff + Gg = 1. Ekkor 1 = Ff + Gg ≡ Ff (mod g).
Invertálható elemek faktorgyur ˝ ukben ˝ Lemma Legyenek f , g ∈ F[x]. Ekkor f + (g) ∈ F[x]/(g) egység, akkor és csakis akkor, ha gcd(f , g) = 1. Ha F , G ∈ F[x] melyekkel Ff + Gg = 1, akkor (f + (g))−1 = F + (g). ˝ Tehát az f + (g) elem inverze a bovített euklideszi algoritmussal meghatározható.
Bizonyítás. f invertálható moduló g ⇔ létezik s ∈ F[x] mellyel fs ≡ 1 (mod g) ⇔ létezik s, t ∈ F[x] mellyel sf + tg = 1 ⇒ gcd(f , g) = 1. Ha gcd(f , g) = 1, akkor léteznek F , G ∈ F[x] melyekre Ff + Gg = 1. Ekkor 1 = Ff + Gg ≡ Ff (mod g).
Véges testek konstrukciója Corollary Ha f ∈ F[x] irreducibilis polinom, akkor F[x]/(f ) egy test. Speciálisan, ha f ∈ Fp [x] irreducibilis és deg f = n, akkor Fp [x]/(f ) ∼ = Fp n .
Example 2x 4 + 3x 2 + 4 ∈ F5 [x] irreducibilis, ezért F5 [x]/(2x 4 + 3x 2 + 4) ∼ = F625 .
Corollary Legyen f ∈ F[x], deg f = n. Ekkor az F[x]/(f ) testben az összeadás költsége O(n), egy szorzás költsége O(n2 ), egy invertálás költsége pedig O(n3 ) muvelet ˝ F-ben.
