83695 Str005 (3)

6 8pit Irefci

Rozdział 6. Krzywe eliptyczne....................206

6.1. Podstawowe pojęciu.............................. 20fi

6.2.    Systemy kryp t ogra fi cm c, w których używa się

krzywych eliptycznych ......................... 2jo

6..?. Test pierwszości, w którym używa się krzywych eliptycznych ....    229

6.4. Rozkład na czynniki za pomocą krzywych eliptycznych....... 234

Odpowiedzi do ćwiczeń...................... 244

Skorowidz

Wstęp

Zarówno Gauss, jak i inni matematycy mają rację, twierdząc, że istnieje tylko

Jedna nauka [teoria liczb J, która Jest tak odległa od zwyczajnej ludzkiej działalno-

icl, ze pozostanie czysta i nieskażona.

- G. H. Hardy, A Mathematician's Apology, 1940

G. H. Hardy byłby zaskoczony i prawdopodobnie zdegustowany rosnącym zainteresowaniem teorią liczb w takich obszarach ,zwyczajnej ludzkiej działalności”, jak przekazywanie informacji (kody korygujące błędy) i kryptografia (tajne szyfry). Mniej niż pół wieku po tym, jak Hardy napisał cytowane wyżej słowa, nie jest już nieprawdopodobne (choć jeszcze dotychczas się nie zdarzyło) to, że NSA (agencja rządowa Stanów Zjednoczonych zajmująca się m. in. kryptografią) zażąda wcześniejszego dostępu do teoretycznych prac badawczych z pewnych działów teorii liczb i prawa wydania zgody na ich publikację.

Po części ogromny wzrost mocy obliczeniowej komputerów miał wpływ na pewne problemy badane przez specjalistów od teorii liczb, dając początek nowej gałęzi tej teorii, nazywanej „obliczeniową teorią liczb”.

W tej książce nie zakładamy prawie żadnej uprzedniej znajomości algebry i teorii liczb. Jej celem jest wprowadzenie czytelnika w zagadnienia arytmetyczne, zarówno bardzo stare, jak i najnowsze, które znajdują się w centrum zainteresowań ze względu na swoje zastosowania, zwłaszcza w kryptografii. Z tego powodu przyjmujemy podejście algortymiczne, kładące nacisk na oszacowania efektywności metod wynikających z teorii. Szczególne miejsce w naszym wykładzie zajmują (w rozdziale 6) pewne najnowsze zastosowania teorii krzywych eliptycznych. Krzywe eliptyczne od pewnego czasu były jednym z ważniejszych pojęć wielu działów matematyki teoretycznej; teraz okazało się, że arytmetyka krzywych eliptycznych może mieć również duże znaczenie praktyczne.

W każdym rozdziale znajduje się wiele ćwiczeń, mających ułatwić studiującemu samodzielnie czytelnikowi głębokie zrozumienie poznawanych pojęć.

W pierwszych dwóch rozdziałach znajduje się wykład podstawowych pojęć wykorzystywanych dalej. Czytelnik, który nie wysłuchał dotychczas