Aug 17, 2019   4:41 p.m. Milica
Academic information system

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


     Information sheet          ECTS          Syllabus          


     Slovak          English          


University: Slovak University of Technology in Bratislava
Faculty: Faculty of Electrical Engineering and Information Technology
Course unit code: B-RAL
Course unit title: Fast algorithms
Mode of delivery, planned learning activities and teaching methods:
lecture2 hours weekly (on-site method)
seminar2 hours weekly (on-site method)

 
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:
Basic:
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
 
Notes:
 
Courses evaluation:
Assessed students in total: 247

ABCDEFX
21,1 %21,9 %18,6 %17,8 %16,6 %4,0 %
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.

Type of output: