Tanja Lange
Coding Theory and Cryptology
Eindhoven Institute for the Protection of Information
Department of Mathematics and Computer Science
Room HG 9.92
Technische Universiteit Eindhoven
P.O. Box 513
5600 MB Eindhoven
Netherlands

Phone: +31 (0) 40 247 4764
Fax.: +31 (0)40 243 5810

e-mail:tanja@hyperelliptic.org

Dit is the pagina voor het college 2WF10 - Algebra 2. De oficiele pagina OWInfo.

Inhoudsbeschrijving

De student krijgt inzicht in de eigenschappen en het nut van de fundamentele algebraische structuren: Groepen, Ringen en Lichamen en de daarbij behorende morfismen. Verder leert de student practische vragen en problemen in dit vakgebied te lijf te gaan met een computer algebra systeem.
Permutaties, symmetriegroepen, monoiden en semigroepen, de classificatie van cyclische monoiden. Productconstructies en deelstructuren. Groepen, de kleine stelling van Fermat, de stelling van Lagrange over ondergroepen. Ringen en Lichamen, een uitgebreide kennismaking met polynoomringen over een lichaam. Idealen en normale ondergroepen als kernen van morfismen. De classificatie van eindige lichamen. Een meer gedetailleerde studie van permutatie groepen, en automorfisme groepen van combinatorische en meetkundige objecten. Algoritmen op groepen, in het bijzonder het Schreier boom algoritme.

Laatste nieuws

Werkcolleges zijn in semester 1, blok A, najaar 2010. Op dinsdagmorgens en op donderdagmorgens van 10:45 tot 12:30 in zaal 2.19 van potentiaal.


Studiemateriaal

Algebra Interactive, verkrijgbaar bij Springer-verslag, heidelberg 1999 ISBN 3-540-65368-6 (aanbevolen), in engels.
Meer informatie op het web

• Andries Brouwer (Technische Universiteit Eindhoven), Algebra 2. Overzicht en woordenlijstje Engels-Nederlands.
• Peter Stevenhagen (Universiteit Leiden), Algebra 1 in nederlands.
• Peter Stevenhagen (Universiteit Leiden), Algebra 2 in nederlands.

Collegeplanning

31 Aug 2010
Repetitie van rekenen modulo n, het RSA-cryptosysteem, de Euclidische algoritme. In het werkcollege hebben wij de systeem "Kid-RSA" van Fellows en Koblitz gekraakt. Attentie, did systeem is niet veilig.
Public-key crypto
M-RSA

02 Sep 2010
Permutaties, list en cykel notatie, aanntal elementen in S_n, decompositie in disjuncte cycli, order van een permutatie.
Huiswerk: les "5.1 Symmetric Groups" en "5.2 Cycles" en de opgaven.
Dank gaat aan Erwin van Duijnhoven voor het nemen van foto's van het board.


07 Sep 2010
Opgaven.
Permutaties: Cykeltype, conjugatie, transposities, permutatie is een product van transposities, pariteit van een permutatie.
Huiswerk: opgave 16, dit is
Put the numbers 1,2,3,4 into a 2 by 2 matrix as follows. Put 1 on spot 11, 2 on spot 12, 3 on spot 21 and 4 on spot 22, i.e. the matrix [[1,2],[3,4]].
a) Suppose you are allowed to interchange two columns or two rows. Which permutations of S₄ can you get using these moves repeatedly? What if you allow as extra type of move a reflection in the diagonal of the matrix?
b) Suppose you are allowed to do the following types of moves: Choose a column or row and interchange the two entries. What permutations do you get this way?
c) Now consider the 3 by 3 matrix [[1,2,3],[4,5,6],[78,9]]. Individual moves are: Choose two rows (or two columns) and interchange them. Show that you can label each resulting permutation with a pair of permutations from S₃ × S₃. Conclude that you get 36 permutation.
d) Experiment with a 3 by 3 matrix, where a single move consists of shifting the entries of an individual column or row cyclically. With the techniques of Chapter 8, you will be able to deal with such problems effectively.
Hier zijn de foto's van het board.


