Construction of rational points on elliptic curves over finite fields

Praca składa się z czterech rozdziałów zatytułowanych odpowiednio: Preliminaria, Krzywe eliptyczne, Konstrukcja punktów wymiernych oraz Zastosowanie konstrukcji punktów wymiernych.W pierwszym rozdziale poza wstępnymi definicjami i twierdzeniami, zaprezentowana jest deterministyczna adaptacja algorytmu Tonelliego-Shanksa wyznaczania pierwiastków kwadratowych w ciałach skończonych. Następnie, metoda ta jest wykorzystana do przedstawienia deterministycznego algorytmu rozwiązywania równań kwadratowych (od dwóch zmiennych) w ciałach skończonych.W drugim rozdziale zaprezentowane są ogólne informacje na temat krzywych eliptycznych. W szczególności przedstawione jest wraz z dowodem twierdzenie Nagella-Lutz oraz twierdzenie Hassego o mocy grupy punktów krzywej eliptycznej nad ciałem skończonym. Dodatkowo sformułowane zostało twierdzenie Mazura o postaci grupy torsyjnej krzywej eliptycznej nad ciałem liczb wymiernych oraz twierdzenie Mordella-Weila o skończonej generowalności grupy punktów K-wymiernych, gdzie K jest ustalonym ciałem liczbowym.W kolejnym rozdziale zaprezentowane są metody konstrukcji punktów wymiernych dla krzywych eliptycznych nad ciałami skończonymi. Metody te różnią się w zależności od ciała nad którym jest zdefiniowana krzywa.Ostatni, czwarty rozdział, rozpoczyna się od skonstruowania algorytmów, będących konsekwencjami twierdzeń z trzeciego rozdziału. W szczególności przedstawione jest oszacowanie na liczbę punków wymiernych jaką można uzyskać przy pomocy tych algorytmów. Na końcu pracy opisany jest protokół Diffiego-Hellmana uzgadniania klucza prywatnego z wykorzystaniem tych algorytmów.

Work consists of four chapters: Preliminaries, Elliptic curves, Construction of rational points and Application of rational points construction.In the first chapter besides basic definitions and theorems, there is shown deterministic adaptation of Tonelli-Shanks algorithm for calculating square roots in finite fields. Afterwards, this algorithm will be used to express deterministic algorithm for solving quadratics in finite fields.In the second chapter there are presented general information about elliptic curves. In particular there are Nagell-Lutz and Hasse theorem with proofs and additionally theorem of Mazur and theorem of Mordell-Wiel without proofs.In the next chapter there are shown methods for constructions of rational points of elliptic curves over finite fields. It is presented depending on characteristic of finite field over which elliptic curve is defined.Last chapter constistc of algorithms of construction of rational points on elliptic curves over finite fields, as a consequence of theorem from third chapter. At the end there is presented Diffie-Hellman protocol of private key agreement with use of this algorithms.