Next:
Contents
Contents
Index
Applied Abstract Algebra
D. Joyner, R. Kreminski, J. Turisco
Date:
8-10-2002
ROUGH DRAFT
Contents
Some elementary number theory
Introduction
Divisibility
Division algorithm
The greatest common divisor and least common multiple
Linear diophantine equations
Binary and
-ary notation
Application: Divisibility criteria
Application: Winning the game of Nim
The Euclidean algorithm
Ideals
The Euclidean algorithm
The extended Euclidean algorithm
Euler's phi function
Primes
Pascal's triangle revisited
The Fundamental Theorem of Arithmetic
Perfect numbers and Mersenne primes
Primality testing
Sieve of Eratosthenes
Multiplicative Functions
Congruences
Application: Divisibility criteria revisited
Aside on equivalence relations
Properties of
Repeated squaring algorithm
Fermat's little theorem
Linear recurrence equations
Application: Two ciphers
Caesar's cipher
A stream cipher: linear feedback shift registers
Feedback with carry shift register ciphers
Application: calendar calculations
First method
Second method (due to Conway)
The Chinese remainder theorem
General Chinese remainder theorem
An application to Euler's
-function
Integral powers mod
Fermat's Little Theorem, revisited
Euler's theorem
Application: Decimal expansions of rational numbers
Application: RSA encryption
Small exponent attack on RSA
Application: The discrete log problem
Application: Diffie-Hellman key exchange
Application: ElGamal encryption
Arithmetic properties of
: a summary
Special project: continued fractions (optional)
Number theory exercises using GAP
Number theory exercises using MAGMA
Polynomials, rings and fields
Fields: basic examples
Quadratic number fields
Gaussian integers
The integers of
A construction of finite fields
Matrix constructions of finite fields
Polynomials
is a ring
Roots
The division algorithm
The Euclidean algorithm
Extended Euclidean Algorithm
Polynomial ideals
Motivation
The ring
Factoring polynomials
Unique factorization theorem
General principals in factoring
Factoring
over
Factoring over a finite field
Modular arithmetic with polynomials
Arithmetic properties of
Constructing finite extensions of fields
Kronecker's theorem
Companion matrices and extension fields
Polynomials in many variables
Monomials
Leading terms
Gröbner bases
Reduction modulo a set
Buchburger's algorithm
Applications
Algebraic curves
Algorithm to find the GCD of
Special project: Nimbers
Numerical notation
Tree notation
Special project: factoring over
Explicit formulas for the roots
Quadratic formula
Cubic formula
Quartic formula
Higher degree case
Factoring
over
Special project: Factoring over
Special Project: Factoring over
or
Primitive polynomials
Factoring strategies
Irreducibility criteria
Factoring
over
Polynomials and rings using GAP
Finite fields
Some vector spaces
Rings
Polynomials
Gröbner bases
Polynomials and rings using MAGMA
Finite fields
Rings
Polynomials
RSA for polynomials in MAGMA
Error-correcting codes
Background on vector spaces
Background on information theory
Binary symmetric channel
Uncertainty
Basic results on codes
The Hamming metric
-codes and error correction
The binary Hamming
code
Equivalent codes
Bounds on the parameters of a code
The dual code
Computing the check matrix and the encoding matrix
Syndrome decoding
Question: What is ``the best'' code?
Application: Searching with lies
Application: The hats problem
Hamming codes
Binary hamming codes
Decoding Hamming codes
Application: Searching with lies, revisited
Cyclic codes
Quadratic residue codes
Some unsolved problems in coding theory
Coding theory exercises using GAP
Background on finite fields
Some vector spaces
Some simple codes
Hamming codes
Reed-Muller codes
Cyclic codes
Coding theory exercises using MAGMA, I
Some vector spaces
Hamming codes
Reed-Muller codes
Cyclic codes
Permutations
Functions
Permutations
Inverses
Cycle notation
An algorithm to list all the permutations
Application: The rotation game
Application: Bell ringing
Application: Rubik's cubes
Rubik's cube
Rubik's cube
Special projects: Tiling with groups
An introduction to groups
Cyclic groups
The symmetric group
General definitions
The general linear group
matrices
Multiplication and inverses
Determinants
The definition of
Application: The automorphism group of a code
Abelian groups
Permutation groups
Subgroups
Puzzling examples
The dihedral group
Example: The two squares group
Commutators
Conjugation
Cosets
Functions between two groups
Application: Campanology, revisited
The Cayley graph of a group
Graphs
Cayley graphs
Application: God's algorithm
Kernels are normal, some subgroups are not
The alternating group
Quotient groups
Special projects: Tiling with groups
Finite groups using GAP
Permutations
Permutation groups
GAP project: Why Steinhaus' algorithm works
Finite groups using MAGMA
Permutations
Permutation groups
MAGMA project: Why Steinhaus' algorithm works
Special projects: Codes
Alternant codes
Lexicodes
The construction
Tanner graph of a code
A brief guide to Goppa codes
Examples of curves
Curves in MAGMA
Examples of points and divisors
Points using MAGMA
Examples of Riemann-Roch spaces
Riemann-Roch spaces in MAGMA
Examples of Goppa codes
Examples of Goppa codes in MAGMA
Brief guide to low density parity check codes
Sparse check matrix definition
Graph-theoretic definition
Cayley graph construction
Other constructions
Block matrices of permutation matrices
Finite geometries construction
Decoding the ternary Golay code
Introduction
Background
Tetracode construction
The ``col/tet'' construction
The MINIMOG and
Curtis' kitten - modulo
labeling
Curtis' kitten - shuffle labeling
The algorithm
Appendices
Basics of GAP
Introduction
Input-output
Polynomials and other functions
Lists
Vectors and matrices
Using for loops
Sets
Adding numbers in a list
GAP functions and procedures
Number theoretic functions in GAP
Simple exercises in MAGMA
Introduction
Input-output
Polynomials and other functions
Common data structures
Lists, sequences, via for loops
Using for loops
Using if-then statements
Removing elements from a list
Cartesian products
Sets
Adding numbers in a list
Membership
More complicated sets
for loops
if then statements
MAGMA functions and procedures
Printing
Basic commands
Calculus
Number theory
Combinatorics
Linear algebra
Plane curves
Solutions to exercises
Bibliography
Index
About this document ...
David Joyner 2002-08-23
-ary notation
-function
: a summary
![$ F[x]/(m(x))$](img10.png){kind=small}
or
![$ F[x]$](img7.png){kind=small}
is a ring
over
![$ f,g\in F[x,y]$](img11.png){kind=small}
![$ [n,k,d]$](img16.png){kind=small}
-codes and error correction![$ [7,4,3]$](img17.png){kind=small}
code
Rubik's cube
Rubik's cube
matrices
labeling