Instructor: Dr . János PINTZ
Text: N. Koblitz: A course in number theory and cryptography,
Springer Verlag, Chapters III--VI. Some topics can also be found in I.
Niven, H. S. Zuckerman, H. L. Montgomery: An introduction to the theory
of numbers, John Wiley & Sons, especially Chapters: 2.4, 2.5, 3.1,
3.2, 3.3, 2.9, 5.6, 5.7, 5.8.
This latter book is also used as a general reference for elementary
number theory.
Prerequisite: Beyond general mathematical experience, a course on elementary number theory covering the basic properties of divisibility and congruences, and the very basic concepts of algebra and probability (in beginners level) are assumed.
Course description: While cryptography in the past ment
secret codes for information exchange exclusively for military purposes,
today it is a necessity for any type of information exchange, such as safe
bank transactions or even private telecommunications. We will discuss some
classical and some modern cryptosystems connected to number theory. Computational
number theory is situated on the border of pure and applied mathematics.
The question whether a ''large'' integer is
a prime challanges mathematicians in any time. Cryptography can use
''large'' primes, while breaking the code needs to factorize ''large''
composite numbers. These problems are all studied during the course. We
will discuss how to calculate certain numbers (solutions) in an effective
way without practically calculating them, we will not use computers,
no such type of experience is needed. However a pocket programmable calculator
or access to a computer can help a lot in homeworks.
Topics:
Greatest common divisor, Euclidean algorithm, linear congruences, exponentials.
Simple linear cryptosystems.
The RSA cryptosystem, discrete logarithm--based cryptosystems.
The pseudoprime test, other primality testing.
Simple factoring methods, Pollard's $\rho$--method.
The basic quadratic sieve factoring method, variations.
if time allows: Elliptic curve cryptosystems, primality
test and factorization.