Оглавление

Faculty of Applied Mathematics & Control Processes, St.Petersburg State University

Lecturer: Prof. Alexei Uteshev

The course is supported by

Shannon information theory. Entropy, information, redundancy. Data compression. Prefix-free coding: Huffman and Shannon-Fano. LZW-algorithm. Error correcting coding.

**Introduction to number theory.** The greatest common divisor (GCD). Euclidean algorithm; Lamé's theorem. Linear representation for GCD, the continuant. Divisibility. Relatively prime numbers. Prime numbers. Factorization; Fermat's method. Euler's totient function.

**Modular arithmetic.** Congruences. Computation of — square-and-multiply algorithm. Theorems by Fermat and Euler. Linear congruence solving, modular inverse. Chinese remainder theorem.

**Index** (discrete logarithm). Primitive root modulo . Solving the congruence .

**Complex numbers.** Roots of unity. Primitive roots of unity.

**Univariate polynomial.** Horner's process. Polynomial multiplication: classical and fast algorithms. Reducibility and irreducibility of a polynomial over . Cyclotomic polynomials.

**Interpolation.** Vandermonde's matrix. Lagrange form. Rational interpolation. Trigonometric interpolation.

Resultant. Sylvester's and Bézout's determinantal representation. Bézout's identity for polynomials. Tschirnhaus transformation.

**History of cryptography**. Cæsar's, Cardano's, Vigenère's and scytale's ciphers.

**Public key encription.** One-way function. Trapdoor function. RSA algorithm. ElGamal algorithm.

**Primality testing algorithms.** Probable prime numbers. Weak probable primes, Carmichael numbers. Miller-Rabin algorithm.

**Cryptanalysis.** Factorization; Pollard's algorithms. Low public exponent attack.

**Authentication.** Cryptography hash function. Birthday (paradox) attack. Digital signature.

**Foundations.** Infinite fields. Finite fields, representation of an element: vector, polynomial and matrix form.

**Multiplication and inversion.** Generalized Fermat's theorem. Order of an element, primitive element. Computation of the element inversion.

**Polynomials over** . Expansion of . Irreducible and primitive polynomials. Polynomials over .

**Error correcting codes.** Hamming distance. Hadamard code. Linear code. Generator and parity check matrices. Hamming code.

**Cyclic code.** Systematic and non-systematic coding. Convolution.

**BCH code.** Reed–Solomon code. Data recovery in RAID-6.

**Discrete Fourier transform.** Algebraic vs. trigonometric interpolation.

**Fast Fourier transform** (FFT).

**Number theoretic transform**(NTT). The Schönhage–Strassen algorithm.

**Applications of FFT and NTT.** Multiplication of polynomials and integers. Circular convolution.

**Blahut R.E.** *Fast Algorithms for Digital Signal Processing.* 1985. Addison-Wesley Press.

**Lidl R., Niederreiter H.** *Finite Fields.* (2nd ed.) 1997. Cambridge University Press.

**Menezes A. J., van Oorschot P.C., Vanstone S.A.** *Handbook of Applied Cryptography.* (5th ed.) 2001. CRC Press

**Oppenheim A.V., Schafer R. W., Buck J.R.** *Discrete-time signal processing.* 1999. Prentice Hall.

**Peterson W.W., Weldon E.J.** *Error-Correcting Codes.* 1972. MIT press.

**Salomon D.** *A Guide to Data Compression Methods.* 2002. Springer.