Applied Abstract Algebra

D. Joyner, R. Kreminski, J. Turisco

Date: 2-1-2003

• Contents
• Some elementary number theory
  • Introduction
  • Divisibility
    • Division algorithm
    • The greatest common divisor and least common multiple
  • Binary and -ary notation
    • Application: Divisibility criteria
    • Application: Winning the game of Nim
  • The Euclidean algorithm
    • Ideals
    • The Euclidean algorithm
    • Linear diophantine equations
    • The extended Euclidean algorithm
    • Euler's phi function
  • Primes
    • Pascal's triangle revisited
    • The Fundamental Theorem of Arithmetic
    • Primality testing
      • Sieve of Eratosthenes
  • Multiplicative Functions
    • Perfect numbers and Mersenne primes
  • 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 principles 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
  • Motivation and notation for codes
    • Basic definitions
    • The Hamming metric
    • Properties of the minimum distance
  • -codes and error correction
    • The generator matrix
    • The binary Hamming code
  • Bounds on the parameters of a code
    • Question: What is ``the best'' code?
  • The dual code
  • Computing the check matrix and the encoding matrix
  • Syndrome decoding
  • Hamming codes
    • Binary hamming codes
    • -ary Hamming codes
    • Decoding -ary Hamming codes
  • Cyclic codes
    • Quadratic residue codes
  • Application: The hats problem
  • Application: Searching with lies
    • The case of one lie
  • 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 project: Tiling with groups
  • Special project: Latin squares
  
  
• An introduction to groups
  • Cyclic groups
  • The dihedral group
  • 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
    • Example: The Verhoeff check digit scheme
    • 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
  • 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 ...