A₧ dosud jsme se zab²vali zejmΘna bezpeΦnostnφmi k≤dy lineßrnφho typu. PoΦφnaje tφmto pokraΦovßnφm se postupn∞ p°esuneme do teorie k≤d∙ cyklick²ch, kterΘ tvo°φ d∙le₧itou a v praxi Φasto pou₧φvanou skupinu ECC.
JeÜt∞ ne₧ se pustφme do slφbenΘho tΘmatu, dovolφm si provΘst malou odboΦku a vysv∞tlit, jak²m sm∞rem se bude styl v²kladu v n∞kolika p°φÜtφch Φlßncφch ubφrat a proΦ. Vychßzφm z toho, ₧e tento serißl mß slou₧it hlavn∞ k pochopenφ teorie kolem ECC a k ukßzßnφ, ₧e v∞ci nemusφ b²t tak magickΘ a nesrozumitelnΘ û pouze je t°eba se zaobφrat i takov²mi "detaily", kterΘ se obvykle pova₧ujφ za "zbyteΦnΘ pitvßnφ" tΘmatu, a tudφ₧ se jaksi ne°φkajφ.
Na druhou stranu by bylo p°φliÜ naivnφ myslet si, ₧e na takto malΘm prostoru je mo₧nΘ prezentovat celou teorii ECC a navφc jeÜt∞ formßlnφm zp∙sobem. Budeme se zde proto sna₧it poukßzat zejmΘna na hlavnφ principy a souvislosti, o kterΘ se teorie bezpeΦnostnφch k≤d∙ opφrß. Nep∙jde nßm p°itom ani o podßnφ zcela p°esnΘho formßlnφho popisu, ani o vytvo°enφ monografie, se kterou si jako s jedin²m zdrojem informacφ vystaΦφme p°i implementaci ECC. NaÜφm cφlem bude si v₧dy p°φjemn∞ odpoΦinout a pop°em²Ület nad velmi zajφmavou matematickou teoriφ, kterß se m∙₧e navφc chlubit bohat²m praktick²m uplatn∞nφm.
Pro ·plnost jeÜt∞ p°ipomφnßm, abyste nevßhali pou₧φt mou e-mailovou adresu, kdykoliv budete mφt jakΘkoliv p°ipomφnky Φi dotazy k probφranΘmu tΘmatu.
AlgebraickΘ struktury
A₧ dosud jsme se v probφran²ch tΘmatech mohli spokojit s tφm, ₧e jsme pou₧φvali b∞₧nΘ matematickΘ operace "obvykl²m" zp∙sobem a p°φliÜ jsme nepßtrali po tom, jak moc bylo naÜe poΦφnßnφ korektnφ. Budeme-li vÜak chtφt sprßvn∞ pochopit zßklady cyklick²ch k≤d∙, nezbude nßm, ne₧ p°estat se spolΘhat na ony obvyklΘ principy a °φci si pßr slov o zßkladnφch algebraick²ch strukturßch a o zp∙sobu jejich pou₧φvßnφ.
Obecn∞ budeme za algebraickou strukturu pova₧ovat n∞jakou mno₧inu hodnot M, na kterΘ je definovßna jedna nebo vφce operacφ, kterΘ jsou na tΘto mno₧inou uzav°enΘ (tj. pokud vstupnφ hodnoty p°φsluÜnΘ operace pat°φ do M, potom je i v²sledek tΘto operace prvkem mno₧iny M).
KonkrΘtn∞ se zatφm omezφme na binßrnφ operace, co₧ jsou zobrazenφ f: MxM ( M. Snadno urΦφme, ₧e vÜech takov²ch zobrazenφ (tj. binßrnφch operacφ na M) je |M||M|^2. V∞tÜina z nich vÜak nenφ pro dalÜφ teoretickΘ studium p°φliÜ p°φnosnß, tak₧e p°i zavßd∞nφ nov²ch operacφ se v∞tÜinou vychßzφ z jemn²ch modifikacφ znßm²ch operacφ "+" a "*". Obvykle jim ponechßvßme i jejich p∙vodnφ nßzev, tj. operace sΦφtßnφ a nßsobenφ.
Je vÜak t°eba mφt na z°eteli, ₧e konkrΘtnφ v²poΦet uveden²ch operacφ m∙₧e siln∞ zßviset na konkrΘtnφ mno₧in∞ M, na kterΘ jsou definovßny. Celkem snadno se m∙₧eme v teorii setkat s operacφ, kterΘ se sice °φkß nßsobenφ, ale kterß mß ke znßmΘmu nßsobenφ na t∞lese reßln²ch Φφsel velmi daleko. Co se naopak u t∞chto operacφ nem∞nφ, jsou jejich vlastnosti, podle kter²ch je mo₧nΘ provßd∞t klasifikaci.
Na obrßzku 1 je uvedena tabulka algebraick²ch struktur, se kter²mi se budeme v teorii ECC setkßvat nejΦast∞ji. Zde uvedenΘ rozd∞lenφ p°edpoklßdß, ₧e mßme mno₧inu M, na kterΘ jsme definovali jednu nebo dv∞ binßrnφ operace, kterΘ znaΦφme symboly "+" a "*". Pokud tyto operace spl≥ujφ podmφnky uvedenΘ v levΘm sloupci tabulky, potom p°φsluÜnou dvojici (M, op1) nebo trojici (M, op1, op2) oznaΦujeme nßzvem, kter² je uveden v pravΘm sloupci tabulky.
Z obrßzku nap°φklad vidφme, ₧e mno₧inu, na kterΘ je definovßna operace sΦφtßnφ s p°φsluÜn²mi vlastnostmi, oznaΦujeme jako aditivnφ grupu, analogicky mno₧inu s definovanou operacφ nßsobenφ jako grupu komutativnφ. Grupy pro nßs budou p°edstavovat zßkladnφ stavebnφ prvek slo₧it∞jÜφch struktur, jako jsou okruhy a t∞lesa. Vzhledem k nßzv∙m uveden²m na obrßzku 1 poznamenejme, ₧e oznaΦenφ "komutativnφ okruh se jednotkov²m prvkem" budeme zkracovat na termφn "okruh". To m∙₧eme ud∞lat, proto₧e s jin²m typem okruh∙ zde prozatφm nebudeme pracovat.
Ob∞ struktury û t∞leso i okruh û se vyznaΦujφ tφm, ₧e majφ definovßnu jak operaci sΦφtßnφ, tak nßsobenφ. Rozdφl mezi t∞lesem a okruhem je v tom, ₧e v okruhu na rozdφl od t∞lesa existujφ prvky, kterΘ vzhledem k operaci nßsobenφ nemajφ v M inverznφ prvek. Zatφmco tedy t∞leso m∙₧eme pova₧ovat zßrove≥ za aditivnφ a multiplikativnφ grupu, okruh je pouze grupou aditivnφ. Operace nßsobenφ zde sice existuje takΘ, avÜak netvo°φ grupu.
P°φkladem struktury, kterß je pouze okruhem, m∙₧e b²t nap°φklad okruh cel²ch Φφsel (Z). Tato struktura je sice aditivnφ grupou (ke ka₧dΘmu Φφslu x existuje jeho aditivnφ inverze -x), ale nenφ grupou multiplikativnφ (s v²jimkou prvku 1 neobsahuje Z pro ₧ßdn² prvek x takΘ prvek 1/x). T∞lesem je teprve mno₧ina racionßlnφch Φφsel, kterß na rozdφl od Z obsahuje ony "chyb∞jφcφ" zlomky. Poznamenejme, ₧e t∞lesem je takΘ mno₧ina reßln²ch Φφsel, avÜak zde se jednß o zcela odliÜn² druh struktury, ne₧ s jakou se budeme setkßvat. T∞leso reßln²ch Φφsel je toti₧ spojitΘ a nekoneΦnΘ, zatφmco nßmi studovanΘ struktury budou diskrΘtnφ a koneΦnΘ.
V∞nujme se v krßtkosti pojmu koneΦnΘ t∞leso. S p°φvlastkem "koneΦn²" se budeme v teorii ECC setkßvat velmi Φasto a m∙₧eme jej pou₧φt pro ka₧dou v²Üe uvedenou algebraickou strukturu. V²znam tohoto p°φvlastku snad ani nemß cenu n∞jak formalizovat, nebo¥ pln∞ odpovφdß jeho intuitivnφmu chßpßnφ û danß struktura (mno₧ina M) mß koneΦn∞ mnoho prvk∙. KoneΦnß t∞lesa se v∞tÜinou oznaΦujφ jako Galoisova t∞lesa a znaΦφ se GF(q), kde q udßvß poΦet prvk∙ v tomto t∞lese.
P°i studiu literatury se m∙₧ete setkat s nejr∙zn∞jÜφmi definicemi t∞lesa GF(q) (nejΦast∞ji jako rozÜφ°enφ n∞jakΘho koneΦnΘho t∞lesa F s charakteristikou p û viz [ADAM89]), avÜak nßmi zavedenß definice je pro nßs zatφm nejen postaΦujφcφ, ale dφky tomu, ₧e ka₧dΘ koneΦnΘ t∞leso je izomorfnφ s n∞jak²m Galoisov²m t∞lesem (d∙kaz viz [ADAM89]), i korektnφ.
V souvislosti s koneΦn²mi t∞lesy byla dokßzßna nßsledujφcφ v∞ta: Pro ka₧dΘ koneΦnΘ t∞leso GF(q) platφ, ₧e q = pn, kde p je prvoΦφslo a n ( N\{0} û tvrzenφ T8.1. D∙sledkem tohoto tvrzenφ je, ₧e existujφ pouze takovß koneΦnß t∞lesa, kterß majφ poΦet prvk∙ rovn² mocnin∞ n∞jakΘho prvoΦφsla. Odtud nap°φklad plyne, ₧e nem∙₧e existovat t∞leso GF(6) (t∞lesa GF(4) a GF(16) naproti tomu existujφ).
Jist∞ je nynφ zajφmavΘ se ptßt, jestli je mo₧nΘ implikaci v tvrzenφ T8.1 obrßtit, nebo jestli naopak existujφ i takovΘ mocniny prvoΦφsel, pro kterΘ GF(q) t∞lesem nenφ. Ukazuje se, ₧e T8.1 obrßtit lze, dφky Φemu₧ dostßvßme nßsledujφcφ tvrzenφ: Pro ka₧dΘ prvoΦφslo p a ka₧dΘ celΘ kladnΘ Φφslo n existuje koneΦnΘ t∞leso GF(q), q = pn û tvrzenφ T8.2. D∙kaz uvßdφ nap°φklad [VAOO89] a [ADAM89].
Na zßv∞r tΘto Φßsti poznamenejme, ₧e aΦkoliv jsme se zde v∞novali nejvφce problematice koneΦn²ch t∞les, v teorii ECC si velmi Φasto vystaΦφme i se strukturou, kterou jsme zde nazvali okruh. Jak u₧ vφme, mß okruh oproti t∞lesu jedinou nev²hodu, ₧e nenφ zaruΦena existence inverznφho prvku pro operaci nßsobenφ. Pokud ovÜem tuto vlastnost nepo₧adujeme, m∙₧e b²t u₧itφ okruhu naopak v²hodn∞jÜφ, nebo¥ (jak uvidφme pozd∞ji) nejsme nap°φklad p°i konstrukci rozÜφ°enφ n∞jakΘho t∞lesa F pomocφ zbytkov²ch t°φd polynomu f(x) nuceni volit pouze ta f(x), kterß jsou nad F ireducibilnφ.
Polynomy nad t∞lesem F
Pro dalÜφ v²klad budeme p°edpoklßdat, ₧e mßme dßno n∞jakΘ koneΦnΘ t∞leso F. NaÜφm cφlem bude nad tφmto t∞lesem vybudovat n∞jakou dalÜφ algebraickou strukturu, kterß bude mφt rovn∞₧ vlastnosti t∞lesa Φi okruhu. Tomuto postupu se obecn∞ °φkß rozÜφ°enφ t∞lesa F a pro prvnφ p°iblφ₧enφ si m∙₧eme uvΘst analogii s vektorov²m prostorem, kter² je v podstat∞ takΘ rozÜφ°enφm n∞jakΘho t∞lesa (v naÜem p°φpad∞ op∞t koneΦnΘho).
ZaΦneme op∞t p°φznaΦn∞, a to definicφ pojmu polynom: Polynomem nad t∞lesem F rozumφme v²raz a(x) = a0 + a1x +...+ anxn, kde ai ( F, 0 ( i ( n a koeficient a0 oznaΦujeme jako konstantnφ Φlen û definice D8.1. Poznamenejme, ₧e v teorii ECC se polynomy obvykle zapisujφ od nejni₧Üφ mocniny po nejvyÜÜφ, co₧ je dßno snahou o p°izp∙sobenφ se systΘmu Φφslovßnφ sou°adnic v aritmetick²ch vektorech, co₧ nßsledn∞ umo₧≥uje snadnΘ mapovßnφ vektor∙ na koeficienty polynom∙ a naopak.
D∙le₧it²m parametrem polynomu a(x) je jeho stupe≥, kter² znaΦφme deg(a(x)) a definujeme jako nejvyÜÜφ Φφslo k, pro kterΘ platφ ak ( 0, stupe≥ nulovΘho polynomu p°itom definujeme deg(a(x)) = -1. Polynom a(x), pro kter² platφ deg(a(x)) = 0, naz²vßme konstantnφ polynom û definice D8.2. Polynom a(x), pro kter² platφ adeg(a(x)) = 1, naz²vßme normovan² û definice D8.3.
Vezm∞me si nynφ mno₧inu vÜech polynom∙ nad t∞lesem F a oznaΦme ji jako F[x]. NaÜφm cφlem bude nynφ ukßzat, ₧e tato mno₧ina spolu s operacemi sΦφtßnφ a nßsobenφ polynom∙ tvo°φ okruh. ZaΦneme definicφ operace sΦφtßnφ: M∞jme polynomy a(x), b(x) ( F[x]. Pro polynom c(x) = a(x) + b(x) = c0 + c1x +...+ cnxn potom platφ: ci = ai + bi û definice D8.3. P°ipome≥me, ₧e pro ·Φely sΦφtßnφ koeficient∙ zde pou₧φvßme operaci sΦφtßnφ tak, jak je definovßna na p°φsluÜnΘm t∞lese F (tj. m∙₧e to b²t nap°φklad souΦet cel²ch Φφsel modulo p û pokud F = Zp, atd.).
Vidφme, ₧e definice sΦφtßnφ na F[x] je v podstat∞ velmi intuitivnφ zßle₧itostφ. Obdobn∞ je tomu i v p°φpad∞ nßsobenφ polynom∙ a(x), b(x) ( F[x], kde pro koeficienty polynomu c(x) = a(x)*b(x) platφ: ci = a0bi + a1bi-1 + ...+ aib0 û definice D8.4. SΦφtßnφ a nßsobenφ koeficient∙ se zde op∞t provßdφ podle pravidel definovan²ch pro p°φsluÜnΘ t∞leso F.
P°i definici operacφ sΦφtßnφ a nßsobenφ na F[x] jsme zßrove≥ ukßzali i jejich uzav°enost (souΦet i souΦin dvou polynom∙ z F[x] je op∞t polynomem z F[x]). Ov∞°it zb²vajφcφ podmφnky a p°esv∞dΦit se tak, ₧e F[x] je opravdu okruh, je ji₧ vφcemΘn∞ jen rutinnφ zßle₧itostφ.
V p°φpad∞ operace souΦinu dvou polynom∙ na F[x] m∙₧eme dokßzat nßsledujφcφ pomocnß tvrzenφ: Pro dva nenulovΘ polynomy a(x), b(x) platφ, ₧e deg(c(x)=a(x)*b(x)) = deg(a(x)) + deg(b(x)) û tvrzenφ T8.3. D∙sledkem tohoto tvrzenφ je, ₧e pokud platφ a(x)*b(x) = 0, potom je alespo≥ jeden z polynom∙ a(x), b(x) nulov² û tvrzenφ T8.4. D∙kaz je snadn², nebo¥ pokud by platilo a(x)*b(x) = 0 pro n∞jakΘ nenulovΘ polynomy a(x) a b(x), potom by platilo, ₧e deg(a(x)*b(x)) = -1, co₧ je spor s T8.3.
DalÜφm d∙sledkem tvrzenφ T8.3 takΘ je, ₧e F[x] nenφ t∞leso û tvrzenφ T8.5. P°edpoklßdejme n∞jak² polynom a(x) ( F[x], kde deg(a(x)) ( 0. Pokud by k tomuto polynomu existovala multiplikativnφ inverze, tj. n∞jakΘ nenulovΘ a(x)-1 takovΘ, ₧e a(x)* a(x)-1 = 1, potom by platilo, ₧e deg(a(x)* a(x)-1) = deg(1) = 0, a to je op∞t spor s T8.3.
D∞lenφ polynom∙
Okruh F[x], kter² jsme si prßv∞ zavedli, mß vzhledem k naÜemu zßm∞ru studovat teorii ECC podstatnou nev²hodu: nenφ koneΦn². NaÜe dalÜφ sna₧enφ proto bude sm∞°ovat k vytvo°enφ "obdobnΘ" struktury, kterß vÜak ji₧ bude koneΦnß.
Abychom mohli zam²Ülenou ·pravu provΘst, musφme si nejprve definovat operaci d∞lenφ polynom∙. Uve∩me si nejprve u₧iteΦnΘ tvrzenφ: Pro libovolnΘ polynomy a(x), b(x) ( F[x], b(x) ( 0, existuje prßv∞ jedna dvojice polynom∙ q(x), r(x) ( F[x], takovß, ₧e a(x) = q(x)*b(x) + r(x), kde deg(r(x)) ( deg(b(x)) û tvrzenφ T8.6. Obdobn∞ jako v p°φpad∞ cel²ch Φφsel naz²vßme polynom q(x) podφlem a polynom r(x) zbytkem po d∞lenφ.
Zßkladnφ algoritmus pro d∞lenφ polynom∙ na F[x] siln∞ p°ipomφnß b∞₧n² postup d∞lenφ cel²ch Φφsel. Pro lepÜφ ilustrativnost si jej uvedeme jako p°φklad na obrßzku 2. Zde je vyobrazen zp∙sob d∞lenφ dvou polynom∙ a(x), b(x), poka₧dΘ nad t°emi r∙zn²mi t∞lesy. Vidφme, ₧e vlastnφ postup je jednoduch² a spoΦφvß v urΦovßnφ koeficient∙ podφlu na zßklad∞ podφlu koeficient∙ u nejvyÜÜφch mocnin polynom∙ a(x) a b(x). PotΘ provedeme odeΦtenφ odpovφdajφcφho nßsobku polynomu b(x) od a(x) a se zφskan²m v²sledkem a(x)' pokraΦujeme rekurzivn∞ v urΦovßnφ zb²vajφcφch koeficient∙ polynomu q(x). Jakmile v pr∙b∞hu d∞lenφ obdr₧φme polynom a(x)', deg(a(x)') ( b(x), polo₧φme r(x) = a(x)' a proces d∞lenφ ukonΦφme.
Zßm∞rn∞ jsme si uvedli v²sledky d∞lenφ syntakticky stejn²ch polynom∙ nad t°emi r∙zn²mi t∞lesy, abychom si ilustrovali, jak zßkladnφ operace na F ovliv≥ujφ operace na F[x]. Zajφmav²m nßm∞tem pro zamyÜlenφ m∙₧e b²t fakt, ₧e koeficienty obdr₧en²ch polynom∙ jsou sice v t∞lese Z r∙znΘ, avÜak v p°φsluÜn²ch Zp nßle₧φ v₧dy ke stejn²m t°φdßm ekvivalence, Φili jsou spolu kongruentnφ. Poznamenejme takΘ, ₧e zatφmco nad Z3 je polynom a(x) d∞liteln² polynomem b(x), nad t∞lesy Z a Z2 tomu tak nenφ.
Ji₧ jsme se zmφnili o pojmu ireducibilnφ polynom, tak₧e nynφ si uvedeme jeho definici: Polynom f(x) je ireducibilnφ nad t∞lesem F, pokud jej nenφ mo₧nΘ vyjßd°it souΦinem f(x) = a(x)*b(x), kde a(x), b(x) jsou polynomy okruhu F[x] ni₧Üφho stupn∞, ne₧ je deg(f(x)) û definice D8.5.
T°φdy modulo f(x)
S pomocφ operace d∞lenφ polynom∙ budeme nynφ definovat kongruenci dvou polynom∙ z mno₧iny F[x]: M∞jme dßn n∞jak² f(x) ( F[x]. O polynomech a(x), b(x) ( F[x] °φkßme, ₧e jsou kongruentnφ modulo f(x) prßv∞ tehdy, kdy₧ existuje q(x) ( F[x] tak, ₧e a(x)-b(x) = q(x)*f(x). Tento vztah zapisujeme jako a(x) ( b(x) (mod f(x)) û definice D8.6.
Kongruence polynom∙ se tak definuje obdobn²m zp∙sobem jako v p°φpad∞ cel²ch Φφsel modulo n. Nenφ slo₧itΘ ukßzat, ₧e kongruence dle D8.6 definuje na F[x] relaci ekvivalence. Voln∞ °eΦeno ji tedy m∙₧eme chßpat jako "b∞₧nou" relaci "rovnß se". P°esn∞jÜφ vÜak budeme, pokud si zavedeme pojem t°φda ekvivalence: M∞jme dßn polynom f(x) ( F[x]. T°φda ekvivalence obsahujφcφ g(x) ( F[x] je definovßna jako mno₧ina [g(x)] = { h(x): h(x) ( g(x) (mod f(x)), h(x) ( F[x] } û definice D8.7.
Smysl zavedenφ t°φd ekvivalence je pro nßs v tom, ₧e aΦkoliv tyto mno₧iny samy o sob∞ nejsou koneΦnΘ, mno₧ina vÜech t°φd ekvivalence pro dan² polynom f(x) ( F[x] koneΦnß je. Mno₧inu vÜech t°φd ekvivalence pro vybran² polynom f(x) ( F[x] znaΦφme F[x]/f(x) û definice D8.8.
Nenφ dßle t∞₧kΘ ukßzat, ₧e ka₧dß t°φda ekvivalence obsahuje prßv∞ jeden polynom g(x) ( F[x], pro kter² platφ deg(g(x)) ( deg(f(x)). Mßme-li takov² polynom, potom m∙₧eme p°φsluÜnou t°φdu definovat jako [g(x)] = { h(x) = g(x) + q(x)f(x): q(x) ( F[x] }. Tuto vlastnost je vhodnΘ zd∙raznit proto, ₧e celou strukturu F[x]/f(x) m∙₧eme popsat pomocφ vÜech polynom∙ stupn∞ menÜφho ne₧ deg(f(x)), Φeho₧ se s v²hodou u₧φvß p°i implementaci tΘto struktury v HW a SW prost°edcφch. (Je to stejnΘ jako v Zp, ve kterΘm se zajφmßme takΘ pouze o Φφsla menÜφ ne₧ p, aΦkoliv bychom mφsto ka₧dΘho z nich mohli pou₧φvat jak²koliv jin² prvek z tΘ₧e t°φdy.)
V∞nujme se nynφ zavedenφ operacφ sΦφtßnφ a nßsobenφ na F[x]/f(x). Tyto operace jsou zde definovßny nßsledujφcφm zp∙sobem: [a(x)] + [b(x)] = [a(x) + b(x)], [a(x)] * [b(x)] = [a(x) * b(x)] - definice D8.9. Poznamenejme, ₧e zatφm se zde p°φsn∞ dr₧φme formßlnφ definice F[x]/f(x), a proto zachßzφme s jejφmi prvky jako se t°φdami. V b∞₧nΘ teorii se vÜak mlΦky toleruje zßpis g(x) ( F[x]/f(x), kter² chßpeme ovÜem jako [g(x)] ( F[x]/f(x). (Viz ostatn∞ op∞t zachßzenφ se Zp, kde se nad tφm ani nepozastavujeme.)
Op∞t je snadnΘ dokßzat, ₧e mno₧ina F[x]/f(x) spolu s operacemi dle D8.9 tvo°φ okruh û tvrzenφ T8.7. Dßle platφ, ₧e F[x]/f(x) spolu s operacemi dle D8.9 je t∞leso prßv∞ tehdy, kdy₧ je polynom f(x) ireducibilnφ nad F û tvrzenφ T8.9. Zde m∙₧eme spat°it jistou analogii mezi vlastnostmi u₧itφ ireducibilnφch polynom∙ a prvoΦφsel.
Zßv∞r
V tomto p°evß₧n∞ algebraickΘm dφlu jsme si ukßzali zßkladnφ struktury, kterΘ se v teorii ECC pou₧φvajφ nejΦast∞ji. Zobecnili jsme si p°itom b∞₧n∞ znßmΘ pojmy, jako je operace sΦφtßnφ a nßsobenφ, a ukßzali jsme si zp∙sobe konstrukce koneΦnΘho okruhu/t∞lesa F[x]/f(x). P°φÜt∞ se budeme v∞novat zp∙sobu vyu₧itφ tΘto struktury pro konstrukci cyklick²ch k≤d∙.
