Бакалавриат
2018/2019
Алгебра
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Программа двух дипломов НИУ ВШЭ и Лондонского университета "Прикладной анализ данных")
Направление:
01.03.02. Прикладная математика и информатика
Когда читается:
1-й курс, 4 модуль
Формат изучения:
Full time
Язык:
английский
Кредиты:
3
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
- GroupsElements of Set Theory, groups, order of elements, cyclic groups, subgroups, normal subgroups, quotient group, homomorphisms and isomorphisms, the Homomorphism Theorem.
- CryptographyDiffie-Hellman key exchange. ElGamal Encryption.
- Rings and IdealsPolynomials in one variable, division with remainder. Ring of remainders, explicit description of the operations. Irreducible polynomials.
- FieldsRing of remainders and field extensions. Finite fields, characteristic of a field. Operations in a finite field. Pseudo random generators based on finite fields.
- Groebner basisPolynomials 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 assignmentsDuring the module students have to complete home assignments weekly. Professors and assistants can ask students to present their written solutions orally.
- Written TestAfter the last class all students pass through a written test.
- Oral Exam
Interim Assessment
- Interim assessment (4 module)0.3 * Home assignments + 0.5 * Oral Exam + 0.2 * 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.