i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 157 — #1
i
i
i
i
i
i
ARITMETIKADVOJI
ˇ
SKIHKON
ˇ
CNIHOBSEGOV
JERNEJ TONEJC
Fakulteta za matematiko in fiziko
Univerza v Ljubljani
Math. Subj. Class. (2010): 11T{06,22,55,71}, 12E{05,20,30}, 68R05
Vˇ clankupredstavimokonˇ cneobsegeinaritmetikovkonˇ cnihobsegihkarakteristike2.
Tiimajopomembnovlogovimplementacijiˇ stevilnihkriptosistemovinkodzaodpravljanje
napak. Opiˇ semo uˇ cinkovite algoritme za raˇ cunanje v polinomskih bazah konˇ cnih obsegov,
ki se pogosto uporabljajo v kriptografskih aplikacijah.
ARITHMETIC OF BINARY FINITE FIELDS
We introduce finite fields and arithmetic in finite fields of characteristic 2 which play
an important role in implementation of many cryptosystems and error-correcting codes.
We describe efficient arithmetic algorithms in polynomial bases for finite fields which are
often used in cryptographic applications.
Uvod
S konˇ cnimi obsegi so se ukvarjali ugledni matematiki, kot so Fermat,
Euler, Lagrange in Legendre, ki so prispevali k razvoju teorije praˇ stevil-
skih obsegov Z
p
. Sploˇ sno teorijo konˇ cnih obsegov sta zaˇ cela graditi Gauss
in Galois. Vendar pa se je le-ta uveljavila v uporabni matematiki ˇ sele s
prihodom raˇ cunalnikov, kjer ne gre brez diskretnih matematiˇ cnih struktur.
Spomnimo se, da je obseg najpreprostejˇ sa algebraiˇ cna struktura, v kateri
lahko izvajamo vse elementarne aritmetiˇ cne operacije, tj. seˇ stevamo, odˇ ste-
vamo, mnoˇ zimo in delimo (v resnici mnoˇ zimo z multiplikativnim inverzom).
Z razvojem teorije kodiranja, kriptografije in ˇ stevilnih kriptosistemov, ki
uporabljajo konˇ cne obsege, se je pokazala potreba po izboljˇ savi algoritmov
za aritmetiko nad konˇ cnimi obsegi. Pri izvajanju kriptografskih aplikacij
se osnovne aritmetiˇ cne operacije v obsegih izvrˇ sijo zelo velikokrat, zato je
hitrost kljuˇ cnega pomena. Seˇ stevanje elementov je obiˇ cajno hitro, zato pa
sta mnoˇ zenje inˇ se posebej raˇ cunanje inverza ˇ casovno zahtevnejˇ si operaciji.
Raˇ cunalnikiskorajvednoraˇ cunajosˇ stevili,predstavljenimivdvojiˇ skem
sistemu. Naravno ˇ stevilo k∈[2
n
,2
n+1
), kjer je n∈N, lahko zapiˇ semo kot
k =2
n
k
n
+2
n−1
k
n−1
+···+2k
1
+k
0
, kjer je k
i
∈Z
2
in k
n
6=0. (1)
Obzornik mat. fiz. 57 (2010) 5 157

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 158 — #2
i
i
i
i
i
i
Jernej Tonejc
Slika 1.
ˇ
Ce bi nam bankomat odvrnil, da po njegovem izraˇ cunu morda le ni gotovo, da
smo pravi lastnik banˇ cne kartice, bi bili najbrˇ z nejevoljni. Priˇ cakujemo natanˇ cen odgovor
DA oziroma NE.
V raˇ cunalniku shranimo le (n + 1)-terico k
n
k
n−1
...k
1
k
0
.
ˇ
Ce je
s = s
n+1
s
n
...s
1
s
0
vsota ˇ stevil a = a
n
a
n−1
...a
1
a
0
in b = b
n
b
n−1
...b
1
b
0
,
manjˇ sih od 2
n+1
, potem za i∈{0,1,...,n} velja
d
i
= a
i
+b
i
+c
i−1
, s
i
= d
i
mod2, c
i
= d
i
div2 in s
n+1
= c
n
. (2)
Z div smo oznaˇ cili celoˇ stevilsko deljenje, c
i
pa je seveda prenos pri seˇ steva-
nju. Pri tem privzamemo c
−1
= 0 in opomnimo, da je ˇ stevilo s
n+1
lahko
tudi enako 0.
Tudi polinom p(x) stopnje n s koeficienti iz Z
2
je primeren za hranjenje
v raˇ cunalniˇ skem pomnilniku, saj za
p(x)=
n
X
i=0
p
i
x
i
, kjer p
i
∈Z
2
in p
n
6=0, (3)
spet shranimo samo (n + 1)-terico p
n
p
n−1
...p
1
p
0
.
ˇ
Ce predstavlja
s
n
s
n−1
...s
1
s
0
vsoto polinomov stopnje kveˇ cjemu n, predstavljenih z
a
n
a
n−1
...a
1
a
0
in b
n
b
n−1
...b
1
b
0
, za vsak i∈{0,1,...,n} velja
s
i
= a
i
+b
i
mod2. (4)
Med zapisoma (1) in (3) na prvi pogled ni velike razlike, le ˇ stevilo
”
2“ za-
menjamo s spremenljivko
”
x“. Vendar pa raˇ cunalniˇ sko vezje za seˇ stevanje,
ki ga predstavlja enaˇ cba (4), sestavlja en sam
”
ekskluzivni ali“ (XOR), za
158 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 159 — #3
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
izraˇ cun izrazov v (2) pa potrebujemo zaradi morebitnega prenosa dvakrat
toliko vezja. V namenskih tiskanih vezjih se tako namesto praˇ stevilskih ob-
segov veˇ cinoma uporabljajo razˇ siritve dvojiˇ skega obsega. Drugi razlog za
njihovo uporabo izhaja iz vpraˇ sanja:
Ali je lahko kvadriranje bistveno hitrejˇ se od mnoˇ zenja?
Naslednja identiteta
a·b=
(a+b)
2
−(a−b)
2
4
nakazuje, da je odgovor najbrˇ z NE. Kajti ˇ ce bi znali
”
zelo“ hitro kvadrirati,
potem bi kveˇ cjemu dvakrat poˇ casneje lahko izraˇ cunali tudi produkt. Ta
enaˇ cba seveda velja le, ˇ ce karakteristika obsega ni enaka 2. V razˇ siritvah
dvojiˇ skih obsegov pa je nekoliko drugaˇ ce. V tem primeru namreˇ c obstajajo
t. i. normalne baze, v katerih je kvadriranje povsem enostavno. Izvedemo
galescikliˇ cnimzamikom, mnoˇ zenjepaostaneteˇ zko(kvadratnezahtevnosti
glede na dolˇ zino zapisa). Zato se bomo osredotoˇ cili na aritmetiko dvojiˇ skih
obsegov, na katere bodo vezani tudi vsi naˇ si primeri.
V nadaljevanju najprej predstavimo osnove konˇ cnih obsegov, nato pa se
posvetimoaritmetikivrazˇ siritvahdvojiˇ skegaobsega. Seˇ stevanjejeobiˇ cajno
relativnohitraoperacija(linearnagledenadolˇ zinozapisapodatkov),karpo-
tem ne velja za mnoˇ zenje. Obstaja pa tudi takˇ sna predstavitev elementov,
da je mnoˇ zenje hitro in seˇ stevanje poˇ casno, kot bomo videli v naslednjem
razdelku. Nato vpeljemo polinomske baze in opiˇ semo metode mnoˇ zenja,
kvadriranja in redukcije v njih. Posebej obravnavamo deljenje, ki ga izva-
jamospomoˇ cjorazˇ sirjenegaEvklidovegaalgoritma. Opiˇ semotudielegantno
Berlekampovo izvedbo razˇ sirjenega Evklidovega algoritma, ki je ˇ se posebej
uporabna za raˇ cunalnike z zelo malo pomnilnika. Na koncu predstavimo
vlogo konˇ cnih obsegov v kriptografiji, kjer je uˇ cinkovita aritmetika pogosto
kljuˇ cnega pomena pri reˇ sevanju raˇ cunsko zahtevnih problemov.
Konˇ cni obsegi
Spomnimo se, da je obseg tak kolobar z enoto za mnoˇ zenje, v katerem
je vsak neniˇ celn element obrnljiv. Podobseg pa je podmnoˇ zica obsega, ki je
za isti operaciji tudi obseg. Za vsak konˇ cen obseg obstaja tako najmanjˇ se
naravnoˇ stevilop,zakateroveljaa+a+···+a= p·a=0,kjerjeapoljuben
element danega obsega. Tako ˇ stevilo p imenujemo karakteristika konˇ cnega
157–175 159

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 160 — #4
i
i
i
i
i
i
Jernej Tonejc
obsega in mora biti zaradi minimalnosti praˇ stevilo. Mnoˇ zica ostankov pri
deljenju s praˇ stevilom p, skupaj z obiˇ cajnim seˇ stevanjem in mnoˇ zenjem po
modulu p, tvori obseg Z
p
={0,1,...,p−1}, ki mu pravimo praobseg in ga
spoznamoˇ zepriˇ studijudeljivostinaravnihˇ stevil. Le-tanimapravnobenega
netrivialnega podobsega!
Izrek 1. Moˇ c poljubnega konˇ cnega obsega je enaka p
n
, kjer je p neko pra-
ˇ stevilo in n neko naravno ˇ stevilo.
Skica dokaza. Naj bo F poljuben konˇ cen obseg in p njegova karakteristika.
V tem obsegu enota za mnoˇ zenje generira podobseg, ki je izomorfen praob-
segu Z
p
. Obseg F je vektorski prostor nad tem podobsegom Z
p
, saj je za
seˇ stevanje komutativna grupa, skalarno mnoˇ zenje vektorjev pa je kar obi-
ˇ cajno mnoˇ zenje v F. Ker je obseg konˇ cen, ima kot vektorski prostor tudi
konˇ cno razseˇ znost. Oznaˇ cimo jo z n.
ˇ
Stevilo elementov tega obsega je torej
enako p
n
.
V nadaljevanju bomo videli, kako konstruiramo konˇ cni obseg s p
n
ele-
menti za poljubno praˇ stevilo p in poljubno naravnoˇ stevilo n. Krajˇ si uvod v
grupe in konˇ cne obsege najdemo v [6], bolj obˇ siren pa v [12]. Konˇ cni obsegi
so podrobno predstavljeni v [8], s kriptografskega staliˇ sˇ ca pa v [9] in [10].
Piˇ simo q = p
n
. Ker so vsi konˇ cni obsegi z enakim ˇ stevilom elementov
med seboj izomorfni, bomo obseg s q elementi oznaˇ cili z GF(q), kjer je
GF okrajˇ sava za Galoisov obseg (angl. Galois field), in ga obravnavali kot
vektorski prostor nad obsegom Z
p
.
ˇ
Ce so elementi α
0
,α
1
,...,α
n−1
baza
prostoraGF(q)nadobsegomZ
p
,lahkovsakelementobsegaGF(q)zapiˇ semo
v obliki vsote
n−1
X
i=0
a
i
α
i
, kjer a
i
∈Z
p
,
ali krajˇ se kot vektor (a
n−1
,a
n−2
,...,a
1
,a
0
).
Mnoˇ zica neniˇ celnih elementov obsega GF(q) tvori za mnoˇ zenje grupo
moˇ ci q− 1, ki jo oznaˇ cimo z GF(q)
∗
in imenujemo multiplikativna grupa
konˇ cnega obsega. Lagrangeev izrek nam pove, da red poljubnega elementa
konˇ cne grupe deli moˇ c te grupe (glej npr. [12, str. 57]), od koder takoj sledi,
da vsak element grupe GF(q)
∗
reˇ si enaˇ cbo
x
q−1
=1. (5)
160 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 161 — #5
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
Izrek 2. Multiplikativna grupa GF(q)
∗
konˇ cnega obsega GF(q) je cikliˇ cna.
Kot je bralec verjetno ˇ ze uganil, bo enaˇ cba (5) v dokazu izreka imela
kljuˇ cno vlogo. Preden se lotimo dokaza izreka, potrebujemo ˇ se dve lemi.
Lema 3. Oznaˇ cimo s ϕ Eulerjevo funkcijo, tj. ϕ(n) je ˇ stevilo naravnih ˇ ste-
vil, manjˇ sih od n, ki so si tuja z n. Potem za vsako naravno ˇ stevilo m
velja
X
d|m
ϕ(d)= m. (6)
Dokaz. Oglejmosimnoˇ ziceA(d)=
 k∈{1,...,m}: D(k,m)= d
 . Oˇ citno
velja A(d) = ∅, ˇ ce d - m in A(d
1
)∩A(d
2
) = ∅, ˇ ce d
1
6= d
2
. Ker za vsako
naravno ˇ stevilo k6 m obstaja d, za katerega je D(k,m)= d, velja
{1,...,m}=
[
d|m
A(d),
kjer vzamemo unijo po vseh deliteljih ˇ stevila m. Koliko elementov pa
ima A(d)? Vsak k ∈ A(d) je veˇ ckratnik ˇ stevila d, torej velja A(d) ⊆
 d,2d,...,
m
d
d
 . Ker velja ˇ se
D(‘d,m)= d ⇐⇒ D
 ‘d,
m
d
d
 = d ⇐⇒ D
 ‘,
m
d
 =1,
je moˇ c mnoˇ zice A(d) natanko ϕ
 m
d
 .
ˇ
Ce upoˇ stevamo, da so mnoˇ zice A(d)
med seboj disjunktne, vidimo, da smo dokazali naslednje:
X
d|m
ϕ
 m
d
 = m.
Kodpreteˇ cevsedeliteljeˇ stevilam,tudi
m
d
preteˇ cevsedelitelje(vobratnem
vrstnem redu), torej lahko zgornjo enakost zapiˇ semo kot
X
d|m
ϕ(d)= m,
kar smo ˇ zeleli dokazati.
157–175 161

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 162 — #6
i
i
i
i
i
i
Jernej Tonejc
Lema 4. Naj bo F poljuben komutativen obseg in m poljubno naravno ˇ ste-
vilo.
ˇ
Ce ima enaˇ cba
x
m
=1 (7)
v F natanko m reˇ sitev, potem obstaja taka reˇ sitev g∈F, da velja g
k
6=1 za
vsa naravna ˇ stevila k < m.
Dokaz. Preprosto je videti, da je mnoˇ zica vseh reˇ sitev te enaˇ cbe v F grupa
za mnoˇ zenje, saj je po predpostavki F komutativen. Naj bo a∈F poljubna
reˇ sitev enaˇ cbe (7). Potem obstaja najmanjˇ se naravno ˇ stevilo d 6 m, da
velja a
d
=1, imenujmo ga minimalna stopnja elementa a. Oˇ citno d deli m,
sicer pridemo v protislovje z minimalnostjo. Elementi a
0
,a
1
,a
2
,...,a
d−1
so zaradi minimalnosti d med seboj razliˇ cni, reˇ sijo enaˇ cbo (7), hkrati pa
zadoˇ sˇ cajo enaˇ cbi x
d
=1, saj za k∈Z velja
(a
k
)
m
= a
km
=(a
m
)
k
=1
k
=1, (a
k
)
d
= a
kd
=(a
d
)
k
=1
k
=1.
Ker ima enaˇ cba x
d
=1 kveˇ cjemu d reˇ sitev, so to natanko vse moˇ zne reˇ sitve.
Torejjepoljubenelementzminimalnostopnjodvmnoˇ zici{a,a
2
,...,a
d−1
}.
Zanimajo nas torej tisti elementi a
k
, 1 6 k 6 d− 1, katerih minimalna
stopnja je prav tako d. To se zgodi takrat, ko je k tuj proti d. Takih je
natanko ϕ(d).
Za vsako reˇ sitev enaˇ cbe (7) obstaja neki delitelj ˇ stevila m, ki je mini-
malna stopnja te reˇ sitve. Za poljubna razliˇ cna delitelja d
1
,d
2
ˇ stevila m sta
mnoˇ zici reˇ sitev z minimalnima stopnjama d
1
in d
2
disjunktni. Pravkar smo
videli, da imamo natanko ϕ(d) reˇ sitev z minimalno stopnjo d, kakor hitro
imamo vsaj eno. Torej imamo natanko
X
ϕ(d) (8)
reˇ sitev, kjer seˇ stevamo po vseh tistih deliteljih ˇ stevila m, za katere obstaja
vsaj ena reˇ sitev z minimalno stopnjo d. Primerjajmo ta izraz z lemo 3. Ker
smopredpostavili, daimaenaˇ cba(7) mreˇ sitev, hkratipavelja(6), moramo
v vsoti (8) seˇ stevati po vseh deliteljih ˇ stevila m. Torej je v njej tudi ˇ clen
ϕ(m), kar pomeni, da obstaja vsaj en element g ∈ F, ki reˇ si enaˇ cbo (7),
katerega minimalna stopnja je m, kar je ravno to, kar smo ˇ zeleli dokazati.
162 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 163 — #7
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
Element g iz leme imenujemo primitivni m-ti koren enote v obsegu F.
Sedaj imamo vse, kar potrebujemo za dokaz izreka.
Dokaz izreka 2. Wedderburnov izrek [12, str. 288] nam pove, da je vsak
konˇ cenobsegkomutativen, torejlahkozaGF(q)uporabimorezultat, kismo
ga pravkar dokazali. Videli smo, da ima enaˇ cba (5) natanko q−1 reˇ sitev
v GF(q), zato v GF(q) obstaja primitivni (q−1)-vi koren enote. To pa je
ravno generator GF(q)
∗
, torej je multiplikativna grupa konˇ cnega obsega res
cikliˇ cna.
Obseg GF(q) torej sestavljajo elementi 0,z,z
2
,...,z
q−1
, kjer je z primi-
tivni (q−1)-vi koren enote. Pri takem naˇ cinu predstavitve elementov obsega
je mnoˇ zenje hitro, saj v pomnilnik namesto elementa z
k
zapiˇ semo le ekspo-
nent k. Ker velja z
k
1
·z
k
2
= z
k
1
+k
2
, produkta ni teˇ zko izraˇ cunati. Vendar
v tej predstavitvi ne znamo hitro in enostavno izraˇ cunati vsote. Za k
1
6 k
2
je z
k
1
+z
k
2
= z
k
1
(1+z
k
2
−k
1
), zato zadoˇ sˇ ca, da za vsak k ∈ Z
q
poznamo
eksponent ‘ ∈ Z
q
, za katerega velja z
‘
= z
k
+1. Tabela vseh takih parov
je poznana pod imenom ZechLog tabela. Medtem ko za majhne q taka ta-
bela poenostavi raˇ cunanje, pa za velike konˇ cne obsege izraˇ cun vseh parov
(k,‘) ni enostaven, njihovo hranjene pa zavzame tudi veliko raˇ cunalniˇ skega
pomnilnika. Za primer navedimo, da bi ˇ ze za GF(2
40
) bila potrebna koli-
ˇ cinapomnilnikazahranjenjetabelekar5terabajtov, medtemkosevpraksi
uporabljajo konˇ cni obsegi velikosti vsaj 2
160
.
Najbolj znana konstrukcija razˇ siritev konˇ cnih obsegov sloni na neraz-
cepnih polinomih. Iskanje nerazcepnega polinoma stopnje m iz kolobarja
GF(q)[x] v sploˇ snem ni tako enostavno, saj ne obstaja dokazano determi-
nistiˇ cen algoritem s polinomsko ˇ casovno zahtevnostjo (tj. ˇ stevilo operacij
v GF(q), ki jih algoritem opravi, je omejeno z nekim polinomom v m in
n, kjer je q = p
n
). Trenutno znani dokazi namreˇ c temeljijo na veljavnosti
posploˇ sene Riemannove hipoteze. Da problem kljub vsemu ni brezupen,
nas prepriˇ ca dejstvo, da obstajajo precej uˇ cinkoviti verjetnostni algoritmi.
Konkretne konstrukcije nerazcepnih polinomov lahko bralec najde v [10,
pogl. 3].
Izrek 5. Naj bo m∈N inGF(q
m
) konˇ cen obseg, ki vsebuje podobsegGF(q).
Potem v kolobarju polinomov GF(q)[x] obstaja nerazcepen polinom f(x) sto-
157–175 163

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 164 — #8
i
i
i
i
i
i
Jernej Tonejc
pnje m, za katerega je
GF(q
m
)
∼
= GF(q)[x]/(f(x)),
kjer je GF(q)[x]/(f(x)) obseg polinomov nad GF(q), reduciranih po modulu
polinoma f(x). Veljaˇ se GF(q
m
)
∼
= GF(q)(α), kjer je α niˇ cla polinoma f(x).
Skica dokaza. Ker je f(x) nerazcepen, je GF(q)[x]/(f(x)) obseg z natanko
q
m
elementi.
ˇ
Ze prej smo videli, da vsak neniˇ celn element a∈ GF(q
m
) reˇ si
enaˇ cbo x
q
m
−1
= 1.
ˇ
Ce to enaˇ cbo pomnoˇ zimo z x, potem je njena reˇ sitev
tudi 0, od koder takoj sledi, da je vsak obseg s q
m
elementi razpadni obseg
polinoma x
q
m
−x. Ker so vsi razpadni obsegi istega polinoma med seboj
izomorfni, velja GF(q)[x]/(f(x))
∼
= GF(q
m
). Dokazati moramo torej obstoj
nerazcepnega polinoma f(x)∈ GF(q)[x] stopnje m. Oznaˇ cimo z N
q
ˇ stevilo
nerazcepnih polinomov v GF(q)[x] stopnje m z vodilnim koeficientom 1, ki
delijo x
q
m
−x. Velja ocena
1
2m
6
N
q
q
m
6
1
m
,
od koder sledi, da nerazcepen polinom f(x) ∈ GF(q)[x] stopnje m mora
obstajati. Za dokaz zadnje trditve v izreku si oglejmo naravno projekcijo
π: GF(q)[x]→GF(q)[x]/(f(x)), π: g(x)7→ g(x)mod f(x).
Enostavno je videti, da je π(x) niˇ cla polinoma f(x), od koder trditev takoj
sledi.
Elementi obsega GF(q
m
) tako ustrezajo polinomom nad GF(q) stopnje
manj kot m. Seˇ stevanje polinomov iz kolobarja GF(q)[x] stopnje manj kot
m se enostavno prevede v kveˇ cjemu m seˇ stevanj elementov obsega GF(q),
kot smo videli ˇ ze v uvodu. Pri mnoˇ zenju pa ne gre tako zlahka, saj lahko
stopnja produkta dveh polinomov doseˇ ze oz. preseˇ ze stopnjo nerazcepnega
polinoma f(x) in je zato potrebna redukcija po modulu polinoma f(x).
Primer 1. Konstruirajmo obseg GF(2
3
). Najprej moramo najti nerazce-
pen polinom stopnje 3 nad Z
2
. Najbolj preprosto bi bilo poskusiti kar z
binomom. Vendar pa za polinom f(x) s sodo mnogo neniˇ celnimi ˇ cleni nad
Z
2
velja f(1) = 0, kar pomeni, da je f(x) razcepen. Zato mora imeti ne-
razcepen polinom iz kolobarja Z
2
[x] liho ˇ stevilo neniˇ celnih ˇ clenov. Njegov
164 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 165 — #9
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
konstantni ˇ clen je neniˇ celn, sicer bi bil polinom deljiv z x. Tako sta edina
kandidata f
1
(x) = x
3
+x+1 in f
2
(x) = x
3
+x
2
+1. Oba sta nerazcepna
nad Z
2
, saj 0 in 1 nista niˇ cli nobenega izmed njiju. Naj bo μ niˇ cla polinoma
f
1
(x). Potem je μ
3
= μ+1 in elementi obsega GF(2
3
) so
0,μ,μ
2
,μ
3
= μ+1,μ
4
= μ
2
+μ,μ
5
= μ
2
+μ+1,μ
6
= μ
2
+1,μ
7
=1.
Za niˇ clo ν polinoma f
2
(x) pa velja ν
3
= ν
2
+1 in dobimo naslednjo upodo-
bitev:
0,ν,ν
2
,ν
3
= ν
2
+1,ν
4
= ν
2
+ν +1,ν
5
= ν +1,ν
6
= ν
2
+ν,ν
7
=1.
V obeh primerih lahko to zapiˇ semo kot trojice a
2
a
1
a
0
, kjer a
i
∈Z
2
ustreza
koeficientu pri μ
i
oz. ν
i
na desni strani enaˇ caja. V primeru ν tako dobimo
000,010,100,101,111,011,110,001.  Polinomske baze
Naj bo f(x) nerazcepen polinom stopnje m iz kolobarja GF(q)[x] in naj
bo α njegova niˇ cla. Minimalni polinom elementa α je tak polinom r(x), za
katerega velja r(α)=0, ima vodilni koeficient enak 1 in ima med vsemi po-
linomi s pravkar omenjenima lastnostma najmanjˇ so stopnjo. Vsak polinom
g(x) ∈ GF(q)[x], ki ima element α za niˇ clo, je zato deljiv z minimalnim
polinomom r(x) elementa α. Ker pa je polinom f(x) nerazcepen, mora
biti kar enak skalarnemu veˇ ckratniku minimalnega polinoma r(x). Zato
element α ni niˇ cla nobenega neniˇ celnega polinoma iz kolobarja GF(q)[x]
stopnje manjˇ se od m. Sledi, da morajo biti elementi 1,α,...,α
m−1
linearno
neodvisni nad GF(q) in zato sestavljajo bazo. Imenujemo jo polinomska
baza vektorskega prostora GF(q
m
) nad obsegom GF(q). Torej vsaka niˇ cla
nerazcepnega polinoma stopnje m iz kolobarja GF(q)[x] doloˇ ca polinomsko
bazo v GF(q
m
). Pri zapisu elementov konˇ cnega obsega GF(2
m
) v polinom-
ski bazi pogosto namesto niˇ cle α polinoma f(x) piˇ semo kar x. Za razliˇ cne
nerazcepne polinome dobimo razliˇ cne baze istega vektorskega prostora.
Primer 2.
ˇ
Ze v prejˇ snjem primeru smo se prepriˇ cali, da je polinom f(x)=
x
3
+x
2
+1nerazcepennadZ
2
. TorejjeGF(2
3
)
∼
=Z
2
[x]/(f(x))
∼
=Z
2
(ν),kjer
157–175 165

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 166 — #10
i
i
i
i
i
i
Jernej Tonejc
je ν niˇ cla polinoma f(x), mnoˇ zica {ν
2
,ν,1} pa je polinomska baza obsega
GF(2
3
). Vsakelementzapiˇ semokota
2
ν
2
+a
1
ν+a
0
,kartakokotvprejˇ snjem
primeruokrajˇ samovtrojicoa
2
a
1
a
0
. Tabela1prikazujeprodukteelementov
v GF(2
3
).
· 000 001 010 011 100 101 110 111
000 000 000 000 000 000 000 000 000
001 000 001 010 011 100 101 110 111
010 000 010 100 110 101 111 001 011
011 000 011 110 101 001 010 111 100
100 000 100 101 001 111 011 010 110
101 000 101 111 010 011 110 100 001
110 000 110 001 111 010 100 011 101
111 000 111 011 100 110 001 101 010
Tabela 1. Mnoˇ zenje v obsegu GF(2
3
).
Za zgled zmnoˇ zimo npr. elementa ν +1 in ν
2
+ν:
(ν +1)(ν
2
+ν)= ν
3
+ν
2
+ν
2
+ν = ν
3
+ν =(ν
2
+1)+ν = ν
2
+ν +1. Preprosta metoda mnoˇ zenja elementov obsega GF(2
m
), predstavljenih
v polinomski bazi {x
m−1
,x
m−2
,...,x,1} z nerazcepnim polinomom f(x)
stopnje m, temelji na zvezi
a(x)·b(x)= a
0
b(x)+a
1
xb(x)+···+a
m−1
x
m−1
b(x).
Po vrsti rekurzivno raˇ cunamo x
i
b(x) (mod f(x)) za i ∈ {1,2,...,m−
1} in priˇ stevamo tiste ˇ clene, pri katerih je a
i
enak 1. Produkt x· b(x)
(mod f(x)) izraˇ cunamo z zamikom koordinat vektorja b(x). Spravimo ga
kar v b(x) ter mu na vsakem koraku priˇ stejemo polinom f(x), ˇ ce je pred
zamikom b
m−1
enak 1. Tak pristop se dobro obnese v strojni opremi, kjer
delamo na bitnem nivoju in lahko izvedemo zamik vektorja v enem ciklu.
V programski implementaciji pa elemente obiˇ cajno shranjujemo kot vek-
torje w-bitnih besed A = (A[t−1],...,A[1],A[0]), kjer je t =dm/we, zato
pri takem pristopu potrebujemo m− 1 zamikov besed. Mnoˇ zenje lahko
izvedemo hitreje, ˇ ce najprej zmnoˇ zimo elemente brez sprotnega reducira-
nja (kot obiˇ cajno mnoˇ zimo polinome) in na koncu napravimo redukcijo
166 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 167 — #11
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
po modulu nerazcepnega polinoma f(x). Pri tem izraˇ cunanemu x
k
b(x) za
k∈{0,1,...,w−1} dodamo na konec j niˇ celnih besed in dobimo element
x
wj+k
b(x). Tako za mnoˇ zenje porabimo samo w− 1 vektorskih zamikov
(mnoˇ zenj z x). Podrobnejˇ si opis algoritma za mnoˇ zenje in njegovih izbolj-
ˇ sav je v [4, pogl. 2].
Posebej omenimo kvadriranje polinomov v obsegih karakteristike 2, ki
je mnogo hitrejˇ se od mnoˇ zenja dveh razliˇ cnih polinomov. Kvadriranje dvo-
jiˇ skih polinomov je linearna operacija, kvadrat polinoma a(x) =
m−1
X
i=0
a
i
x
i
je namreˇ c kar a(x)
2
=
m−1
X
i=0
a
i
x
2i
. Kvadrat elementa dobimo z vstavitvijo
niˇ celnih bitov med bite elementa a(x):
(a
m−1
,a
m−2
,...,a
1
,a
0
)7−→(a
m−1
,0,a
m−2
,0,...,0,a
1
,0,a
0
).
Raˇ cunanje v polinomskih bazah je bolj uˇ cinkovito, ˇ ce je nerazcepni poli-
nom f(x) iz izreka 5 enostavnejˇ si. V praksi izberemo take f(x), ki imajo
malo neniˇ celnih koeficientov, saj to poenostavi modularno redukcijo s poli-
nomom f(x). Polinome s tremi neniˇ celnimi ˇ cleni imenujemo trinomi. Le-ti
omogoˇ cajo hitrejˇ so implementacijo aritmetike konˇ cnih obsegov. V tabeli 2
so naˇ steti nerazcepni trinomi nad obsegom Z
2
stopnje m ∈ (150,500), ki
se pogosto uporabljajo v kriptosistemih z eliptiˇ cnimi krivuljami. V tabeli
je zapisano ˇ stevilo m, za katero nerazcepen trinom obstaja, ter najmanjˇ se
ˇ stevilo k, za katero je polinom x
m
+x
k
+1 nerazcepen nad Z
2
.
Tako pri mnoˇ zenju kot tudi pri kvadriranju polinomov lahko stopnja
produkta c(x) doseˇ ze ali preseˇ ze stopnjo m izbranega nerazcepnega poli-
noma f(x). Stopnja produkta je lahko najveˇ c 2m− 2, zmanjˇ samo pa jo
z redukcijo po modulu nerazcepnega polinoma f(x). Vzemimo vektor w-
bitnih besed C = (C[n],C[n− 1],...,C[1],C[0]) in opiˇ simo algoritem, ki
temelji na dejstvu, da za i ≥ m velja x
i
= x
i−m
f
1
(x) (mod f(x)), kjer je
f
1
(x)= f(x)−x
m
.
ˇ
Ce je f(x) trinom, potem je x
m
= x
k
+1 in je redukcija uˇ cinkovitejˇ sa,
saj moramo pri reduciranjuˇ clena x
i
za i≥ m popraviti vektor C le na dveh
mestih: pri x
i−(m−k)
in x
i−m
. Ob redukciji naslednjega ˇ clena x
i−1
popra-
vljamo sosednje bite prej omenjenih mest. Zato lahko redukcijo izvajamo
nad besedami namesto nad biti in s tem pohitrimo algoritem.
157–175 167

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 168 — #12
i
i
i
i
i
i
Jernej Tonejc
m k m k m k m k m k m k m k
151 3 153 1 154 15 155 62 156 9 159 31 161 18
162 27 166 37 167 6 169 34 170 11 172 1 174 13
175 6 177 8 178 31 180 3 182 81 183 56 185 24
186 11 191 9 193 15 196 3 198 9 199 34 201 14
202 55 204 27 207 43 209 6 210 7 212 105 214 73
215 23 217 45 218 11 220 7 223 33 225 32 228 113
231 26 233 74 234 31 236 5 238 73 239 36 241 70
242 95 244 111 247 82 249 35 250 103 252 15 253 46
255 52 257 12 258 71 260 15 263 93 265 42 266 47
268 25 270 53 271 58 273 23 274 67 276 63 278 5
279 5 281 93 282 35 284 53 286 69 287 71 289 21
292 37 294 33 295 48 297 5 300 5 302 41 303 1
305 102 308 15 310 93 313 79 314 15 316 63 318 45
319 36 321 31 322 67 324 51 327 34 329 50 330 99
332 89 333 2 337 55 340 45 342 125 343 75 345 22
346 63 348 103 350 53 351 34 353 69 354 99 358 57
359 68 362 63 364 9 366 29 367 21 369 91 370 139
372 111 375 16 377 41 378 43 380 47 382 81 383 90
385 6 386 83 388 159 390 9 391 28 393 7 394 135
396 25 399 26 401 152 402 171 404 65 406 141 407 71
409 87 412 147 414 13 415 102 417 107 418 199 420 7
422 149 423 25 425 12 426 63 428 105 431 120 433 33
436 165 438 65 439 49 441 7 444 81 446 105 447 73
449 134 450 47 455 38 457 16 458 203 460 19 462 73
463 93 465 31 468 27 470 9 471 1 473 200 474 191
476 9 478 121 479 104 481 138 484 105 486 81 487 94
489 83 490 219 492 7 494 17 495 76 497 78 498 155
Tabela 2. Nerazcepni trinomi nad Z2. Do te tabele lahko pridemo na poˇ zreˇ sen naˇ cin
(podobno kot npr. pri Eratostenovem reˇ setu) tako, da najprej zmnoˇ zimo vse nerazcepne
linearne polinome, tj. x in x+1. Njihovi produkti x
2
, x
2
+x, x
2
+1 oˇ citno ne
”
pokrijejo“
vseh (ˇ stirih) polinomov stopnje 2. Zato je polinom x
2
+x+1 nerazcepen. Sedaj mno-
ˇ zimo x in x+1 s polinomi stopnje 2 in ugotovimo, da pri stopnji 3 tudi ne
”
pokrijemo“
vseh polinomov. Z nadaljevanjem tega postopka lahko poiˇ sˇ cemo vse nerazcepne polinome
ˇ zelene stopnje. Kadar za neki m ne obstaja nerazcepen trinom, iˇ sˇ cemo nerazcepen pen-
tanom ali heptanom. Za vse m6 10000 obstaja vsaj nerazcepen pentanom, kolikor ni ˇ ze
nerazcepnega trinoma stopnje m, glej [11].
Invertiranje in razˇ sirjeni Evklidov algoritem
Za invertiranje elementov obsega GF(2
m
) lahko uporabimo razˇ sirjeni
Evklidov algoritem [1, razdelek 2.1], ki ga bomo podrobneje opisali v nada-
ljevanju.
168 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 169 — #13
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
Slika 2. Evklid
Morda je sicer na prvi pogled bolj naravna metoda potenciranja, saj za
vsak α∈GF(2
m
)velja α
2
m
= α, odkoderza α6=0sledi α
−1
= α
2
m
−2
. Tak
pristop se dobro obnese v teoriji, vendar pa se razˇ sirjeni Evklidov algoritem
v praksi izkaˇ ze za dosti hitrejˇ sega. Za m = 173 pri raˇ cunanju inverza s
potenciranjem porabimo 10 mnoˇ zenj, medtem ko lahko z razˇ sirjenim Evkli-
dovim algoritmom inverzni element dobimo s 3–4 mnoˇ zenji.
Za dani polinom a(x) ∈ Z
2
[x] stopnje manj od m iˇ sˇ cemo tak polinom
p(x) ∈ Z
2
[x] stopnje manj od m, da velja a(x)p(x) ≡ 1 (mod f(x)). To
pomeni, da obstaja tak polinom q(x), da v kolobarju polinomov Z
2
[x] velja
a(x)p(x)+q(x)f(x)=1. (9)
Ker je polinom f(x) nerazcepen, je najveˇ cji skupni delitelj polinomov f(x)
in a(x) enak 1. V sploˇ snem je enaˇ cbo (9) teˇ zko reˇ siti, zato si pomagamo z
enostavnejˇ simi primeri. Poznamo namreˇ c reˇ sitev enaˇ cbe (9), kadar na desni
strani stoji bodisi f(x) ali a(x). V prvem primeru je reˇ sitev kar p(x) = 0
in q(x) = 1. V drugem primeru, ko je na desni a(x), pa enaˇ cbo reˇ si par
p(x) = 1 in q(x) = 0. Zdaj lahko z iterativno metodo poiˇ sˇ cemo zaporedji
polinomov p
i
in q
i
, za kateri velja ap
i
+ fq
i
= r
i
. Upoˇ stevamo omenjena
posebna primera in zaˇ cnemo z r
−2
= f, r
−1
= a, p
−2
=0, p
−1
=1, q
−2
=1
in q
−1
=0. Na vsakem koraku iˇ sˇ cemo taka polinoma s
i
in r
i
, da velja
r
i−2
= s
i
r
i−1
+r
i
,
pri ˇ cemer je stopnja polinoma r
i
manjˇ sa od stopnje polinoma r
i−1
. Posta-
vimo ˇ se
q
i
= s
i
q
i−1
+q
i−2
in p
i
= s
i
p
i−1
+p
i−2
157–175 169

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 170 — #14
i
i
i
i
i
i
Jernej Tonejc
terponavljamopostopek,doklernanekemkorakunedobimor
k
=0. Iskana
reˇ sitev je potem q(x) = q
k−1
in p(x) = p
k−1
, kjer je stopnja q manjˇ sa od
stopnje a, stopnja p pa manjˇ sa od stopnje f. Potrebujemo le polinom p(x),
zato zaporedja q
i
sploh ne raˇ cunamo. Za laˇ zjo predstavo si oglejmo primer.
Primer 3. Naj bo a(x)= x
4
+x+1 in f(x)= x
5
+x
2
+1. Poiˇ sˇ cimo inverz
polinoma a(x).
r
−2
= x
5
+x
2
+1 = x(x
4
+x+1)+x+1
r
−1
= x
4
+x+1 = (x
3
+x
2
+x)·(x+1)+1
r
0
= x+1 = (x+1)·1+0
x·1+0 = x= p
0
(x)
(x
3
+x
2
+x)·x+1 = x
4
+x
3
+x
2
+1= p
1
(x)
(x+1)·(x
4
+x
3
+x
2
+1)+x = x
5
+x
2
+1= p
2
(x).
V zadnji vrstici postane ostanek r
2
enak 0, zato je inverz polinoma a(x)
enak p
1
(x). Podrobneje si oglejmo ta postopek z vidika raˇ cunalnikov. Ra-
ˇ cunalnik polinome deli postopoma, tako da mnoˇ zi polinom niˇ zje stopnje
z ustrezno potenco elementa x. To pomeni, da izvaja cikliˇ cni zamik, vse
dokler nimata oba polinoma enake stopnje. Nato zamenja polinom, ki je
na zaˇ cetku viˇ sje stopnje, z njuno razliko. Postopek ponavlja, vse dokler se
stopnjatistegapolinoma,kiimaviˇ sjoalienakostopnjo,nezmanjˇ sapodsto-
pnjodrugegapolinoma. Takosepodelihizraˇ cunavsakpolinoms
i
. Oglejmo
si pravkar opisani postopek na naˇ sem primeru. Za i=0 se v prvem koraku
r
−1
najprej pomnoˇ zi z elementom x. Razlika med r
−2
in x·r
−1
je linearni
polinomr
0
= x+1intakojselahkoizraˇ cunap
0
= s
0
·p
−1
+p
−2
= x·1+0= x.
Nato se za i = 1 (pri deljenju polinoma r
−1
z r
0
) ostanek iz prejˇ snjega ko-
raka r
0
najprej mnoˇ zi z ustrezno potenco elementa x, kar predstavlja prvi
sumand v s
1
, recimo mu s
11
:
r
−1
= x
4
+x+1= x
3
·(x+1)+x
3
+x+1.
Razlika med r
−1
in x
3
·r
0
je polinom x
3
+x+1, ki je viˇ sje stopnje od r
0
.
Zato se polinoma zamenja in postopek se ponovi. Pri tem se spet mnoˇ zi
170 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 171 — #15
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
z ustrezno potenco elementa x, ki zdaj predstavlja drugi del polinoma s
1
,
tj. s
12
:
x
3
+x+1= x
2
·(x+1)+x
2
+x+1.
Ker je razlika med x
3
+ x + 1 in x
2
· r
0
ˇ se vedno viˇ sje stopnje od r
0
, se
ju spet zamenja in mnoˇ zi r
0
z elementom x, kar ustreza tretjemu sumandu
polinoma s
1
, tj. s
13
:
x
2
+x+1= x·(x+1)+1.
Sedaj je ostanek enak 1 in je niˇ zje stopnje od linearnega polinoma r
0
. Tako
se po delih izraˇ cuna s
1
= s
11
+ s
12
+ s
13
. Ob tem se vzporedno raˇ cuna
polinom p
1
= s
1
p
0
+p
−1
kot
((s
11
p
0
+p
−1
)+s
12
p
0
)+s
13
p
0
=((x
3
·x+1)+x
2
·x)+x·x= x
4
+x
3
+x
2
+1.
Podobno v tretjem koraku (i=2) iz r
0
= x+1=(x+1)·1+0 sledi, da je
s
2
= x+1, r
1
=1 in r
2
=0. Potem pa polinoma p
2
sploh ni treba raˇ cunati,
saj je inverz elementa a enak polinomu p
1
.  Berlekampov algoritem
Predstavimo Berlekampovo realizacijo razˇ sirjenega Evklidovega algorit-
ma [1, razdelek 2.3], ki je posebej prilagojena za raˇ cunalnike z zelo malo
pomnilnika, kot so na primer pametne kartice. Potrebujemo namreˇ c le dva
Slika 3. Elwyn Ralph Berlekamp
157–175 171

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 172 — #16
i
i
i
i
i
i
Jernej Tonejc
registra z m+2 biti, kjer je m stopnja nerazcepnega polinoma, opravimo
pa najmanjˇ se moˇ zno ˇ stevilo logiˇ cnih operacij. Ideja je v zamikanju parov
polinomov.
Koeficiente polinomov r in p postavimo skupaj tako, da najbolj levi bit
predstavlja vodilni koeficient polinoma r, najbolj desni bit pa vodilni koe-
ficient polinoma p. Na zaˇ cetku so v zgornjem registru koeficienti polinoma
r
−2
, katerim sledi enica, ki predstavlja p
−1
. V spodnji register pa na za-
ˇ cetek zloˇ zimo koeficiente polinoma r
−1
, katerim sledi p
−2
. Takˇ sen zapis je
najprimernejˇ si, saj polinomom r
i
stopnja pada, polinomom p
i
pa se veˇ ca.
Zaˇ cetno stanje prikazuje slika 4.
p r
a a a b b b
c c c d d d
x x x x 1 1
2 2
2 2
2 2 1 1
1 1
0 0
0 0
r p
-2
-2
-1
-1
. . .
. . . . . .
. . .
x x x x 1 1
2 2
Slika 4. Zaˇ cetno stanje registrov.
ˇ
Ce mnoˇ zimo polinom r
−1
z elementom x, zaradi povezave med enaˇ cbama
r
−2
= s
0
r
−1
+r
0
in p
0
= s
0
p
−1
+p
−2
hkrati mnoˇ zimo tudi p
−1
z elementom
x. Pri tem se levi del spodnjega registra, v katerem so zapisani koeficienti
polinoma r
−1
, zamakne za eno mesto v levo. Desni del zgornjega registra
pa se zaradi mnoˇ zenja p
−1
z x zamakne za eno mesto v desno. Zamika sta
prikazana na sliki 5.
b b b
2 1 0
c c c
2 1 0
x
3
x
3
p
-1
x r
r
-2
-1
x
a a a
d d d
x x x x 1
2 2
2
2 1
1
0
0
p
-2
. . .
. . . . . .
x x x x 1
2 2
. . .
Slika 5. Zamik registrov pri mnoˇ zenju z x.
172 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 173 — #17
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
Ta dva zamika pa sta ekvivalentna temu, da le zgornji register zamaknemo
za eno mesto v desno, kot prikazuje slika 6. Potem seveda ne moremo med
seboj primerjati bitov, ki leˇ zijo med obema odebeljenimaˇ crtama. Lahko pa
primerjamo tiste, ki leˇ zijo na levi strani bolj leve odebeljene ˇ crte, saj le-ti
ustrezajo enakim potencam elementa x. Podobno lahko med seboj primer-
jamo bite, ki leˇ zijo na desni strani bolj desne odebeljene ˇ crte in ustrezajo
naraˇ sˇ cajoˇ cim potencam elementa x.
a a a
x x
2
2 1 0
. . .
. . .
x x 1
2
d d d
x x 1
2
2 1 0
p
-2
. . .
r
r
-2
-1
x
x
3
c c c
2 1 0
x x
2
. . .
p
-1
x
x
3
b b b
2 1 0
Slika 6. Kompaktna oblika registrov.
Algoritem je sestavljen le iz zamikov in seˇ stevanj. Skupno ˇ stevilo zamikov
(Z) je 2m+1. Ker vsakemu seˇ stevanju (S) sledi zamik, ne more biti veˇ c
kot 2m seˇ stevanj in celoten algoritem ne zahteva veˇ c kot 4m+1 operacij.
Oglejmo si postopek na primeru iz prejˇ snjega razdelka. Z rimskimi ˇ ste-
vilkami so oznaˇ cene skupine operacij, ki ustrezajo posameznim vrsticam v
primeru, vejica pa ima enako vlogo kot odebeljena ˇ crta na slikah.
Primer 4.
I.
 1 0 0 1 0 1, 1
0 1 0 0 1 1, 0
 =
 r
−2
, p
−1
r
−1
, p
−2
 =
 f(x),1
a(x),0
 Z:
 1 0 0 1 0 1, 1
1 0 0 1 1, 0 0
 =
 r
−2
, xp
−1
xr
−1
, p
−2
 S:
 0 0 0 0 1 1, 1
1 0 0 1 1, 0 1
 =
 r
−2
+xr
−1
, xp
−1
xr
−1
, p
−2
+xp
−1
 157–175 173

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 174 — #18
i
i
i
i
i
i
Jernej Tonejc
II. Z:
 0 0 0 1 1, 1 0
1 0 0 1 1, 0 1
 =
 r
0
, p
−1
r
−1
, p
0
 3×Z:
 1 1, 1 0 0 0 0
1 0 0 1 1, 0 1
 =
 x
3
r
0
, p
−1
r
−1
, x
3
p
0
 S:
 1 1, 1 0 0 0 1
0 1 0 1 1, 0 1
 =
 x
3
r
0
, p
−1
+x
3
p
0
r
−1
+x
3
r
0
, x
3
p
0
 Z:
 1 1, 1 0 0 0 1
1 0 1 1, 0 1 0
 =
 x
2
r
0
, p
−1
+x
3
p
0
r
−1
+x
3
r
0
, x
2
p
0
 S:
 1 1, 1 0 0 1 1
0 1 1 1, 0 1 0
 =
 x
2
r
0
, p
−1
+(x
3
+x
2
)p
0
r
−1
+(x
3
+x
2
)r
0
, x
2
p
0
 Z:
 1 1, 1 0 0 1 1
1 1 1, 0 1 0 0
 =
 xr
0
, p
−1
+(x
3
+x
2
)p
0
r
−1
+(x
3
+x
2
)r
0
, xp
0
 S:
 1 1, 1 0 1 1 1
0 0 1, 0 1 0 0
 =
 xr
0
, p
−1
+(x
3
+x
2
+x)p
0
r
−1
+(x
3
+x
2
+x)r
0
, xp
0
 III. Z:
 1 1, 1 0 1 1 1
0 1, 0 1 0 0 0
 =
 r
0
, p
1
r
1
, p
0
 Z:
 1 1, 1 0 1 1 1
1, 0 1 0 0 0 0
 =
 r
0
, xp
1
xr
1
, p
0
  Konˇ cni obsegi v kriptografiji
Podroˇ cje konˇ cnih obsegov je polno raziskovalnih problemov, tako teore-
tiˇ cnih, kakor tudi tistih, ki so povezani z njihovo uporabo. Mnogo slednjih
izviraizkriptografijeinteorijekodiranja,kjerjearitmetikakonˇ cnihobsegov
velikokratbistvenegapomena. Valgoritmihpogostouporabljamorazˇ siritve
dvojiˇ skih obsegov ali praˇ stevilske obsege. Prednost prvih je v prilagodlji-
vosti dvojiˇ skemu zapisu v raˇ cunalnikih, prednost drugih pa v ˇ ze vgrajeni
aritmetiki v sodobnih procesorjih. Primeri kriptografskih shem, ki temeljijo
na konˇ cnih obsegih, so
• klasiˇ cni Diffie-Hellmanov protokol za dogovor o kljuˇ cu [2], [5],
• ElGamalove sheme za digitalni podpis [3] ter
174 Obzornik mat. fiz. 57 (2010) 5

i
i
“Tonejc(2)” — 2010/11/25 — 14:12 — page 175 — #19
i
i
i
i
i
i
Aritmetika dvojiških konˇ cnih obsegov
• kriptosistemi z javnimi kljuˇ ci, ki uporabljajo eliptiˇ cne krivulje [7].
Uˇ cinkovitost teh raˇ cunsko zahtevnih shem je odvisna od hitrosti izvajanja
aritmetiˇ cnih operacij, zahtevnost teh pa je odvisna od izbire baze. Idealno
bibilo,ˇ cebilahkovsakooperacijoopravilivtistibazi,vkaterijoznamonaj-
bolj uˇ cinkovito izvesti, saj bi potem lahko kombinirali najboljˇ se iz razliˇ cnih
svetov. V praksi je izbor baze odvisen od tega, katere operacije z elementi
najpogosteje izvajamo. V kriptografiji so najbolj uveljavljene polinomske in
normalne baze in videli smo, da imajo polinomske baze pomembno vlogoˇ ze
pri vpeljavi konˇ cnih obsegov. Njihova praktiˇ cna prednost se pokaˇ ze pred-
vsem v uˇ cinkovitem invertiranju, ki ga izvajamo z razˇ sirjenim Evklidovim
algoritmom. Normalnebazepasozanimivetakosstaliˇ sˇ camatematiˇ cneteo-
rije kot tudi zaradi praktiˇ cne uporabe, zato si zasluˇ zijo posebno obravnavo.
LITERATURA
[1] E. Berlekamp, Algebraic Coding Theory, Aegean Park Press; Revised edition, 1984.
[2] W. Diffie in M. E. Hellman, New directions in Cryptography, IEEE Transactions on
Information Theory IT-22, (1976) 6, str. 644–654.
[3] ElGamal, A public-key cryptosystem and signature scheme based on discrete logari-
thms, IEEE Transactions on Information Theory IT-21, (1985) 4, str. 469–472.
[4] D. Hankerson, A. Menezes in S. Vanstone, Guide to Elliptic Curve Cryptography,
Springer-Verlag, 2004.
[5] A. Juriˇ si´ c, Diffie-Hellmanov dogovor o kljuˇ cu, Presek 34, (2006/2007) 1, str. 25–30.
[6] A. Juriˇ si´ c, Raˇ cunala nove dobe, Presek 30, (2002/2003) 4 in 5, str. 226–231 in 290–
296 .
[7] N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation 48, (1987),
str. 203–209 .
[8] R. Lidl in H. Niederreiter, Encyclopedia of Mathematics and Its Applications: Finite
Fields, Cambridge University Press, 1987.
[9] A. J. Menezes, P. van Oorschot in S. Vanstone, Handbook of Applied Cryptography,
CRC Press, 1996.
[10] A. J. Menezes, I. F. Blake, S. Gao, R. C. Mullin, S. A. Vanstone in T. Yaghoobian,
Applications of Finite Fields, Kluwer Academic Publishers, 1993.
[11] G. Seroussi, Table of Low-Weight Binary Irreducible Polynomials, Hewlett-Packard
Laboratories Technical Report, HPL-98-135, 1998.
[12] I. Vidav, Algebra, DMFA–zaloˇ zniˇ stvo, 2003.
157–175 175