COMPUTER ALGEBRA
Academic year and teacher
If you can't find the course description that you're looking for in the above list,
please see the following instructions >>
- Versione italiana
- Academic year
- 2017/2018
- Teacher
- FABIO STUMBO
- Credits
- 6
- Didactic period
- Primo Semestre
- SSD
- MAT/02
Training objectives
- The goal of the course is to deepen theoretical aspects which are the basis of some important algebraic algorithms commonly used in applications with particular reference to Cryptography and Coding Theory.
Main acquired knowledges are:
* Structure of finite fields;
* Meaning of computational complexity of an algorithm;
* Basic property of symmetric and asymmetric ciphers;
* Factorization algorithms for numbers and polynomials;
* Primality test for integers;
* Coding algorithms and error correction for message transmission.
Main acquired skills are:
* Knowing how to calculate the computational complexity of an algorithm;
* Knowing how to encrypt messages using the studied ciphers;
* Recognize the primality of an integer;
* Factor a whole number;
* Knowing how to factor polynomials with coefficients in the ring of integers or in a finite field;
* Knowing how to encode and decode a message and ability to recognize and correct errors occurred during transmission according to the studied algorithms. Prerequisites
- Elementary algebra knowledge as acquired in a first year undergraduate Algebra course. In particular:
* Notions about groups, rings and fields;
* Structure of finite fields;
* Calculation of the GCD and the Euclidean algorithm. Course programme
- The course forecasts 48 hours of standard lessons with both theory and exercises, approximately shared in the following way:
1. Algebraic prerequisites (12 hours):
* Euclidean algorithm
* Euler-Fermat Theorem.
* Congruences.
* Finite fields.
* Primitive elements.
* Roots of unity and cyclotomic classes
* Computational complexity.
2. Cryptography (6 hours):
* Permutations and substitutions.
* Substitution algorithms.
* Transposition algorithms.
* Hill's algorithm.
* Symmetric algorithms: DES and AES.
* Public key algorithms: RSA cipher, ElGamal cipher
* Hash functions: SHA-1.
* Digital signature: DSA.
3. Factorization of integer numbers (4 hours):
* Sieves.
* Factoring algorithms: Pollard (p-1), Pollard Rho.
* Primality tests: Miller-Rabin algorithm, AKS algorithm.
4. Factorization of polynomials (4 hours):
* Berlekamp's algorithm.
* Hensel Lemma.
* Factorization in Q[x].
5. Error correcting codes (22 hours):
* Hamming's distance.
* Bounds: Hamming, Singleton e Gilbert-Varshamov.
* Linear odes, Hamming codes.
* Cyclic codes, BCH codes and Reed-Solomon codes.
* Coding and decoding.
* Syndrome decoding, Slepian decoding.
* Meggitt decoding in cyclic codes.
* Decoding algorithms in BCH codes: PGZ, Forney, Sugyiama, Berlekamp-Massey. Didactic methods
- The course is organized in conventional lectures, usually 2 hours each.
Learning assessment procedures
- Examination test consists in verifying the achievement of expected skills.
This verification is through a written test lasting
3 hours and consisting in exercises related to the topics of the course lectures.
The written test consists of questions and/or exercises with
variable score for a total of not less than 30.
The total number of points obtained in the test (limited to 30 if greater) is
the student's grade.
The examination is passed if the grade is at least 18.
Oral session is optional, at student's request.
Any oral session contributes to the final mark with a score
between -3 and 3. Reference texts
- 1) Fabio Stumbo, Computer Algebra, Ed. Aracne
2) Fabio Stumbo, Teoria dei Codici