09 Sep 2010
Opgaven.
Permutaties: signum (teken), sgn is multiplicatiev, alternerende groep A_n, eigenschappen.
Monoiden en groepen: definities, structuur, n-tallige bewerkingen, halfgroepen.
Huiswerk: opgave 13, dit is:
For g ∈S_n, we define a matrix M by M_ij=1 if i=g(j), and M_ij=0 otherwise. The matrix M is called the permutation matrix of g.
a)Calculate the permutation matrices for the 6 permutations of S₃.
b) Prove: If g, h ∈S_n with associated permutation matrices M and N, then the permutation matrix of g h is MN.
c) Prove: If g is a transposition then det(M)=-1.
d) Show that sgn(g)=det(M).
Jullie kunnen gebruik maken van IMGP2046.JPG.
Hier zijn de foto's van het board.


14 Sep 2010
Monoiden en groepen: halfgroepen, neutraal element/eenheidselement, monoiden, commutatieve bewerkingen, onderhalfgroepen, ondermonoiden, voorbeelden.
Huiswerk: opgaven 2 en 4 in Sectie 6.7:
2. Prove: if in a monoid every element x different from the identity satisfies x²=e, then the monoid is commutative.
4. Which of the two monoids on 2 elements, Z/2Z with addition or multiplication, is the extension of a semi-group with a unit element?
Hier zijn de foto's van het board.

16 Sep 2010
Monoiden en groepen: ondermonoiden, GL_n, SL_n, {c}^*, Z[i], iedere doorsnede van monoiden is een monoid, direct product, morfismen, isomorfismen, automorfismen, voorbeelden.
Huiswerk: opgaven 6, 8 en 7 in Sectie 6.7:
6. Show that the direct product of two monoids is again a monoid.
8. If S_i is a submonoid of the monoid M_i, for i=1,2, then S₁ × S₂ is a submonoid of M₁ × MS₂. Prove this.
7. Find two submonoids of Z/6Z such that their union is not a submonoid.
Hier zijn de foto's van het board.

21 Sep 2010
Monoiden en groepen: cyclische monoiden, voortbrenger van een cyclische monoid, ondermonoid van M voortgebracht door D, C_k,n, inverse, inverse van a is uniek, schrapwet.
Huiswerk: bewijs van Theorem 17 lezen; opgaven 10, 11 en 13 in Sectie 6.7:
10. Let X be be a nonempty set. If M is a monoid with unit element e, then we can define a monoid structure o the set F of all maps from X to M as follows.


• If f and g are in F, then their product f × g is defined by (f× g)(x)=f(x)*g(x).
• The constant map x ↦ e is the unit element.
Prove this.
11. Let M be a cyclic monoid generated by the element c. Suppose that c²≠ e, c²≠c⁶, and c⁴=c⁸ . With with C_k,l is M isomorphic?
13. Suppose that f:M→M' is a morphism. Prove that the image f(M) is a submonoid of M' and that the kernel of f, i.e., {m ∈ M|f(m)=e'}, where e' is the identity of M', is a submonoid of M.
Hier zijn de foto's van het board.

23 Sep 2010
Monoiden en groepen: Euler function, Z/nZ^*, groepen; voorbelden.
Huiswerk: Compute phi(37800)
17. What are the invertible elements of C_k,n?
Hier zijn de foto's van het board.

28 Sep 2010
Monoiden en groepen: groepen, ondergroepen, cyclische groepen, voorbrenger, centrum, centralisator, normalisator, voorbeelden.
Huiswerk: bewijs dat C(X), Z(G) en N(X) ondergroepen zijn.
Hier zijn de foto's van het board.

30 Sep 2010
Monoiden en groepen: centrum, centralisator, normalisator, homomorfismen, isomorfismen, beeld, kern, cyclische groepen, orde van groepen en elementen, voorbeelden.
Huiswerk: 23 en 24 in 6.7.
23. Let G be a group and H a nonempty finite subset of G closed under multiplication. Prove the following

1. For h ∈ H, the elements h^1, , h², h³, ... are not all distinct.
2. The identity element is in H.
3. Every element of H has finite order.
4. H is a subgroup of G.

24. Let G be a finite group of order m. Let g ∈ G. Suppose that for each prime divisor p of m we have that g^m/p is not the identity. Prove that the group G is cyclic and generated by g.
Hier zijn de foto's van het board.

05 Oct 2010
Monoiden en groepen: ondergroepen van cyclische groepen, orde van a mod 29 voor alle a, aantal van elementen met order d in cyclische groep van order n, vezel.
Huiswerk: 27 and two extra parts.
27 On R we define the operation * by x*y=x+y-xy.
a) Is * commutative?
b) Is * associative?
c) Is there an identity element in R with respect to x?
d) Which elements in (R,*) are invertible? e) Is (R,*) a group?
Hier zijn de foto's van het board.

