Бакалавриат
2023/2024
Алгебра
Статус:
Курс обязательный (Прикладной анализ данных)
Направление:
01.03.02. Прикладная математика и информатика
Где читается:
Факультет компьютерных наук
Когда читается:
1-й курс, 4 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Язык:
английский
Кредиты:
4
Контактные часы:
40
Course Syllabus
Abstract
The course is a gentle introduction to the theory of algebraic structures, including Groups, Rings and Fields, with applications to Algorithms, Cryptography and Coding Theory. The course provides professional background for further courses related to Discrete Mathematics, Formal Languages, Game Theory and Information Security. Prerequisites: the course is based on knowledge of numerical systems and functions studied in high school, as well as on the basic concepts of the courses on Linear Algebra and Geometry, Calculus and Discrete Mathematics in the first three modules.
Learning Objectives
- Introduction of main algebraic structures with explicit examples, motivations and applications.
- Practice in basic computations with groups, rings and fields.
- Forming students’ skills in using matrix and polynomial techniques to formalize and solve applied problems, including economic and financial ones.
- Study of the algorithmic aspects of the theory of finite groups and finite fields.
- Formalization for further applications in programming, public-key cryptography and information theory.
Expected Learning Outcomes
- Apply encryption and decryption algorithms to transfer a simple message.
- Apply the Homomorphism theorem to describe a quotient group.
- Check if a given group is cyclic or not.
- Check if a given subgroup is normal.
- Check if a set of polynomials is a Groebner basis.
- Check if a set with an operation is a group or not.
- Compute a Groebner basis for a given set of polynomials.
- Compute explicitly a finite extension of a field.
- Compute orders of all elements of a given group.
- Construct a quotient group for a given group and a subgroup.
- Describe a pseudo random generator based on a multiplication in a finite field.
- Describe key exchange algorithm.
- Describe message encryption and decryption algorithms.
- Describe multiplication and addition of the ring of remainders.
- Describe the division algorithm in a polynomial ring with one variable.
- Find the characteristic of a given field.
- For a given monomial, find all smaller monomials with respect to the lexicographic order.
- Formulate a criterion for the ring of remainders to be a field.
- Give an example of a field.
- Give an example of a finite field.
- Give an example of a group.
- Give an example of a normal subgroup.
- Give an example of a ring.
- Give an example of an ideal.
- Give an example of an irreducible and reducible polynomials.
- Give examples of cyclic groups applicable for message transferring.
- Give the definition of a characteristic of a field.
- Give the definition of a field.
- Give the definition of a finite field.
- Give the definition of a Groebner basis.
- Give the definition of a group.
- Give the definition of a homomorphism and an isomorphism.
- Give the definition of a ring.
- Give the definition of an ideal.
- Give the definition of an irreducible polynomial.
- Give the definition of an S-polynomial.
- Give the definition of the lexicographic order.
- Give the statement of the Chinese remainder theorem.
- Give the statement of the Homomorphism theorem.
- Reduce a polynomial with respect to a set of polynomials.
Bibliography
Recommended Core Bibliography
- 9781466570276 - Katz, Jonathan; Lindell, Yehuda - Introduction to Modern Cryptography, 2nd Edition - 2014 - CRC Press - http://search.ebscohost.com/login.aspx?direct=true&db=nlebk&AN=1766746 - nlebk - 1766746
Recommended Additional Bibliography
- David A. Cox, John Little, Donal O’Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. - Springer International Publishing, Switzerland, 2015. Print ISBN: 978-3-319-16720-6. Online ISBN: 978-3-319-16721-3.