5. Eliptičke krivulje nad konačnim poljima

5.1. Konačna polja

Konačno polje s q elemenata označava se s . Neka je p karakteristika polja . Tada sadrži prosto polje = , i stoga je vektorski prostor nad . Dimenziju od kao vektorskog prostora nad označimo s k. Tada ima p^k elemenata, tj. q = p^k. Nadalje, za svaku potenciju prostog broja q = p^k postoji jedinstveno (do na izomorfizam) polje s q elemenata. Jedna od realizacija tog polja je [x] / (f(x)), gdje je f(x) neki ireducubilni polinom stupnja k nad . Elementi ovog polja su polinomi nad stupnja manjeg ili jednakog k - 1 (očito je da takvih polinoma ima točno p^k), dok su operacije zbrajanje i množenje polinoma u [x], s time da se nakon množenja računa ostatak pri djeljenju s polinomom f(x).

Primjer: Konstrukcija polja ₉.
Polinom f(x) = x² + 1 je ireducibilan nad ₃ jer nema korijena u ₃. Stoga ₉ možemo reprezentirati kao ₃[x] / (f(x)). Dakle, elementi od ₉ su 0, 1, 2, x, x + 1, x + 2, 2x, 2x + 1, 2x + 2. Izračunajmo, na primjer, (x + 1)² u polju ₉. Imamo: (x + 1)² = x² + 2x + 1 = 2x.

Označimo s ^* multiplikativnu grupu polja . Tada je grupa ^* ciklička, što znači da postoji element g takav da se svaki element iz ^* može dobiti kao neka potencija od g.

Za primjene u kriptografiji, posebno za primjene eliptičkih krivulja u kriptografiji, najvažniji su slučajevi kad je q = p prost broj, te kad je q = 2^m potencija broja 2. Kako smo već rekli, polje ₂ jest vektorski prostor nad ₂ dimenzije m. Postoji mnogo različitih baza tog vektorskog prostora. Mi ćemo spomeniti dva tipa takvih baza: trinomijalne baze i normalne baze.

Ako je f(x) ireducibilni polinom stupnja m nad ₂, tada se polje ₂ može reprezentirati kao skup svih polinoma nad ₂ stupnja manjeg od m, s operacijama modulo f(x). To se zove reprezentacija pomoću polinomijalne baze. Reprezentacija pomoću trinomijalne baze je specijalni slučaj reprezentacije pomoću polinomijalne baze u kojem polinom f(x) ima oblik f(x) = x^m + x^k + 1. Prednost takve reprezentacije jest efikasnost provođenja redukcije modulo f(x). Za neke m-ove (npr. za m 0 (mod 8)), trinomijalna baza ne postoji. Eksperimentalno je pokazano da trinomijalna baza postoji za nešto više od pola m-ova manjih od 1000.

Normalna baza od ₂ nad ₂ je baza oblika

{b, b², b², ... , b²},

Zadatci:

1. Dokažite da je polinom f(x) = x³ + x + 1 ireducibilan nad ₂. Napravite tablice zbrajanja i množenja za 8 elemenata polja ₈ reprezentiranog kao ₂[x] / (f(x)).

2. Neka je f(x) = x^m + x^k + 1, te neka je a(x) = a₀ + a₁x + a₂x² + ... + a_{2m -2}x^{2m -2} ₂[x]. Uvjerite se da sljedeći algoritam računa ostatak pri dijeljenju polinoma a(x) s polinomom f(x):

   For   i = 2m - 2   to   m   by   -1   do
           a_{i - m} = a_{i - m} + a_i
           a_{i - m + k} = a_{i - m + k} + a_i.