07 Oct 2010
Monoiden en groepen: alle vezels zijn even groot als de kern, linkernevenklassen, stelling van Lagrange, kleine stelling van Fermat, stelling van Euler, rechternevenklassen, normaaldeler; voorbeelden.
Huiswerk: bewijs van Theorem 44 lezen; proeftentamen.
Hier zijn de foto's van het board.

12 Oct 2010
Monoiden en groepen: kern is een normaaldeler.
Ringen en lichamen: ring, deelring, regenregels, eenheidengroep, homomorfismen, voorbeelden.
Huiswerk: Opgaven 1 en 3 in 7.8.
Hier zijn de foto's van het board.

14 Oct 2010
Ringen en lichamen: homomorfismen, eigenschappen, cartesisch product van ringen, voorbeelden.
Hier zijn de foto's van het board.

19 en 21 Oct 2010
Lecture given by Andries Brouwer. Here is what he sent to me as a summary for the two lectures. This material is important and you will need it later on, but it is not part of the exam.
I talked about general structures and substructures and the smallest sub-foo <A> generated by a set A inside a foo X. Showed that a submonoid is not the same as a subsemigroup with 1.
Illustrated the construction of new systems by making something that is too big and dividing out an equivalence relation: Given the natural numbers one can form pairs (m,n) and call two equivalent when m+n' = m'+n. On the quotient one gets the integers. Then again form pairs (p,q) with nonzero q, and call two equivalent when pq' = qp'. On the quotient one gets the rationals.
Talked about domains. The above construction yields the field of fractions. Any finite domain is a field.
Talked about fields. The subfield generated by the empty set is the prime field. It is either Q, the field of rationals, or GF(p) = Z/(p). One says that the characteristic is 0 and p in these cases. A field is a vector space over a subfield. It follows that a finite field has p^e elements, p prime.
Explicitly constructed GF(2), GF(3), GF(4), GF(8) on the blackboard. Constructed the complex numbers as R[X]/(X^2+1), R the reals. Gave the construction of GF(p^e) as GF(p)[X]/(p(X)) for an irreducible polynomial p(X) of degree e. Showed that (the residue class of) X is a root of p(X) in this extension, so that one can construct the splitting field of a polynomial. Showed that x ↦ x^q is an automorphism of any field of characteristic p. Constructed GF(q) as splitting field of X^q-X.

Tentamen

Het tentamen voor 2WF10 is gepland voor dinsdag 02-11-2010, 14:00-17:00; sluitingsdatum is de 17-10-2010. De herkansing is gepland voor vrijdag 21-01-2011, 14:00-17:00, sluitingsdatum is de 09-01-2011.
Het tentamen behandelt al materiaal dat tot en met inbegrip van 14 Oktober wordt voorgesteld.

Proeftentamen

Voor de laatste jaren was Andries Brouwer de docent voor Algebra 2. Hij was zo vriendschappelijk om me zijn oude examens te geven.

• tent9.pdf Uiteindelijk zou je alle oefeningen behalve nummer 4 moeten kunnen oplossen.
• tent10.pdfUiteindelijk zou je alle oefeningen behalve nummer 4 moeten kunnen oplossen.
• tent11.pdfUiteindelijk zou je alle oefeningen behalve nummer 3 moeten kunnen oplossen.
• opgaven.pdfUiteindelijk zou je alle oefeningen behalve nummer 5 moeten kunnen oplossen.
• 2WF10_2009_10_26.pdfUiteindelijk zou je alle oefeningen behalve nummers 4 en 5 moeten kunnen oplossen.
• 2WF10_2010_01_18.pdfUiteindelijk zou je alle oefeningen behalve nummers 4b) en 5 moeten kunnen oplossen.