ch-09

Chapter 9: Mathematics of Cryptography

9.1 Primes

  • Asymmetric-key cryptography relies heavily on prime numbers.

  • Important sections to discuss:

    • Definition of primes

    • Cardinality of primes

    • Checking for primality

    • Euler’s phi-function

    • Fermat’s Little Theorem

    • Euler’s Theorem

    • Generating primes

9.1.1 Definition

  • A prime number is defined as a number greater than 1 that has no positive divisors other than 1 and itself.

    • Example: The smallest prime is 2.

    • Primes smaller than 10: 2, 3, 5, 7; percentage of primes in the range 1-10 is 40%.

9.1.2 Cardinality of Primes

  • Infinite Number of Primes: It has been proven that there is an infinite number of primes.

  • Example given by the set {2, 3, 5, 7, 11, 13, 17}:

    • Prime product P = 510510; showing primes above 17 can be found.

  • Actual number of primes under 1,000,000 is 78,498.

9.1.3 Checking for Primeness

  • Method: Check if n is divisible by all primes less than or equal to the square root of n.

    • If composite, it has a prime divisor less than or equal to its square root.

  • Example: Is 97 prime? Check against primes less than √97 (below 9).

9.1.4 Euler’s Phi-Function

  • Defined as: φ(n) counts the positive integers up to n that are relatively prime to n.

  • Calculation:

    • For prime p: φ(p) = p - 1.

    • For composite n with prime factorization, combine rules from distinct primes.

  • Example: φ(13) = 12; φ(10) = φ(2) * φ(5) = 4.

9.1.5 Fermat’s Little Theorem

  • Two forms:

    • If p is a prime, then for any integer a:

      1. a^p ≡ a (mod p)

      2. a^(p-1) ≡ 1 (mod p)

  • Example: Solving 6^10 mod 11 to show application of theorem.

9.1.6 Euler’s Theorem

  • Contains two forms:

    • a^(φ(n)) ≡ 1 (mod n) if gcd(a, n) = 1

    • Used in RSA algorithm.

9.1.7 Generating Primes

  • Mersenne Primes: Form Mp = 2^p - 1.

  • Fermat Primes cover the series: 3, 5, 17, 257, 65537.

9.2 Primality Testing

  • Algorithms to test large integers for primality:

    • Deterministic algorithms

    • Probabilistic algorithms

9.2.1 Deterministic Algorithms

  • Divisibility Test: Check divisibility until √n.

    • Example: This can be very inefficient.

  • AKS Algorithm: Efficient with complexity depending on the number of bits.

9.2.2 Probabilistic Algorithms

  • Fermat Test: Quick check; if it returns true, n is likely prime but could be composite.

  • Example: Number 561 passes the test but is composite.

9.3 Factorization

  • Importance in cryptography; its difficulty ensures security in public-key systems.

  • Fundamental Theorem of Arithmetic: Every integer > 1 either is prime or can be uniquely factored into primes, disregarding order.

9.3.2 Factorization Methods

  • Trial Division Method: Iteratively test possible factors.

  • Fermat’s Method: Based on expressing n as the difference of two squares.

  • Pollard Method: Uses properties of modular arithmetic to find factors.

9.4 Chinese Remainder Theorem

  • CRT can solve simultaneous congruences with relatively prime moduli.

  • Example solutions demonstrate combining steps:

    1. Find M = product of moduli.

    2. Calculate M_i = M/m_i and find their inverses.

    3. Final solution combines components modular M.

9.5 Quadratic Congruence

9.5.1 Modulo a Prime

  • The quadratic residue definition and checking solutions.

  • Example equations exhibit solutions in prime moduli.

9.6 Exponentiation and Logarithm

  • Discuss fast exponentiation using square-and-multiply methods; critical for computational efficiency.

  • Modular Logarithm: Exhaustive search methods discussed for finding logarithmic values in mod contexts.

Summary

  • The topics of primes, factorization, and testing are interwoven within the foundation of cryptography, particularly influencing algorithms in public key systems, through operations based on modular arithmetic and number theory.