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 2011. Op dinsdag van 15:45 tot 17:30 in auditorium 16 en op donderdag van 13:45 tot 15:30 ook in auditorium 16.

Studiemateriaal

Algebra Interactive, Springer-verslag, Heidelberg 1999 (aanbevolen), in engels. Dit boek is niet meer beschikbaar voor verkoop maar de auteurs stellen een exemplaar voor download ter beschikking.
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

06 Sep 2011
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

08 Sep 2011
Monoiden en groepen: definities, structuur, n-tallige bewerkingen, halfgroepen, neutraal element/eenheidselement, commutatieve bewerkingen. Permutaties: Cykeltype, conjugatie, transposities, permutatie is een product van transposities, pariteit van een permutatie.

1. Huiswerk: Lees over permutaties (hoofdstuk 5).
2. Sym_n is een halfgroep met bewerking compositie (of samenstelling). Laat zien dat Alt_n een halfgroep is.
3. Laat zien dat (M_n(R,*)) (n × n matrices met reële coëfficiënten en bewerking multiplicatie) een halfgroep is.

13 Sep 2011
Permutaties, signum (teken), alternerende groep Alt_n, eigenschappen.

Huiswerk:
Laat zien dat (M_n(R,*)) (n × n matrices met reële coëfficiënten en bewerking multiplicatie) een halfgroep is.
Hier zijn de foto's van het board.

15 Sep 2011
Monoiden, onderhalfgroepen, ondermonoiden, direct product van monoiden en halfgroepen, enkele voorbeelden.
Huiswerk: Maak een tabel van alle elementen en hun producten van (Alf_n,*)×(Z/4Z,+).
Hier zijn de foto's van het board.

20 en 22 Sep 2011
Lecture given by Andries Brouwer. Here is what he sent to me as a summary for the two lectures.
Talked about "algebraic structures" (as a defined concept) so that one gets uniform definitions for substructure (and generation), and (homo)morphism, and direct product.
Examples are semigroups, monoids, groups, rings (commutative or not).
The intersection of substructures is a substructure, and the intersection of all substructures containing a subset D is the substructure <D> generated by D, the smallest substructure containing D. One has <∅>=∅ iff there are no 0-adic operations.
Also talked about fields and skew fields (e.g., the quaternions). These are not algebraic structures in the above formal sense (for two reasons: taking inverses is not defined everywhere, and the axiom 0 ≠ 1 is an inequality instead of an equality). Therefore it is not surprising that the direct product of two fields is not a field.

As application of the 1-generator monoid: Pollard rho, how to factor numbers of medium size.

The free monoid on an alphabet is the collection of strings, with the empty string as neutral element and concatenation as binary operation.

A field has a prime field that is either the rational numbers (case of characteristic 0) or a finite field with p elements (case of characteristic p).
The field is a vector space over the prime field. It follows that a finite field has p^e elements for some prime p and exponent e.

A semigroup can have many left units or many right unit, but if there is both a left and a right unit, then they coincide, and there is a unique unit element.
In a monoid an element can have several left or right inverses. But if there are both left and right inverses, these coincide and there is a unique inverse.

For a monoid M, the subset M* of invertible elements carries a group structure. For example, for M_n(R) (real matrices of order n) we find M_n(R)* = GL_n(R), the group of real matrices of order n with nonzero determinant. It has the subgroup SL_n(R) of real matrices of order n with determinant 1.

