discipline 
Pure
Mathematics

subject 
Computational Number Theory

lecturers 
András Sárközy 
credits 
2 
period 

curriculum 
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 Jacobisymbol, its basic properties, and its
application to compute the Legendresymbol. Cryptography. Cryptosystem, key.
Public key cryptography. Trapdoor and oneway functions. RSA. Discrete
logarithm. The DiffieHellman key exchange system. Primality testing,
probabilistic and deterministic tests. Pseudoprimes, primality tests using
Fermat’s congruence. 
literature 

form of tuition 
Lecture 
mode of assessment 
written/oral
exam 