# 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

## 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.

2016/10/16 00:05 редактировал au 