IDC207: Number theory and cryptography

[Cr:2, Lc:2, Tt:0, Lb:0]

Course Outline

Number Theory : Diophantine equations, primes and their distribution, cryptography, divisibility, Euclidean algorithm, linear Diophantine equations, Fermat and Mersenne numbers, fundamental theorem of arithmetic, Pythagorean triples, differences of squares, prime factorization of factorials, Riemann-zeta function, congruences, Chinese remainder theorem, Fermats little theorem, Eulers theorem, Wilsons theorem.

Cryptographic applications : Shift and affine ciphers, secret sharing, RSA algorithm

Congruences : Polynomials mod primes, solutions modulo prime powers, composite moduli.

Primitive roots : Orders of elements, primitive roots, discrete log problem, existence of primitive roots, Diffie-Hellman key exchange, ElGamal public key cryptosystem, digital dignatures.

Quadratic reciprocity : Squares and square roots mod primes, Legendre symbol, quadratic reciprocity, applications to cryptography.

Recommended Reading

• James S. Kraft, Lawrence C. Washington An Introduction to Number Theory with Cryptography,Chapman and Hall/CRC.

• Neal Koblitz, A Course in Number Theory and Cryptography (Graduate Texts in Mathematics), Springer. ISBN-10: 0387942939 ISBN-13: 978-0387942933.

• V V Yaschenko, Cryptography: An Introduction, Student Mathematical Library, AMS, Universities Press India (2009).