V tomto pokraΦovßnφ naÜeho serißlu o bezpeΦnostnφch k≤dech navß₧eme na p°edchozφ dφl v²kladem korespondence mezi cyklick²mi podprostory a ideßly okruhu. Ukß₧eme si dßle vyu₧itφ t∞chto poznatk∙ pro konstrukci cyklick²ch k≤d∙.
Pojem cyklick² k≤d jsme si zavedli ji₧ v druhΘm dφlu tohoto serißlu pomocφ D2.3. Pro lepÜφ pochopenφ nßvaznosti na ideßly okruhu (kterΘ si definujeme za okam₧ik) si zde tuto definici jeÜt∞ up°esnφme. P°edtφm si vÜak jeÜt∞ zavedeme pojem cyklickΘho podprostoru: Pod pojmem cyklick² podprostor L prostoru Vn(F) rozumφme ka₧d² jeho podprostor L takov², ₧e z platnosti (a0, a1, a2, ..., an-1) ( L plyne, ₧e (an-1, a0, a1, a2, ..., an-2) ( L û definice D9.1.
S vyu₧itφm D9.1 si nynφ zavedeme pojem cyklickΘho k≤du takto: Lineßrnφ k≤d s mno₧inou k≤dov²ch slov Ck, kterß je reprezentovßna cyklick²m podprostorem L, naz²vßme cyklick² k≤d û definice D9.2.
UvedenΘ definice si zaslou₧φ n∞kolik poznßmek. Prvnφ se t²kß oznaΦenφ Vn(F), kterΘ jsme pou₧ili v D9.1. Tφmto zp∙sobem budeme znaΦit vektorov² prostor aritmetick²ch vektor∙ dΘlky n, jejich₧ sou°adnice jsou z t∞lesa F. D°φve jsme pro tento ·Φel pou₧φvali jednoduÜÜφ a obecn∞jÜφ zßpis V(n,q), pro kter² zde budeme p°edpoklßdat, ₧e platφ V(n,q) = Vn(F), kde F = GF(q).
Poznamenejme dßle, ₧e jsme zßm∞rn∞ definovali pouze pojem cyklick² podprostor. Prostor Vn(F) toti₧ podmφnku cykliΦnosti trivißln∞ spl≥uje v₧dy, nebo¥ obsahuje vÜechny aritmetickΘ vektory dΘlky n.
Souvislost s okruhy
Z p°edchozφch v²klad∙ vφme, ₧e na lineßrnφm prostoru je definovßna operace sΦφtßnφ a ₧e ka₧d² lineßrnφ prostor m∙₧eme pova₧ovat za aditivnφ abelovskou grupu. Se sΦφtßnφm vektor∙ proto nenφ ₧ßdn² problΘm. HorÜφ je to vÜak s operacφ nßsobenφ û zde jsme limitovßni pouze na nßsobenφ vektoru skalßrem. Pro teorii cyklick²ch k≤d∙ je vÜak z mnoha d∙vod∙ nutnΘ rozÜφ°it operace v prostoru k≤dov²ch slov i o operaci nßsobenφ vektoru vektorem, jejφm₧ v²sledkem bude op∞t vektor (tj. nejde nßm zde o skalßrnφ souΦin). Jako nej·Φeln∞jÜφ cesta k definici po₧adovanΘ operace se zde jevφ zavedenφ korespondence mezi vektorov²m prostorem a okruhem zbytkov²ch t°φd modulo f(x).
P°edpoklßdejme, ₧e mßme vektorov² prostor Vn(F), kter² chceme rozÜφ°it o operaci nßsobenφ. Nejprve definujeme zp∙sob p°evodu prvk∙ Vn(F) na jim odpovφdajφcφ polynomy stupn∞ nejv²Üe n-1: aritmetick² vektor v = (a0, a1, a2, ..., an-1) pova₧ujeme za polynom v(x) ( F[x], v(x) = a0 + a1*x + a2*x2 +, ..., an-1*xn-1. Nynφ si zvolφme polynom f(x) = xn-1, jeho₧ pomocφ vytvo°φme okruh F[x]/f(x). Poznamenejme zde, ₧e bychom sice mohli vybrat libovoln² f(x) ( F[x], deg(f(x)) = n (odpovφdß dimenzi prostoru), avÜak vybran² polynom f(x) = xn-1 nßm krom∞ definice operace nßsobenφ umo₧≥uje jeÜt∞ snadn² popis operace cyklickΘho posuvu vpravo (viz dßle).
Vlastnφ definice nßsobenφ je ji₧ velmi jednoduchß a intuitivnφ. Pro libovolnΘ vektory v1, v2 ( Vn(F) definujeme v²sledek operace v = v1 * v2, v ( Vn(F) takto: nech¥ v1(x) a v2(x) jsou polynomy odpovφdajφcφ vektor∙m v1 a v2 (viz v²Üe). Potom vektor v odpovφdß polynomu v(x), kter² p°edstavuje reprezentanta t°φdy [v1(x)*v2(x)] ( F[x]/f(x) s nejni₧Üφm stupn∞m. Voln∞ °eΦeno, polynom v(x) p°edstavuje zbytek po d∞lenφ souΦinu v1(x)*v2(x) polynomem f(x) û definice D9.3.
Vidφme, ₧e nßsobenφ sice u₧ vyu₧φvß pom∞rn∞ sofistikovanΘ algebraickΘ struktury, avÜak pochopenφ jeho technickΘ realizace je jist∞ snadnΘ. Vφce o tΘto problematice budeme hovo°it p°i studiu logick²ch obvod∙ vyu₧φvan²ch k hardwarovΘ realizaci operacφ pro cyklickΘ k≤dy.
Vra¥me se nynφ k volb∞ f(x) = xn-1. JeÜt∞ p°edtφm uΦinφme poznßmku o zp∙sobu zßpisu polynom∙ û pokud bude zßpis vyjad°ovat polynom, kter² koresponduje s n∞jak²m aritmetick²m vektorem, budeme pou₧φvat zaveden² zßpis od nejni₧Üφ mocniny prom∞nnΘ x k nejvyÜÜφ. Pokud se vÜak bude jednat o zcela obecn² p°φpad polynomu, u kterΘho nep°edpoklßdßme souvislost s n∞jak²m aritmetick²m vektorem, budeme pou₧φvat obvyklejÜφ zßpis od nejvyÜÜφ mocniny k nejni₧Üφ. Rozhodnutφ o tom, zda dan² polynom souvisφ s n∞jak²m vektorem, Φi nikoliv, je vÜak n∞kdy znaΦn∞ intuitivnφ zßle₧itost. Proto berte tuto poznßmku jako upozorn∞nφ, ₧e se nejednß o p°eklepy Φi ned∙slednost, n²br₧ spφÜe o snahu dodr₧et obvyklou notaci u₧φvanou v dostupnΘ literatu°e.
Nynφ se vra¥me k otßzce v²b∞ru f(x). Vzhledem k volb∞ f(x) = xn-1 platφ na F[x]/f(x) nßsledujφcφ kongruence xn ( 1 (mod f(x)). Sledujme nynφ, jak² mß tato skuteΦnost vliv na nßsobenφ libovolnΘho polynomu v(x) = a0 + a1*x + a2*x2 +, ..., an-1*xn-1 polynomem g(x) = x. Pro souΦin t∞chto polynom∙ platφ: v(x)*g(x) = a0x + a1*x2 + a2*x3 +, ..., an-1*xn. Takto zapsan² polynom vÜak z°ejm∞ nenφ reprezentantem svΘ t°φdy ekvivalence s nejni₧Üφm stupn∞m. V obecnΘm p°φpad∞ bychom nynφ museli provΘst operaci d∞lenφ polynomem f(x), abychom takovΘho reprezentanta naÜli jako zbytek po tΘto operaci. Vzhledem k volb∞ f(x) vÜak postaΦuje nahradit ka₧dou mocninu xn jedniΦkou. Provedeme-li tuto ·pravu, dostaneme, ₧e v(x)*g(x) ( an-1 + a0x + a1*x2 + a2*x3 +, ..., an-2*xn-1 (mod f(x)). V²sledek tak odpovφdß vektoru (an-1, a0, a1, a2, ..., an-2), co₧ je cyklick² posuv vektoru v o jednu pozici vpravo.
Z p°edchozφho p°φkladu plynou dv∞ v²hody, kterΘ nßm volba f(x) = xn-1 nabφzφ: tou prvnφ je mo₧nost snadnΘho urΦenφ zbytku po d∞lenφ tφmto polynomem (postup vychßzφ z nßhrady vÜech symbol∙ xn jedniΦkou). Za druhΘ mßme mo₧nost snadno popsat operaci cyklickΘho posuvu vpravo jako nßsobenφ polynomem g(x) = x. Jak uvidφme pozd∞ji, umo₧≥uje nßm tento fakt realizovat operaci nßsobenφ vektor∙ pomocφ operace sΦφtßnφ a cyklickΘho posuvu vpravo.
Ideßl okruhu
VÜe, co jsme si doposud °ekli, nßm umo₧≥uje podle pot°eby zachßzet s vektory prostoru Vn(F) jako s polynomy okruhu F[x]/f(x), deg(f(x)) = n a obrßcen∞. To je jist∞ u₧iteΦn² v²sledek, avÜak pro naÜe ·Φely to nestaΦφ. NaÜφm hlavnφm cφlem je toti₧ v prostoru Vn(F) najφt jeho cyklickΘ podprostory a ty n∞jak "rozumn∞" popsat. Patrn∞ p°itom budeme chtφt takΘ n∞jak²m zp∙sobem vyu₧φt zavedenou korespondenci mezi vektory a polynomy. Pokud se nad tφm zamyslφme, zjistφme, ₧e nßm zde patrn∞ chybφ jeÜt∞ n∞jakß algebraickß struktura: pokud toti₧ vektorov² prostor odpovφdß okruhu, potom nutn∞ jeho podprostor musφ odpovφdat obdobn∞ pojatΘ struktu°e uvnit° tohoto okruhu. Touto strukturou bude takzvan² ideßl okruhu, kter² si nynφ definujeme.
M∞jme okruh (R, +, *). Jeho neprßzdnou podmno₧inu I nazveme ideßlem okruhu R, prßv∞ kdy₧ platφ (definice D9.4):
(I, +) je aditivnφ abelovskß grupa.
i*r ( I pro vÜechna i ( I a r ( R.
Elegantnφ zp∙sob, jak vygenerovat ideßl p°φsluÜnΘho okruhu, spoΦφvß v nßsledujφcφ konstrukci: vezm∞me libovoln² nenulov² prvek g ( R a vytvo°me mno₧inu I = { g*r: r ( R }. Snadno ov∞°φme, ₧e I je opravdu ideßlem okruhu R. Takov²m ideßl∙m °φkßme ideßly generovanΘ prvkem g û definice D9.5. ProblΘm tohoto zp∙sobu je v tom, ₧e jej nenφ mo₧nΘ pou₧φt pro vÜechny druhy okruh∙. Okruhy, jejich₧ ideßly je mo₧nΘ tφmto zp∙sobem konstruovat, naz²vßme zßkladnφ ideßlovΘ okruhy û definice D9.6.
Pro nßs je d∙le₧itΘ, ₧e jak okruh F[x], tak i F[x]/f(x) jsou zßkladnφmi ideßlov²mi okruhy û tvrzenφ T9.1. Ukß₧eme si zde d∙kaz tohoto tvrzenφ pro p°φpad okruhu F[x]/f(x), nebo¥ ten mß jistΘ hlubÜφ souvislosti s dalÜφm v²kladem. M∞jme ideßl I okruhu R. Pokud I = {0}, potom je I generovßn jednoduÜe polynomem g(x) = 0. V opaΦnΘm p°φpad∞ vezm∞me normovan² polynom g(x) nejni₧Üφho stupn∞ deg(g(x)), kter² reprezentuje n∞jakou t°φdu v I. Podle v²Üe zavedenΘ notace m∙₧eme psßt g(x) ( I (formßln∞ji [g(x)] ( I û od tohoto zßpisu vÜak postupn∞ upustφme). Nynφ budeme dokazovat, ₧e g(x) generuje ideßl I.
Pro tento ·Φel si vezmeme libovoln² h(x) ( I. Podle T8.6 platφ: h(x) = q(x)g(x) + r(x), kde deg(r(x)) < deg(g(x)). NaÜφm cφlem je dokßzat, ₧e r(x) = 0, a tudφ₧ ka₧d² prvek I lze vyjßd°it jako nßsobek g(x) (co₧ odpovφdß D9.5). Nejd°φve ukß₧eme, ₧e r(x) ( I. To plyne z rovnice [h(x)] = [q(x)*g(x) + r(x)] = [q(x)*r(x)] + [r(x)]. Proto₧e [h(x)] ( I a [q(x)*g(x)] ( I (viz definice ideßlu), platφ i [r(x)] ( I. Polynom g(x) mß ale ze vÜech polynom∙ nejni₧Üφ stupe≥, tak₧e podle T8.6 musφ platit r(x) = 0. Tφm jsme dokßzali, ₧e g(x) generuje ideßl I.
Souvislost s ideßly
V tΘto Φßsti dolo₧φme formßln∞ vztah mezi cyklick²mi podprostory a ideßly. ZaΦneme tvrzenφm, kterΘ nßm tuto souvislost ukazuje: Neprßzdnß mno₧ina vektor∙ L ( Vn(F) je cyklick² podprostor prßv∞ tehdy, kdy₧ mno₧ina polynom∙ I odpovφdajφcφch vektor∙m z L je ideßlem okruhu R, kter² odpovφdß prostoru Vn(F) û tvrzenφ T9.2. D∙kaz tohoto tvrzenφ je vφcemΘn∞ jen technickou zßle₧itostφ, kde se dovedn∞ vyu₧φvß zejmΘna vyjßd°enφ operace nßsobenφ pomocφ cyklick²ch posuv∙.
Tvrzenφ T9.2 nßm ukazuje, jak²m sm∞rem se mßme ubφrat p°i hledßnφ cyklick²ch k≤d∙. Mo₧nost, kterß se nßm zde nabφzφ, spoΦφvß v hledßnφ ideßl∙ p°φsluÜn²ch okruh∙, co₧ vzhledem k T9.1 znamenß soust°edit se na hledßnφ polynom∙, kterΘ je generujφ. K tomu vÜak pot°ebujeme vφce prostudovat jejich vlastnosti. O krok dßl na tΘto cest∞ nßs posunuje nßsledujφcφ tvrzenφ: Nech¥ I je nenulov² ideßl okruhu odpovφdajφcφho Vn(F) a nech¥ g(x) je normovan² polynom nejni₧Üφho stupn∞, kter² reprezentuje n∞jakou t°φdu v I. Potom g(x) generuje I a d∞lφ f(x) = xnû1 û tvrzenφ T9.3. Prvnφ Φßst tohoto tvrzenφ jsme ji₧ dokßzali pro T9.1. Zb²vß dokßzat, ₧e g(x) d∞lφ f(x). Podle T8.6 platφ: f(x) = h(x)*g(x) + r(x), kde deg(r(x)) < deg(g(x)). NaÜφm cφlem je ukßzat, ₧e r(x) = 0. K tomu vyu₧ijeme fakt, ₧e f(x) ( 0 (mod f(x)), Φili [f(x)] = [0]. Odtud pro rovnici [f(x)] = [h(x)*g(x) + r(x)] = [h(x)]*[g(x)] + [r(x)] dostaneme, ₧e [r(x)] = [-h(x)]*[g(x)] ( I. S ohledem na vlastnosti g(x) a omezenφ na stupe≥ r(x) musφ platit r(x) = 0, tak₧e g(x) d∞lφ f(x).
Dßle si uvedeme tvrzenφ, kterΘ ukazuje na jedineΦnost generujφcφch polynom∙ (viz definice dßle): Pro ka₧d² ideßl I okruhu R korespondujφcφho s Vn(F) existuje prßv∞ jeden normovan² polynom nejni₧Üφho stupn∞, kter² generuje I û tvrzenφ T9.4. Tomuto polynomu budeme °φkat generujφcφ polynom û definice D9.7.
Tvrzenφ T9.3 samo o sob∞ vybφzφ k zamyÜlenφ nad tφm, zda je mo₧nΘ vÜechny d∞litele modulovΘho polynomu f(x) pova₧ovat za generujφcφ polynomy n∞jakΘho ideßlu. Nßsledujφcφ st∞₧ejnφ tvrzenφ ukazuje, ₧e ano: Bu∩ h(x) je normovan² d∞litel polynomu f(x) = xn-1. Potom h(x) je generujcφ polynom ideßlu I = {a(x)*h(x): a(x) ( F[x]/f(x)} û tvrzenφ T9.5. Pro lepÜφ porozum∞nφ si op∞t ukß₧eme i d∙kaz. Nech¥ g(x) je generujφcφm polynomem ideßlu I. NaÜφm cφlem nynφ bude ukßzat, ₧e g(x) = h(x). Proto₧e g(x) ( I, musφ existovat polynom a(x) takov², ₧e [g(x)] = [a(x)*h(x)]. P°esuneme-li se do okruhu F[x], m∙₧eme tuto rovnici zapsat jako g(x) = a(x)*h(x) + b(x)*f(x), pro n∞jak² polynom b(x). Proto₧e h(x) d∞lφ f(x), d∞lφ zßrove≥ takΘ g(x). Podle T9.3 vÜak takΘ g(x) d∞lφ f(x), tak₧e odtud g(x) d∞lφ h(x). Oba polynomy h(x) a g(x) jsou p°itom normovanΘ. Odtud plyne h(x) = g(x).
Na zßklad∞ vÜech dosud prezentovan²ch tvrzenφ m∙₧eme vyslovit nßsledujφcφ teorΘm, kter² nßm umo₧≥uje urΦit poΦet cyklick²ch podprostor∙ danΘho prostoru: Existuje vzßjemn∞ jednoznaΦnΘ zobrazenφ mezi mno₧inou cyklick²ch podprostor∙ prostoru Vn(F) a mno₧inou normovan²ch polynom∙ g(x) ( F[x], kterΘ d∞lφ polynom f(x) = xn-1 û tvrzenφ T9.6.
Jako d∙sledek T9.6 m∙₧eme formulovat nßsledujφcφ: Nech¥ mß polynom f(x) = xn-1 faktorizaci f(x) = p1a1(x)*p2a2(x)*...*ptat(x), kde pi(x) jsou navzßjem r∙znΘ ireducibilnφ normovanΘ polynomy nad F a ai jsou celß kladnß Φφsla, pro 1 ( i ( t. Potom Vn(F) obsahuje celkem (a1+1)*(a2+1)*...*(at+1) cyklick²ch podprostor∙ û tvrzenφ T9.7.
Z prßv∞ vylo₧en²ch tvrzenφ vypl²vß d∙le₧itost um∞t faktorizovat polynom f(x) = xn-1 nad r∙zn²mi t∞lesy F. Nepochybn∞ proto se pom∞rn∞ velkß pozornost v teorii ECC v∞nuje prßv∞ metodßm rozkladu faktorizace tohoto polynomu. My se zde t∞mito metodami alespo≥ prozatφm zab²vat nebudeme. Mφsto nich budeme jako pomocn² nßstroj vyu₧φvat tabulku na obrßzku 1, kterß ukazuje rozklady xn-1 nad GF(2) pro 1 ( n ( 25.
Generujφcφ matice cyklickΘho k≤du
Prßv∞ jsme se seznßmili s tφm, jak generovat cyklickΘ podprostory pomocφ generujφcφch polynom∙ jim p°φsluÜejφcφch ideßl∙. Ukßzali jsme si takΘ, jak tyto polynomy hledat pomocφ faktorizace modulovΘho polynomu f(x). Tato dovednost sama o sob∞ je jist∞ velmi u₧iteΦnß. My vÜak p∙jdeme jeÜt∞ dßl a ukß₧eme si, jak²m zp∙sobem na zßklad∞ znalosti generujφcφho polynomu sestavφme generujφcφ matici pro p°φsluÜn² podprostor. Znalost matice je u₧iteΦnß zejmΘna v p°φpadech, kdy chceme pro k≤dovßnφ pou₧φt vektorov²ch operacφ namφsto v²poΦt∙ na ideßlu. Zde je vÜak t°eba p°edeslat, ₧e v d°φv∞jÜφch dobßch byly cyklickΘ k≤dy hojn∞ pou₧φvßny hlavn∞ proto, ₧e s ohledem na tehdejÜφ technologickΘ mo₧nosti bylo (z dneÜnφho pohledu mo₧nß paradoxn∞) jednoduÜÜφ hardwarov∞ realizovat operace na F[x]/f(x) ne₧li maticovΘ nßsobenφ. Dnes se zase s ohledem na jednoduÜÜφ matematickΘ vyjßd°enφ a existenci levn²ch jednoΦipov²ch mikropoΦφtaΦ∙ m∙₧e zdßt efektivn∞jÜφ pou₧φvat maticovou algebru. Vφce se t∞mito otßzkami budeme zab²vat v samostatnΘm dφlu tohoto serißlu.
Pro konstrukci generujφcφ matice platφ nßsledujφcφ tvrzenφ: Bu∩ g(x) je normovan² d∞litel polynomu f(x) = xn-1 nad t∞lesem F, stupn∞ deg(g(x)) = n-k. Potom je g(x) generujφcφm polynomem ideßlu I, kterΘmu odpovφdß cyklick² podprostor L dimenze dim(L) = k prostoru Vn(F). Bßzi podprostoru L tvo°φ mno₧ina vektor∙ B = {g(x), x*g(x), x2*g(x), ..., xk-1*g(x)} û tvrzenφ T9.8.
UvedenΘ tvrzenφ nßs krom∞ zp∙sobu konstrukce matice G (jejφ₧ °ßdky odpovφdajφ vektor∙m z mno₧iny B) informuje takΘ o dimenzi podprostoru odpovφdajφcφho p°φsluÜnΘmu ideßlu. Vzhledem k tomu, ₧e se jednß o pom∞rn∞ d∙le₧it² teorΘm, ukß₧eme si zde jeho d∙kaz. Nejd°φve dokß₧eme, ₧e vektory z B jsou lineßrn∞ nezßvislΘ. P°edpoklßdejme, ₧e by zßvislΘ byly. Potom by existovalo netrivißlnφ °eÜenφ rovnice (i=0k-1 (i*xi*g(x) = 0. Zam∞°me se nejprve na koeficient u mocniny xn-1. Ten zßvisφ pouze na hodnot∞ (k-1. Pro spln∞nφ uvedenΘ rovnice tedy musφ platit, ₧e (k-1 = 0. Nynφ se zam∞°me na xn-2. Jejφ koeficient je zßvisl² na hodnotßch (k-1 a (k-2. Proto₧e ale (k-1 = 0, musφ platit, ₧e (k-2 = 0. Tφmto postupem nakonec ukß₧eme, ₧e uvedenß rovnice mß pouze trivißlnφ °eÜenφ, tak₧e vektory z mno₧iny B jsou lineßrn∞ nezßvislΘ.
Prßv∞ jsme dokßzali, ₧e podprostor generovan² bßzφ B mß dimenzi k. Nynφ jeÜt∞ musφme ukßzat, ₧e tento podprostor pokr²vß cel² ideßl generovan² polynomem g(x), tak₧e je cyklick². Vezm∞me si libovoln² h(x) ( I. Proto₧e g(x) je generßtor I, platφ h(x) ( a(x)*g(x) (mod f(x)). Bez ·jmy na obecnosti budeme p°edpoklßdat, ₧e deg(a(x)) < k. Pokud toti₧ deg(a(x)) ( k, potom na F[x] platφ: a(x)*g(x) = q(x)*(xn-1) + r(x), kde deg(r(x)) ( n-1. Dßle platφ, ₧e r(x) ( h(x) (mod f(x)) a g(x) d∞lφ r(x). S ohledem na stupe≥ r(x) existuje a'(x), deg(a'(x)) ( k-1, pro kterΘ platφ h(x) ( a'(x)*g(x) (mod f(x)). M∙₧eme proto pou₧φt a'(x) namφsto a(x). Dodejme, ₧e toto pomocnΘ tvrzenφ je zajφmavΘ samo o sob∞.
Podle toho, co jsme prßv∞ dokßzali, m∙₧eme p°edpoklßdat, ₧e a(x) mß tvar a(x) = (i=0k-1 (i*xi. Odtud plyne, ₧e h(x) ( (i=0k-1 (i*xi*g(x) (mod f(x)). Uvedenß operace je zßrove≥ realizovatelnß pro libovoln² vektor a = ((0, (1, ..., (k-1) jako h = a*G, kde G je generujφcφ matice, jejφ₧ °ßdky p°edstavujφ vektory z bßze B. Tφm jsme dokßzali, ₧e podprostor L mß bßzi tvo°enou k lineßrn∞ nezßvisl²mi vektory a obsahuje ideßl I, tak₧e je cyklick² o dimenzi k.
KonkrΘtnφ p°φklad tvorby generujφcφ matice binßrnφho cyklickΘho k≤du typu (7,4) je na obrßzku 2. Vzhledem k tomu, ₧e se jednß o cyklick² podprostor dimenze 4 prostoru V7(F), F = GF(2), nalezli jsme jeho matici na zßklad∞ generujφcφho polynomu g(x), kter² je normovan², stupn∞ deg(g(x)) = 3 a d∞lφ f(x) = xn-1. Podle obrßzku 1 jsme nalezli rozklad f(x) nad GF(2) a jako g(x) jsme vybrali polynom g(x) = 1 + x + x3. Podle T9.8 jsme potom polo₧ili °ßdky matice G rovnΘ cyklick²m posuv∙m g(x). Tφm jsme obdr₧eli generujφcφ matici hledanΘho cyklickΘho k≤du.
Zßv∞r
Hlavnφ nßplnφ tohoto dφlu bylo ukßzat, jak²m zp∙sobem se konstruujφ cyklickΘ k≤dy typu (n,k) nad GF(q). Ukßzali jsme si, ₧e pro tento ·Φel pot°ebujeme znßt normovan² polynom g(x) stupn∞ n-k, kter² nad GF(q) d∞lφ xn-1. Generujφcφ matici hledanΘho k≤du potΘ vytvo°φme cyklick²mi posuvy g(x).
P°φÜt∞ se zam∞°φme na hledßnφ kontrolnφ matice cyklickΘho k≤du a na operace k≤dovßnφ a dek≤dovßnφ.
TomᚠRosa, tomas.rosa@decros.cz
Stupe≥ nFaktorizace xn-1 nad GF(2)11+x2(1+x)23(1+x)(1+x+x2)4(1+x)45(1+x)(1+x+x2+x3+x4)6(1+x)2(1+x+x2)27(1+x)(1+x+x3)(1+x2+x3)8(1+x)89(1+x)(1+x+x2)(1+x3+x6)10(1+x)2(1+x+x2+x3+x4)211(1+x)(1+x+...+x10)12(1+x)4(1+x+x2)413(1+x)(1+x+...+x12)14(1+x)2(1+x+x3)2(1+x2+x3)215(1+x)(1+x+x2)(1+x+x2+x3+x4)(1+x+x4)(1+x3+x4)16(1+x)1617(1+x)(1+x+x2+x4+x6+x7+x8)(1+x3+x4+x5+x8)18(1+x2)(1+x+x2)2(1+x3+x6)219(1+x)(1+x+x2+...+x18)20(1+x)4(1+x+x2+x3+x4)421(1+x)(1+x+x2)(1+x2+x3)(1+x+x3)(1+x2+x4+x5+x6)(1+x+x2+x4+x6)22(1+x)2(1+x+x2+...+x10)223(1+x)(1+x+x5+x6+x7+x9+x11)(1+x2+x4+x5+x6+x10+x11)24(1+x)8(1+x+x2)825(1+x)(1+x+x2+x3+x4)(1+x5+x10+x15+x20)