Other examples of groups: additive group of the reals or the integers, multiplicative group of the nonzero reals, Sym_n and Alt_n, the dihedral group (called D_m or D_2m of symmetries of a regular m-gon.

In a group one has cancellation: xy=xz implies y=z.

The size of a subgroup of a finite group is a divisor of the size of the group since one has a partition into cosets. In particular, the orders of elements divide the order (that is, size) of the group.

The Euler totient function φ is defined by Σ φ(d) = n, where the sum is over the divisors d of n. We computed this for small n but did not derive a formula. If (a,m)=1 then a^φ(m) = 1 because φ(m) is the size of (Z/mZ)*.

27 Sep 2011
Monoiden en groepen: direct product, morfismen, isomorfismen, Chinese reststelling, voorbeelden.
Huiswerk:

1. Vind een oplossing van het volgende systeem van simultane congruenties:
   x≡ 1 mod 2, x≡ 4 mod 5, x≡ 3 mod 9.
   
   Let op de veranderingen in het laatste beeld.
   
   Je kunt hulp op wikipedia Wikipedia krijgen of op paginas 26 en 27 van "Number Theory and Algebra"
2. Hebben de volgende systemen oplossingen? Modulo welke getallen zijn deze uniek?
   1. x≡ 3 mod 4, x≡ 6 mod 12.
   2. x≡ 4 mod 9, x≡ 10 mod 12.
3. If S_i is a submonoid of the monoid M_i, for i=1,2, then S₁ × S₂ is a submonoid of M₁ × M₂. Prove this.

21 Sep 2010
Monoiden en groepen: ondermonoiden, ondergoepen, Alt_n als ondergroep van Sym_n, GL(n,R), SL(n,R, iedere doorsnede van ondermonoiden/ondergroepen is een monoid/groep, cyclische monoiden/groepen, voortbrenger van een cyclische monoid, ondermonoid/ondergroep van M voortgebracht door D, C_k,n.

Huiswerk: 6.7.11 Let M be a cyclic monoid generated by the element c. Suppose that c²≠ e, c²≠c⁶, and c⁴=c⁸ . With with cyclic monoid C_k,l is M isomorphic?
Hier zijn de foto's van het board.

04 Oct 2011
Monoiden en groepen: cyclische groepen, orde van groepen en elementen, voorbeelden, Euler function,
Huiswerk: Compute phi(37800).
Compute phi(148167).
Compute phi(103417899045095880).
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.

06 Oct 2011 Centrum Z(G), centralisator C(X), normalisator N(X), beeld, kern, linkernevenklassen, stelling van Lagrange.
Voorbeelden:

• Is een G commutatieve groep, dan zijn Z(G)= C(X)= N(X)=G voor iedere X.
  
• G=GL(n,R). Z(G)={diagonaalmatrices A met det(A)!=0}.
• G=Sym₃, X={(1,2)}. Z(G)={id}. C(X)={id, (1,2)}= N(X).
  Y={(1,2,3), (1,3,2)}. C(Y)={id}, N(Y)={id,(1,2,3), (1,3,2)}.

Huiswerk: bewijs dat Z(G), N(X) en Im(f) ondergroepen zijn.
Hier zijn de foto's van het board.

11 Oct 2011
Vorbeelden van centrum Z(G), centralisator C(X), normalisator N(X), stelling van Lagrange, kleine stelling van Fermat.
Huiswerk: 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 c?
d) Which elements in (R,*) are invertible?
e) Is (R,*) a group?
Hier zijn de foto's van het board.

13 Oct 2011
Z/nZ^*, alle linkernevenklassen zijn even groot, stelling van Lagrange, kleine stelling van Fermat, stelling van Euler, rechternevenklassen, normaaldeler; Monoiden en groepen: kern is een normaaldeler.
voorbeelden.
Huiswerk: (per email op Oct 18)
Let M be a monoid. Show that the set M^× of invertible elements is a group.
Show that Z(G) and ker(f) are normal subgroups.

Hier zijn de foto's van het board.

18 en 20 Oct 2011
Lecture given by Andries Brouwer. Here is a detailed summary for the two lectures.
Rings, and examples such as Z, Z/nZ, polynomial rings R[x] over a ring R, matrix rings M_n(R) over a ring R, fields. Ring extension R[a]. Field extension F(a).
Cardinalities, cardinal numbers, power set.
Subrings, homomorphisms of rings, ideals: the kernel of a homomorphism is an ideal and an ideal is the kernel of a homomorphism, namely the quotient map from R to R/I.
Zero divisors. Domains.
For a prime ideal I the quotient R/I is a domain.
If R is a domain, it has a quotient field.
For a maximal ideal I the quotient is a field.
Examples: GF(4) with addition and multiplication table.
The complex numbers as reals[X]/(X^2+1).
GF(4) as GF(2)[X]/(X^2+X+1).
GF(8) as GF(2)[X]/(f(X)) with f(X) = X^3+X+1 or X^3+X^2+1.
A field has a characteristic, a prime field.
A big field is a vector space over a subfield.
In particular, a finite field has positive characteristic p and size p^e for some e.
In a field, a polynomial does not have more roots than its degree.
In the field F[X]/(f(X)), where f(X) is irreducible over F, the polynomial f has a root (namely, the residue class of X).
It is not true that f always factors into linear factors, see Q[X]/(X^3-2). Splitting fields exist via repeated extensions.
All elements a of GF(q) satisfy a^q=a.
Raising to the power p is a field automorphism, and so is raising to the power q. The elements in a field in which X^q-X factors into linear factors and that satisfy a^q=a form a subfield of size q.
Since splitting fields exist and are unique it follows that GF(q) can be defined as the splitting field of X^q-X.
There is a unique field GF(q) for each prime power q.
One can count the number of irreducible polynomials of a given degree.
The multiplicative group of a field is cyclic.


25 Oct 2011
Ringen en lichamen: ring, licham, eenheidengroep, cartesisch product, doorsnede van onderringen, voorbeelden.
Hier zijn de foto's van het board.

27 Oct 2011
Ringen en lichamen: domain, nuldeeler, homomorfismen, Im, Ker, ideal.
Hier zijn de foto's van het board.

Tentamen

Het tentamen voor 2WF10 is gepland voor donderdag 10-11-2011, 14:00-17:00 in Aud 11; sluitingsdatum is de 23-10-2010. De herkansing is gepland voor vrijdag 27-01-2012, 14:00-17:00, sluitingsdatum is de 09-01-2011.


Proeftentamen

Tentamen van 2011: 2011-11-10.pdf.
Tentamen van 2010: 2010-11-02-exam.pdf en 2011-01-21-exam.pdf.

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.