• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Bachelor 2019/2020

Algebra

Area of studies: Applied Mathematics and Information Science
When: 1 year, 4 module
Mode of studies: offline
Language: English
ECTS credits: 3
Contact hours: 44

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

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

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

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

Assessment Elements

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

Interim Assessment

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

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.