Aug 10, 2020   1:07 a.m. Vavrinec
Academic information system

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

     Information sheet          ECTS          Syllabus          

     Slovak          English          

Slovak University of Technology in Bratislava
Course unit code:
Course unit title:
Fast algorithms
Mode of delivery, planned learning activities and teaching methods:
2 hours weekly (on-site method)
2 hours weekly (on-site method)

Credits allocated:
Recommended semester/trimester:
Applied Informatics - bachelor (semi-compulsory), 6. semester
Level of study: 1.
Prerequisites for registration:
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:
LIDL, R. -- NIEDERREITER, H. Finite Fields. Cambridge: Cambridge University Press, 2nd Ed., 1997. 768 p. ISBN 0-521-39231-4.
POMERANCE, C. -- CRANDALL, R. Prime Numbers. New York: Springer, 2001. 546 p. ISBN 0-387-94777-9.

Language of instruction:
slovak or english
Courses evaluation:
Assessed students in total: 268

23,1 %
21,6 %
19,4 %
16,4 %
16,4 %
3,1 %
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
doc. RNDr. Karol Nemoga, CSc. and programme supervisor

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

Type of output: