# Course syllabus B-RAL - Fast algorithms (FEEIT - SS 2019/2020)

**Information sheet**ECTS Syllabus

Slovak

**English**

University: | Slovak University of Technology in Bratislava | ||||||||||||

Faculty: | |||||||||||||

Course unit code: | B-RAL | ||||||||||||

Course unit title: | Fast algorithms | ||||||||||||

Mode of delivery, planned learning activities and teaching methods: | |||||||||||||

| |||||||||||||

Credits allocated: | 6 | ||||||||||||

Recommended semester/trimester: | Applied Informatics - bachelor (semi-compulsory), 6. semester | ||||||||||||

Level of study: | 1. | ||||||||||||

Prerequisites for registration: | none | ||||||||||||

Assesment methods: | |||||||||||||

Students make one task concerning computations in finite field and will demonstrate functionality of the task via programm with the interface which enables to test the proposed solution. Maximum value of the task is 30 points, one written examination during the semester is the next 30 points and the value of the final examination is 40 points. | |||||||||||||

Learning outcomes of the course unit: | |||||||||||||

The goal is to obtain basic knowledge from the theory of algebraic structures, esspecially theory of finite fields and sequences over finite fields. Further knowledge concerning effectiva and fast computations over finite fields. Student will obtain knowledge concerning mathematical procedures and programing techniques used in various crypto apllications. Student after absolving the lectures will understand construction of algorithms in core of various applications for transmission and storage of protected information. | |||||||||||||

Course contents: | |||||||||||||

1. Basic notions. Algorithm of Eclide + effective algorithm for finding GCD, extended algorithm of Euclide.
2. Basic algebraic structures - groups, rings, fields, polynomials, extensions of fields, splitting fields, cyclotomic polynomials. 3. Finite fields, structure and representations, norm, trace. 4. Construction of irrecducible and primitive polynomials. 5.Polynomial factorization, Belrkamp's algorithm. 6. Linear recurring sequences, solutions representation, LFSRs, Berlekamp-Massey's algorithm. 7. Solving of equations over finite field, effective computation in finite fields, Chinese reminder theorem. 8. Effective methods of arithmetics, Montgomery arithmetics, Karacuba multiplication, Cook multiplication. 9. Discrete Fourier transform and its applications, convolutions, Winograd algorithm. 10. Elliptic curves, computations. 11. NTL library, software packages for computations. 12. Lattices, LLL algorithm, applications. 13. Large linear systems, Block Lanczos and Wiedeman algorithm. | |||||||||||||

Recommended or required reading: | |||||||||||||

| |||||||||||||

Language of instruction: | slovak or english | ||||||||||||

Notes: | |||||||||||||

Courses evaluation: | |||||||||||||

Assessed students in total: 268
| |||||||||||||

Name of lecturer(s): | RNDr. Karla Čipková, PhD. (examiner, instructor, lecturer, tutor) - slovak, english doc. RNDr. Karol Nemoga, CSc. (lecturer, person responsible for course) - slovak, english | ||||||||||||

Last modification: | 6. 5. 2019 | ||||||||||||

Supervisor: | doc. RNDr. Karol Nemoga, CSc. and programme supervisor |

*Last modification made by RNDr. Marian Puškár on 05/06/2019.*