☞ **((algorithms РУССКАЯ ВЕРСИЯ))** ==Constructive Algebra: Algorithms for Information Processing== Faculty of Applied Mathematics & Control Processes, St.Petersburg State University Lecturer: ((http://www.apmath.spbu.ru/en/staff/uteshev/ Prof. Alexei Uteshev)) ~~TOC~~ The course is supported by ((http://www.digdes.com/ {{ :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. ((:detse:resultante 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.