Инструменты сайта


РУССКАЯ ВЕРСИЯ

Constructive Algebra: Algorithms for Information Processing

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

Lecturer: Prof. Alexei Uteshev

The course is supported by

dd1.jpg

Overview

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

Algebraic preliminaries

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 $ A^B \pmod{M} $ — square-and-multiply algorithm. Theorems by Fermat and Euler. Linear congruence solving, modular inverse. Chinese remainder theorem.

Index (discrete logarithm). Primitive root modulo $ M_{} $. Solving the congruence $ x^n \equiv B \pmod{M} $.

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 $ \mathbb Q_{} $. 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.

Cryptography

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.

Galois fields

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 $ \mathbf{GF}(2) $. Expansion of $ x^{2^{n}} - x $. Irreducible and primitive polynomials. Polynomials over $ \mathbf{GF}(2^n) $.

Coding

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.

Fast Fourier transform

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.

References

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.

algorithms_e.txt · Последние изменения: 2020/06/18 20:31 — au