Бакалавриат 2020/2021

Алгебра

Статус: Курс обязательный (Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных")

Направление: 01.03.02. Прикладная математика и информатика

Кто читает: Департамент больших данных и информационного поиска

Где читается: Факультет компьютерных наук

Когда читается: 1-й курс, 4 модуль

Формат изучения: без онлайн-курса

Преподаватели: Авдеев Роман Сергеевич, Калеева Галина Анатольевна, Мажуга Андрей Михайлович, Медведь Никита Юрьевич, Трушин Дмитрий Витальевич

Язык: английский

Кредиты: 3

Контактные часы: 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

• Give the definition of a group.
• Give an example of a group.
• Check if a set with an operation is a group or not.
• Compute orders of all elements of a given group.
• Check if a given group is cyclic or not.
• Give an example of a normal subgroup.
• Check if a given subgroup is normal.
• Construct a quotient group for a given group and a subgroup.
• Give the definition of a homomorphism and an isomorphism.
• Give the statement of the Homomorphism theorem.
• Apply the Homomorphism theorem to describe a quotient group.
• Give the statement of the Chinese remainder theorem.
• Describe key exchange algorithm.
• Describe message encryption and decryption algorithms.
• Apply encryption and decryption algorithms to transfer a simple message.
• Give examples of cyclic groups applicable for message transferring.
• Give the definition of a ring.
• Give an example of a ring.
• Give the definition of an ideal.
• Give an example of an ideal.
• Describe the division algorithm in a polynomial ring with one variable.
• Describe multiplication and addition of the ring of remainders.
• Give the definition of an irreducible polynomial.
• Give an example of an irreducible and reducible polynomials.
• Give the definition of a field.
• Give an example of a field.
• Formulate a criterion for the ring of remainders to be a field.
• Give the definition of a finite field.
• Give an example of a finite field.
• Give the definition of a characteristic of a field.
• Find the characteristic of a given field.
• Compute explicitly a finite extension of a field.
• Describe a pseudo random generator based on a multiplication in a finite field.
• Give the definition of the lexicographic order.
• For a given monomial, find all smaller monomials with respect to the lexicographic order.
• Reduce a polynomial with respect to a set of polynomials.
• Give the definition of a Groebner basis.
• Check if a set of polynomials is a Groebner basis.
• Give the definition of an S-polynomial.
• Compute a Groebner basis for a given set of polynomials.

Course Contents

• Groups
  Elements of Set Theory, groups, order of elements, cyclic groups, subgroups, normal subgroups, quotient group, homomorphisms and isomorphisms, the Homomorphism Theorem.
• Cryptography
  Diffie-Hellman key exchange. ElGamal Encryption.
• Rings and Ideals
  Polynomials in one variable, division with remainder. Ring of remainders, explicit description of the operations. Irreducible polynomials.
• Fields
  Ring of remainders and field extensions. Finite fields, characteristic of a field. Operations in a finite field. Pseudo random generators based on finite fields.
• Groebner basis
  Polynomials in several variables. The lexicographic order. Reduction of a polynomial with respect to a polynomial or a set of polynomials, remainder. Groebner basis and Buchberger's algorithm.

Assessment Elements

• Home assignments
  During the module students have to complete home assignments weekly. Professors and assistants can ask students to present their written solutions orally.
• Written Test
  After the last class all students pass through a written test.
• Oral Exam

Interim Assessment

• Interim assessment (4 module)
  0.3 * Home assignments + 0.4 * Oral Exam + 0.3 * Written Test

Bibliography

Recommended Core Bibliography

• Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (Vol. Second edition). Boca Raton, FL: Chapman and Hall/CRC. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=nlebk&AN=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.