Testowanie Pierwszości
elladdn.gif

Piotr Achinger, Maciej Zdanowicz

Liczby pierwsze stanowią jeden z najbardziej podstawowych obiektów matematycznych. Z tego względu są obiektem ciągłych, dokładnych badań. W szczególności problem efektywnych testowania pierwszości, interesuje zarówno matematyków jak i informatyków. Praktycy, zajmujący się np. kryptografią, opierają swoje rozwiązania (np. protokoły) o duże liczby pierwsze.

Problem PRIMES - sprawdzania pierwszości danej liczby $N$, ma bardzo długą historię i różnorodność rozwiązań. Najprostsze rozwiązanie - dzielenie przez wszystkie liczby mniejsze od od $\sqrt{N}$ - znane było już starożytnym (idea podobna jest do znanego sita Eratostenesa). Jednak złożoność tego algorytmu nie jest wielomianowa od długośći zapisu liczby, czyli $log_2{N}$. Na naszych zajęciach postaramy się wprowadzić uczestników w tajniki problemu i ostatecznie pokazać współczesne algorytm testowania pierwszości, wraz z optymalnym - wielomianowym - algorytmem AKS.

W ramach zajęć dokonamy przeglądu (z dowodami) najbardziej znanych algorytmów sprawdzania pierwszości (i powiązanych problemów np. z kryptografii). Skupimy się na aspektach teorioliczbowych zagadnienia, w szczególności pisanie programów pozostawimy chętnym.

Plan:

Dzień 1

  • powtórzenie potrzebnych faktów z teorii liczb,
  • proste fakty zahaczające o teorię grup i teorię ciał,
  • testy oparte na Małym Twierdzeniu Fermata,
  • test $\rho$ Pollarda

Dzień 2

  • algorytm AKS (Agrawal-Kayal-Saxena)

Dzień 3

  • testy pierwszości używające krzywych eliptycznych.

Zadania kwalifikacyjne. Jest 10 zadań i można za nie uzyskać łącznie 20 punktów. Próg przyjęcia na warsztaty to 12 punktów. Rozwiązania należy przysłać na jeden z adresów: piotr.achinger i m.zdanowicz na gmailu.

Bibliografia

1. M. Agrawal, N. Kayal, N. Saxena PRIMES is in P, Ann. Math. 160 (2004), http://annals.math.princeton.edu/2004/160-2/p12

2. N. Koblitz Teoria liczb i kryptografia, WNT

3. J. Silveman Arithmetic of Elliptic Curves, Springer

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License