Koło Naukowe Matematyków U¦ PL SMS

Number theory and cryptography

Szczyrk, 23rd - 25th November 2012

The leading topic of the session is Number theory and cryptography. We will shortly upload some exemplary topics; for now we provide the following references (in Polish and English):

In Polish:

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

In English:

G.H. Hardy, E.M. Wright - Introduction to the Theory of Numbers
(A rather difficult book with a multitude of tangential lemmas),
H. Cohn - Advanced Number Theory (rather algebraic, standard),
R.K. Guy - Unsolved Problems in Number Theory (from the session viewpoint probably the most interesting - the title speaks for itself)
Song Y. Yan - "Number theory for computing" (not a very difficult or mathematical book, one can find many topics concerning applications of number theory in computer technology)

Below we list possible topics from number theory, computational number theory and cryptography, which may be of interest to you:

Number theory:

  • Distribution of prime numbers: approximating the $pi(X)$ function, Riemann zeta function, the prime number theorem,
  • Elliptic curves: elementary notions like operations on points and intuitions connected to it, or something more serious like the Taniyama-Shimura-Weil conjecture,
  • Diophantine equations: some examples and methods of solving them (e.g. Pell equations), Fermat's Last Theorem (along with its history, as it is very interesting), connection between FLT and Taniyama-Shimura-Weil hypothesis,
  • Waring problem, Goldbach conjecture, Waring-Goldbach problem,
  • Elementary tools of algebraic number theory: algebraic numbers, integer algebraic numbers, number fields,
  • Probabilistic number theory: Turan-Kubilius inequality, Erdos-Kac theorem.

    Computational number theory:

  • Simple number theoretic algorithms, e.g. modular raising to powers, group operations on elliptic curves etc.,
  • Primality tests: deterministic primality tests, Fermat test, the strong pseudoprimality test, Lucas test, tests using elliptic curves,
  • Factorisation of integers: the continued fraction method (CFRAC), QS, NFS, ECM method,
  • Computing discrete logarithms: Shanks method, Silver-Pohlig-Hellman algorithm, computing discrete logarithms on elliptic curves,
  • Quantum algorithms: quantum algorithms of integer factorisation (Shore scheme), quantum algorithms of computing discrete logarithms.

    Cryptography and applications of number theory in cryptography:

  • Cryptosystems with a private key (symmetric cryptography): AES, Twofish, Blowfish, Serpent, IDEA,
  • Cryptosystems with a public key (asymmetric cryptography): RSA, cryptosystems based on discrete logarithms (e.g. ElGamal), cryptosystems based on elliptic curves,
  • Mixing (hashing) functions,
  • Algorithms for generation of pseudorandom numbers,
  • Quantum cryptography: quantum key distribution, quantum commitment, security of quantum algorithms in the bounded magazine of data model and bounded magazine of data with noise,
  • Post-quantum cryptography (i.e. cryptosystems immune to attacks by methods of quantum cryptoanalysis): McEliece cryptosystem, cryptosystems based on lattices (Goldreich-Goldwasser-Haley cryptosystem, NTRUEncrypt), the Lamport signature method, the Merkle signature method.

    last update: 02.12.2012
  • Contact:

    Students' Mathematical Society of the University of Silesia
    (Koło Naukowe Matematyków Uniwersytetu ¦l±skiego)
    40-007 Katowice, ul. Bankowa 14 (room 524)
    tel. (032) 359-20-96, email: knm@knm.katowice.pl