Algebra 1


Presented topics

  1. (5.10.) Motivation and goal of the course. 1. Prime factorization and gcd. Divisibility, Euclid's algoritm and Bezout identity, proof of Fundamental theorem of arithmetic [KS, 1.1-2].

  2. (12.10.) 2. Modular arithmetic. Congruences, Eulers's function and Eulers's Theorem. The Chinese Reminder Theorem and formulta for computing Eulers's function. [KS, 2.1-3].

  3. (19.10.) 3. Fileds, rings and domains. Axiomatic description and examples of rings, subrings, domains amd fields. Basic propoerties of operations of a ring, a characterization of finite domains as fields [KS, 3.1-2].

  4. (26.10.) 4. Quotient fields and polynomials. The construction of the quotient field of a domain [KS, 3.3]. Polynomial rings over commuative rings and over domains, degree of a polynomial. The algorithm of polynomial divison with reminder, roots and divisibility. [KS, 4.1-3].

  5. (9.11.) The number of roots is bounded by the degree of a polynomial [KS, 4.4]. 5. Divisibility. General notions of divisible and associated pairs of elements, description of associated pairs via invertible multiples [KS, 5.1]. The greatest common divisor, irreducible and prime elements. The notion of unique factorization domains (UFD).

  6. (16.11.) 6. Unique factorization domains. Characterization of a UFD as a ring with all greatest common divisors and without infinite chains of proper divisors [KS, 5.2-3, 7.1-3].

  7. (23.11.) 7. Calculating greatest common divisors. Euclidean norms and Euclidean domains, general Euclid's algoritm and Bezout coeffitients. Each Euclidean domain is a UFD. Examples. [KS, 7.4-6]. Gauss lemma, calculating gcd's in polynomials rings over a UFD, Gauss theorem [KS, 6.5-8].

  8. (30.11.) 8. Computing modulo a polynomial. Relation modulo in a polynomial ring over a field, construction of a factor ring. Factor ring F[x]/(m) for a filed F and a polynomial is a field if and only if m is irreducible [KS, 8.5]. Construction of rupture and splitting fields of polynomials [KS, 8.6,7], description and construction of finite fileds [KS, 9.1].

  9. (7.12.) The Chinese Reminder Theorem for polynomials and its consequences [KS, 8.1-3]. 9. Applications. Aplications of modular and finite-field arithmetic in cryptography: RSA and AES cyphers, protocol of (k,n)-secret sharing [KS, end of section 2.2, sections 9.1,2]. Basics of error-correcting codes: (generalized) Reed-Solomon codes [KS, section 9.3].

  10. (14.12.) 10. Groups and subgroups. Basic properties, examples and constructions of groups and their subgroups. Computational rules, intersections of subgroups [KS, section 10.1, Lemma 11.1]. Powers and the order of an element [KS, section 10.2], .

  11. (21.12.) 11. Order of subgroups. Subgroup generated by a set,, correspondence of the orders of a cyclic subgroup and its generator. Langrange's theorem. [KS, section 11], .

  12. (4.1.) 12. Group actions. Action of a group on a set. Stabilizer, an orbit of transitivity. Burnside's lemma. [KS, section 12].

  13. (11.1.) 13. Cyclic groups. Subgroups and generators of cyclic groups, orders of elements of a finite cyclic group. A finite subgroup of a multiplicative group of a field is cyclic. Diffie-Hellman key exchange protocol [KS, section 13].


Literature.
[KS] - Lecture notes