Koło Naukowe Matematyków UŚ ENG KNM
O NAS DLA LICEALISTOW FORUM

XXXIII sesja KNM
Teoria liczb i kryptografia

Szczyrk, 23 - 25 listopada 2012

Tematem sesji jest Teoria liczb i kryptografia. Proponowane przykładowe tematy pojawią się niebawem; na razie proponujemy wybrane pozycje z bibliografii polsko- i anglojęzycznej:

Z książek w języku polskim:

A. Czogała, M. Szyjewski - Teoria liczb (wraz z kryptografią),
W. Sierpiński - Arytmetyka teoretyczna (bardziej algebraiczno-teoriomnogościowa),
W. Sierpiński - Teoria liczb,
W. Narkiewicz - Teoria liczb

Z anglojęzycznych:

G.H. Hardy, E.M. Wright - Introduction to the Theory of Numbers
(książka dosyć... harda :), dużo pobocznych lematów i lemacików),
H. Cohn - Advanced Number Theory (raczej algebraicznie, standardowo),
R.K. Guy - Unsolved Problems in Number Theory (pod kątem sesji to jest chyba najciekawsza pozycja, tytuł mówi sam za siebie)
Song Y. Yan - "Teoria liczb w informatyce" (w języku angielskim: "Number theory for computing"; nie jest to bardzo trudna i matematyczna książka, ale można w niej znaleźć wiele tematów dotyczących zastosowań teorii liczb w informatyce)

Poniżej przedstawiamy listę zagadnień z teorii liczb, obliczeniowej teorii liczb oraz kryptografii i zastosowań teorii liczb w kryptografii, które mogą Was zainteresować:

Z teorii liczb:

  • rozmieszczenie liczb pierwszych: przybliżanie funkcji $pi(X)$, dzeta Riemanna, twierdzenie o liczbach pierwszych,
  • krzywe eliptyczne: podstawowe pojęcia takie jak działania na punktach krzywych eliptycznych i intuicje z nimi związane, lub coś grubszego jak hipoteza Taniyamy-Shimury-Weila,
  • równania diofantyczne: jakieś przykłady równań i metody ich rozwiązywania (np. równania Pella), wielkie twierdzenie Fermata (tutaj ktoś mógłby opowiedzieć historię prób dowiedzenia tego twierdzenia, bo to bardzo ciekawa historia), związek WTF z hipotezą Taniyamy-Shimury-Weila,
  • problem Waringa, hipoteza Goldbacha, problem Waringa-Goldbacha,
  • podstawowe narzędzia algebraicznej teorii liczb: liczby algebraiczne, całkowite liczby algebraiczne, ciała liczbowe,
  • probabilistyczna teoria liczb: nierówność Turana-Kubiliusa, twierdzenie Erdosa-Kaca.

    Z obliczeniowej teorii liczb:

  • proste algorytmy teorioliczbowe: np. szybkie potęgowanie modularne, szybkie operacje grupowe na krzywych eliptycznych etc.,
  • testy pierwszości: deterministyczne testy pierwszości, test Fermata, test silnej pseudopierwszości, test Lucasa, test z wykorzystaniem krzywych eliptycznych,
  • rozkład na czynniki liczb całkowitych: metoda ułamków łańcuchowych (CFRAC), metoda QS i NFS, metoda ECM,
  • obliczanie logarytmów dyskretnych: metoda Shanksa, algorytm Silvera-Pohliga-Hellmana, obliczanie logarytmów dyskretynych na krzywych eliptycznych,
  • algorytmy kwantowe: kwantowe algorytmy faktoryzacji liczb całkowitych (np. schemat Shore'a), kwantowe algorytmy obliczania logarytmów dyskretnych.

    Z kryptografii i zastosowań teorii liczb w kryptografii:

  • kryptosystemy z kluczem prywatnym (kryptografia symetryczna): AES, Twofish, Blowfish, Serpent, IDEA,
  • kryptosystemy z kluczem publicznym (kryptografia asymetryczna): RSA, kryptosystemy oparte na logarytmach dyskretnych (np. ElGamal), kryptosystemy oparte na krzywych eliptycznych,
  • funkcje mieszające (hashujące),
  • algorytmy generowania liczb pseudolosowych,
  • kryptografia kwantowa: kwantowa dystrybucja klucza, kwantowe zobowiązania (quantum commitment), bezpieczeństwo algorytmów kwantowych w modelu ograniczonego magazynu danych oraz ograniczonego magazynu danych z szumem,
  • post-kwantowa kryptografia (czyli o kryptosystemach odpornych na ataki przy pomocy kryptoanalizy kwantowej): kryptosystem McEliece, kryptosystemy oparte na kratach (kryptosystem Goldreicha-Goldwassera-Halevi'ego, NTRUEncrypt), metoda podpisu Lamporta, metoda podpisu Merkle'a.

    ostatnia aktualizacja: 02.12.2012
  • Kontakt:

    Koło Naukowe Matematyków Uniwersytetu Śląskiego
    40-007 Katowice, ul. Bankowa 14 (pokój 524)
    tel. (032) 359-20-96, e-mail: knm@knm.katowice.pl