50325 Str120

236    6, Krzywe eliptyczne

dzielnikiem pierwszym liczby //. Założymy, że p > 3. Dla dowolnej liczby całkowitej m i dowolnych dwóch liczb wymiernych v, i x_2> których mianowniki są względnie pierwsze z ni, piszemy x_{ ~ x₂ (mod ni), jeśli różnica x_i — x₂, zapisana w postaci ułamka nicskracalncgo, ma licznik podzielny przez m. Dla dowolnej liczby wymiernej a,, której mianownik jest względnie pierwszy z m, istnieje dokładnie jedna liczba całkowita x₂ (nazywana „resztą z dzielenia"), zawarta w przedziale od 0 do m — 1, taka że x_{ = x₂ (mod m). Czasami tę resztę z. dzielenia będziemy oznaczać symbolem *| mod m.

Przypuśćmy, że mamy dane równanie postaci y² = x³ + ax + b, gdzie a, /Je Z. oraz. mamy punkt P = (jr, y), którego współrzędne spełniają to równanie. W praktyce krzywa E i punkt P na niej będą generowane w pewien „losowy” sposób, na przykład wybierzemy trzy losowe liczby a, x i y, a następnie obliczymy b -y² - x³ — ax. Założymy, że wielomian trzeciego stopnia ma różne pierwiastki, tzn. 4a³ + 27b² 0; prawie na pewno tak będzie, jeśli współczynniki zostaną wybrane w opisany losowy sposób. Dla uproszczenia założymy też dalej, że liczba 4a³ + 27 6² nie ma wspólnych dzielników z n\ inaczej mówiąc, wielomian x² + ax + b nie ma pierwiastków wielokrotnych modulo p dla dowolnego dzielnika pierwszego p liczby n. W praktyce możemy to sprawdzić po wybraniu a i b, obliczając NWD(4a³ + 27ó², n). Jeśli ten największy wspólny dzielnik jest większy od jedności, to albo n|4a³ + 27ó² (i wtedy musimy wybrać inne a i b), albo otrzymamy nietrywialny dzielnik liczby n (co było naszym celem). Możemy zatem założyć, że NWD(4a³ + 27ó², n) = l.

Przypuśćmy teraz, że chcemy znaleźć wielokrotność kP za pomocą metody iterowanego podwajania, opisanej w podrozdziale 6.2. Można to zrobić w 0(logk) krokach, przy czym każdy taki krok polega na podwojeniu punktu lub dodaniu dwóch różnych punktów. Można to zrobić na wiele sposobów. Można na przykład przedstawić liczbę k w postaci jej rozwinięcia dwójkowego a₀ + Aj • 2 + ... + fl_m_ j • 2^m" \ a następnie podwajać punkt P, dodając 2^JP do sumy częściowej, gdy tylko odpowiadający bit aj jest równy 1. Inaczej, można rozłożyć k na czynniki pierwsze l_j} a następnie obliczać kolejno l_y (P), /₂ft(P)) itd., gdzie /_lf /₂, ... są liczbami pierwszymi występującymi w rozkładzie (np. w kolejności niemalęjącej). Wtedy każda wielokrotność IjPj, gdzie Pj = lj_ j lj_ ₂... /jP, jest obliczana metodą iterowanego podwajania, po przedstawieniu każdej liczby pierwszej lj w postaci rozwinięcia dwójkowego.

Przyjmiemy, że została wybrana jakaś tego typu metoda obliczania wielokrotności kP.

Będziemy zajmować się wszystkimi wielokrotnościami punktu P modulo n. Oznacza to, że definiujemy P mod n = (x mod n, y mod n) i za każdym razem, gdy wyznaczamy jakąś wielokrotność kP, naprawdę obliczamy tylko reszty z dzielenia współrzędnych przez n. Abyśmy jednak mogli wykonywać działania modulo n, podwajanie punktu lub dodawanie dwóch różnych punktów, musi być spełniony pewien nietrywialny warunek. Mianowicie wszystkie mianowniki muszą być względnie pierwsze z n.

