Veikko Keränen, Jouko Teeriaho, Rovaniemen AMK 2007

Introduction to Cryptography - Part 1    ( Part 2 is here )

ELEMENTARY NUMBER THEORY AND ALGORITHMS


  • Exercises  nb pdf
  • 1.  Integers and Division

  • 1.1 - Factorisation  nb pdf
  • 1.2 - Division Algorithm  nb pdf
  • 1.3 - Primes  nb pdf
  • 1.4 - Greatest Common Divisor and Least Common Multiple  nb pdf
  • 1.5 - Fundamental Theorem of Arithmetic  nb pdf
  • 2.  Euclidean Algorithm

  • 2.1 - An Efficient Way of Computing the Greatest Common Divisor  nb pdf
  • 2.2 - Linear Combination with Integer Coefficients gcd(a,b) = ua +vb  nb pdf
  • 2.3 - Complexity of Euclidean Algorithm  nb pdf
  • 3.  Congruences

  • 3.1 - Remainder and Congruence  nb pdf
  • 3.2 - Residue Class Modulo m   nb pdf
  • 3.3 - Complete Residue System Modulo m  nb pdf
  • 3.4 - Computational Rules for Congruences  nb pdf
  • 4.  Euler's and Fermat's Theorems

  • 4.1 - Coprime Residue Class (System) and Euler's Totient φ-Function  nb pdf
  • 4.2 - Reduced Residue System Modulo m  nb pdf
  • 4.3 - Euler's and Fermat's Theorems  nb pdf
  • 4.4 - Euler's Totient Function and Preservation of Multiplication  nb pdf
  • 4.5 - Quick Computation of Big Powers: Euler's Theorem and Method of Successive Squares  nb pdf