5.2. Grupa E(F_q)

Primjer: Promotrimo eliptičku krivulju

E :     y² = x³ + x + 3

x([2] P) = 0 - 8 = 6,     y([2] P) = - 1 + 0 = 6,
x([3] P) = ((6 - 1)/(6 - 4))² - 4 - 6 = (5 4)² - 10 = 5,
y([3] P) = - 1 + (4 - 5)(6 - 1)/(6 - 4) = 0,
[4] P = (6,1),     [5] P = (4,6),     [6] P = .

Neka je E eliptička krivulja nad konačnim poljem . Postavlja se pitanje što se općenito može reći o grupi E(). Jasno je da za broj elementa na eliptičkoj krivulji vrijedi #E() 2q + 1. Naime, imamo jednu točku u beskonačnosti, a pored toga svakom od q mogućih x-eva odgovaraju najviše dva y-a. No, samo pola elemenata od imaju kvadratni korijen (to su točno oni elementi koju su oblika g²ⁿ, gdje je g generator grupe ^*), pa možemo očekivati da će broj #E() biti približno jednak q + 1. Ovo razmatranje je precizirano u sljedećem važnom teoremu.

Teorem: (Hasse) |q + 1 - #E()| 2 q

Veličina t definirana sa #E() = q + 1 - t naziva se Frobeniusov trag od E u q. Prema Hasseovom teoremu je |t| 2 q.

Za eliptičke krivulje nad tvrdnja Hasseovog teorema je najbolja moguća, u smislu da za svaki prirodan broj n iz intervala (p + 1 - 2 p, p + 1 + 2 p) postoji eliptička krivulja reda n. Štoviše, unutar manjeg intervala (p + 1 - p, p + 1 + p) redovi su gotovo uniformno distribuirani. Ova činjenica je jako važna za neke od primjena eliptičkih krivulja, kao što faktorizacija velikih prirodnih brojeva, te dokazivanje prostosti.

Napomenimo da računanje reda grupe E() za velike brojeve q nije sasvim jednostavan problem. Prvi polinomijalni algoritam za računanje #E() dao je Schoof 1995. godine. Broj operacija u tom algoritmu je bio O(log⁸q). Kasnije su Atkin i Elkies poboljšali Schoofov algoritam, tako da se danas broj #E() može efikasno izračunati za brojeve q s do 500 znamenaka.

Pretpostavimo sada da imamo eliptičku krivulju E zadanu nad . Bez smanjenja općinosti možemo pretpostaviti da su joj koeficijenti cjelobrojni. Stoga za svaki prosti broj p možemo promatrati ostatke tih koeficijenata pri djeljenju s p. Na taj način ćemo dobiti krivulju nad koja će biti eliptička ukoliko je nesingularna, a to će biti ukoliko p ne dijeli diskriminantu D od E. Podsjetimo se da je jedno od važnih pitanja vezanih uz eliptičke krivulje nad određivanje njihovog ranga. Jedna od najpoznatijih i najvažnijih slutnji u matematici jest Birch - Swinnerton-Dyerova slutnja koja povezuje rang eliptičke krivulje nad s brojem točaka na toj istoj krivulji kad se ona promatra nad konačnim poljem . Ugrubo rečeno, za eliptičku krivulju velikog ranga bi brojevi #E() trebali biti relativno veliki za mnogo prostih brojeva p. Preciznije, (#E() / p), gdje se produkt uzima po svim prostim brojevima p koji ne dijele diskriminantu, a manji su od realnog broja X, je proporcionalan sa (log X)^r, gdje je r upravo rang krivulje E. Još preciznija formulacija Birch - Swinnerton-Dyerove slutnje je preko tzv. L-funkcija, te kaže da je rang jednak redu nultočke jedne analitičke funkcije koja se definira pomoću brojeva #E().

Za razliku od slučaja eliptičkih krivulja nad , gdje je otvoreno pitanje koji su sve rangovi mogući, u slučaju polja poznato je da je pripadna grupa ili ciklička ili produkt dvije cikličke grupe. Preciznije, vrijedi

E() _d × _e,

U dosadašnjim razmatranjima, mi smo se uglavnom ograničili na eliptičke krivulje nad poljima karakteristike različite od 2 i 3. Međutim, kako su za primjene u kriptografiji od velike važnosti eliptičke krivulje nad konačnim poljima karakteristike jednake 2, sada ćemo reći nešto o njima.

Svaka eliptička krivulja nad poljem , gdje je q = 2^m, može se transformirati u jedan od sljedeća dva oblika y² + cy = x³ + ax + b ili y² + xy = x³ + ax² + b. Međutim, krivulje prvog oblika su tzv. supersingularne krivulje, koje nisu, iz razloga koje ćemo kasnije objasniti, od interesa kod primjene u kriptografiji. Stoga se možemo usredotočiti na krivulje drugog oblika. Pritom je b proizvoljan ne-nul element iz , dok za a imamo samo dvije bitno različite (koje daju neizomorfne krivulje) mogućnosti: a = 0 ili a = , gdje je neki fiksirani element iz sa svojstvom da je Tr() = + ² + ⁴ + ... + ² = 1. Ako je m neparan, onda možemo uzeti da je = 1.

Navedimo još formule za zbrajanje točaka na eliptičkoj krivulji zadanoj jednadžbom y² + xy = x³ + ax² + b nad poljem karakteristike 2. Ako je P = (x₁, y₁) i Q = (x₂, y₂), onda je

-P = (x₁, x₁ + y₁),
x(P + Q) = ((y₂ + y₁) / (x₂ + x₁))² + (y₂ + y₁) / (x₂ + x₁) + a + x₁ + x₂,
y(P + Q) = y₁ + x(P + Q) + (x₁ + x(P + Q)) (y₂ + y₁) / (x₂ + x₁),

x([2]P) = ((x₁² + y₁) / (x₁))² + (x₁² + y₁) / (x₁) + a,
y([2]P) = y₁ + x([2]P) + (x₁ + x([2]P)) (x₁² + y₁) / (x₁).

Zadatci:

1. Neka je eliptička krivulja E zadana jednadžbom y² = x³ - x. Odredite #E() za q = 3, 5, 7, 9, 11.

2. Prema Hasseovom teoremu, red grupe eliptičke krivulje nad poljem ₅ je jedan od brojeva n = 2, 3, ... , 10. Za svaki od mogućih n-ova, pronađite jednu eliptičku krivulju nad ₅ čiji je red upravo jednak n.