Twierdzenie 6.4.1. Niech E będzie krzywą eliptyczną opisaną równaniem y¹ = x³ + ax -\- b, gdzie a, be'Z oraz NWDióa³ -f 276², n) = 1. A/fec/i P_t i P₂ będą dwoma punktami na krzywej E, których współrzędne mają mianowniki względnie pierwsze z n oraz niech P, ź -P₂ Wtedy punkt P, + P₂eE ma współrzędne, których mianowniki są względnie pierwsze z n wtedy i tylko wtedy, gdy nie istnieje liczba pierwsza p\n o następującej własności: suma punktów p, mod p i P₂ mod p na krzywej E mod p jest punktem w nieskończoności O mod peE mod p. E mod p oznacza tu krzywą eliptyczną nad ciałem F_p otrzymaną przez zredukowanie modulo p współczynników równania y¹ = jc³ + | ax + b.

Dowód. Załóżmy najpierw, że wszystkie współrzędne punktów P_x = (#„ y_x), P₂ = (jc₂, y₂) oraz P_x+ P₂eEmają mianowniki względnie pierwsze z n. Niech p będzie dowolnym dzielnikiem pierwszym liczby n. Musimy pokazać, że P_x mod p + P₂ mod p ź O mod p. Jeśli x_x $x₂ (mod p), to z definicji dodawania punktów na krzywej E mod p natychmiast wnioskujemy, że punkt ?! mod p + P₂ mod p nie może być punktem w nieskończoności na krzywej E mod p. Przypuśćmy teraz, żex_l = x₂ (mod p). Po pierwsze, jeśli P_x - P₂, to współrzędne punktu P_x + P₂ = 2 P_x są dane wzorem (5) z podrozdziału 6.1, a współrzędne punktu 2P_X mod p można obliczyć według tego samego wzoru, z tym tylko, że każdą liczbę zastępujemy jej resztą z dzielenia przez p. Musimy pokazać, że mianownik 2y_x nie jest podzielny przez p. Gdyby był podzielny przez p, to ponieważ mianownik współrzędnej x punktu 2P_x nie dzieli się przez p, licznik 3 xf + a musiałby dzielić się przez p. Ale to oznaczałoby, że x_x jest pierwiastkiem modulo p wielomianu x³ + ax + b i jego pochodnej, co przeczy założeniu, że ten wielomian nic ma pierwiastków wielokrotnych modulo p. Przypuśćmy teraz, że P_x ± P₂. Ponieważ x₂ = x_x (mod p) oraz x₂ ± x_x, więc możemy przedstawić x₂ w postaci x₂ = x_x + p^rx, gdzie liczba r ^ 1 jest dobrana tak, by ani licznik, ani mianownik x nie były podzielne przez p. Ponieważ założyliśmy, że współrzędne punktu P_x + P₂ mają mianowniki niepodzielne przez p, możemy skorzystać ze wzoru (4) z podrozdziału 6.1, by stwierdzić, że y₂ jest postaci y_x + p^ry. Natomiast

y\ = (*i + p^rx)² + a(x_x + p^rx) + b =

= x³ + ax_x + b + p^Tx(3x% + a) = y_x+ p^Tx(3x\ + a) (mod p^r+1).    (!)

Ale ponieważ x₂ = x_x (mod p) i y₂ = y_x (mod p), więc P_x mod p = P₂ mod p. Zatem suma P_x mod p + P₂ mod p-2P_x mod p jest punktem w nieskończoności O mod p wtedy i tylko wtedy, gdy y_x = y₂ s 0 (mod p). Gdyby jednak ta ostatnia kongruencja była prawdziwa, to liczba y₂ — y\ = = (y₂ - y_x)(y₂ + y_x) byłaby podzielna przez p^r+1 (tzn. jej licznik byłby podzielny), a więc z kongruencji (1) wynikałoby, że 3x? + a = 0 (mod p). To jednak jest niemożliwe, bowiem wielomian x³ + ax + b nie ma pierwiastków wielokrotnych modulo p, a więc .v, nie może być zarówno pierwiastkiem tego