Pure Mathematics


Computational Number Theory


András Sárközy






Representation in number system base b. Bit operation. Time complexity of the basic operations and of some elementary problems. The sieve of Eratosthenes for determining the primality of n. The computation of the greatest common divisor. Congruences. Time complexity of computing the multiplicative inverse and solving linear congruences. In case of , determining p and q is polynomially equivalent to determining. Modular exponentiation. Factorization via algebraic identities. Finite fields. The Jacobi-symbol, its basic properties, and its application to compute the Legendre-symbol. Cryptography. Cryptosystem, key. Public key cryptography. Trapdoor and one-way functions. RSA. Discrete logarithm. The Diffie-Hellman key exchange system. Primality testing, probabilistic and deterministic tests. Pseudoprimes, primality tests using Fermat’s congruence. Carmichael numbers. Euler pseudoprimes. The Solovay-Strassen and Miller-Rabin primality tests. The polynomial time AKS primality test. Factorization. The factor base algorithm. The quadratic sieve.         Elliptic curves, operation among its points. Elliptic curves over finite fields. The analogue of the Diffie-Hellman key exchange. Pseudorandom 0-1 sequences and their applications. The linear congruence method. The Vernam crypto-algorithm. Random and pseudorandom bit generator. Two constructions for pseudorandom sequences.



form of tuition


mode of assessment

written/oral exam