2.1 Number theory and modular arithmetic

Number theory and modular arithmetic are the building blocks of modern cryptography. These mathematical concepts provide the foundation for secure communication and data protection in our digital world.

From prime numbers to modular operations, these tools enable the creation of complex encryption algorithms. Understanding these principles is crucial for grasping how cryptographic systems work and why they're so effective at keeping our information safe.

Fundamental Concepts of Number Theory

Divisibility and Prime Numbers

Top images from around the web for Divisibility and Prime Numbers

• 

  Prime Numbers Demystified by 8-Dimensional Algorithms View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime Numbers Demystified by 8-Dimensional Algorithms View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Divisibility and Prime Numbers

• 

  Prime Numbers Demystified by 8-Dimensional Algorithms View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

• 

  Prime Numbers Demystified by 8-Dimensional Algorithms View original

  Is this image relevant?

• 

  Prime number - Wikipedia View original

  Is this image relevant?

1 of 2

• Number theory focuses on properties of integers and their relationships, forming the foundation for many cryptographic algorithms
• Divisibility occurs when an integer a can be expressed as a product of another integer b and some integer k, such that a = b * k
• Prime numbers have exactly two factors (1 and themselves)
  • Fundamental theorem of arithmetic states every positive integer uniquely factors into a product of primes
• Greatest common divisor (GCD) represents the largest positive integer that divides two or more integers without a remainder
  • Crucial concept in number theory with applications in cryptography (key generation)

Modular Arithmetic Basics

• Modular arithmetic involves numbers "wrapping around" after reaching a certain value called the modulus
  • Essential for many cryptographic operations (encryption, digital signatures)
• Modulo operation finds the remainder after division of one number by another
  • Forms the basis of modular arithmetic and congruence relations
  • Example: 17 mod 5 = 2, because 17 ÷ 5 = 3 remainder 2
• Congruence relations state two numbers are congruent modulo n if their difference divides by n
  • Written as a ≡ b (mod n)
  • Example: 23 ≡ 8 (mod 5), because 23 - 8 = 15, which is divisible by 5

Euclidean Algorithm and Applications

Euclidean Algorithm and GCD Computation

• Euclidean algorithm efficiently computes the greatest common divisor (GCD) of two integers
  • Based on the principle that GCD(a,b) = GCD(b, a mod b)
  • Example: To find GCD(48, 18)
    1. 48 = 2 * 18 + 12
    2. 18 = 1 * 12 + 6
    3. 12 = 2 * 6 + 0
    4. GCD(48, 18) = 6
• Extended Euclidean algorithm finds GCD and coefficients of Bézout's identity
  • Expresses GCD as a linear combination of the two original numbers
  • GCD(a,b) = sa + tb, where s and t are integers
  • Example: For GCD(48, 18) = 6, we can find s = -1 and t = 3 such that 6 = -148 + 318

Solving Linear Congruences

• Linear congruences take the form ax ≡ b (mod m), where a, b, and m are known integers and x is unknown
• Extended Euclidean algorithm solves linear congruences by finding modular multiplicative inverse of a modulo m
  • Solution exists if and only if GCD(a,m) divides b
• Chinese Remainder Theorem solves systems of simultaneous linear congruences with coprime moduli
  • Useful in various cryptographic protocols (secret sharing, RSA)
• Modular multiplicative inverse crucial in cryptography, particularly in RSA encryption for private key computation
  • a^(-1) mod n exists if and only if a and n are coprime
  • Satisfies the equation a * a^(-1) ≡ 1 (mod n)

Arithmetic in Modular Systems

Basic Modular Operations

• Modular addition and subtraction involve adding or subtracting operands then taking result modulo n
  • Ensures result remains within range [0, n-1]
  • Example: (14 + 23) mod 10 ≡ 37 mod 10 ≡ 7
• Modular multiplication multiplies operands then takes result modulo n
  • Essential in many cryptographic algorithms (RSA, ElGamal)
  • Example: (7 * 8) mod 13 ≡ 56 mod 13 ≡ 4
• Modular exponentiation raises a number to a power in modular arithmetic
  • Fundamental operation in public-key cryptography
  • Efficiently computed using square-and-multiply algorithm
  • Example: 3^5 mod 7 ≡ 243 mod 7 ≡ 5

Advanced Modular Concepts

• Distributive property holds in modular arithmetic: (a + b) mod n ≡ ((a mod n) + (b mod n)) mod n
  • Important for simplifying complex modular expressions
• Fermat's Little Theorem states if p is prime and a not divisible by p, then a^(p-1) ≡ 1 (mod p)
  • Used in primality testing and RSA algorithm
  • Example: For p = 5 and a = 2, 2^4 ≡ 1 (mod 5)
• Euler's theorem generalizes Fermat's Little Theorem: if a and n are coprime, then a^φ(n) ≡ 1 (mod n)
  • φ(n) is Euler's totient function, counting numbers less than n coprime to n
  • Example: For n = 9 and a = 2, φ(9) = 6, and 2^6 ≡ 1 (mod 9)

Number Theory in Cryptography

Public-Key Cryptosystems

• Number theory provides mathematical foundation for modern cryptographic systems, especially public-key cryptography
• RSA cryptosystem bases security on difficulty of factoring large composite numbers into prime factors
  • Widely used public-key encryption algorithm
  • Example: Public key (n,e), private key d, where n = pq (p and q are large primes)
• Discrete logarithm problem underlies cryptosystems like ElGamal and Diffie-Hellman key exchange
  • Difficulty of finding x in equation g^x ≡ y (mod p) given g, y, and p
  • Example: In Diffie-Hellman, shared secret computed as (g^a)^b ≡ (g^b)^a (mod p)

Cryptographic Applications

• Primality testing utilizes number-theoretic concepts for generating keys in public-key cryptosystems
  • Uses Fermat's Little Theorem and Miller-Rabin test
  • Example: Miller-Rabin test checks if n is prime by verifying a^(n-1) ≡ 1 (mod n) for multiple bases a
• Security of many cryptographic protocols depends on computational intractability of certain number-theoretic problems
  • Integer factorization (RSA)
  • Discrete logarithm problem (ElGamal, Diffie-Hellman)
• Modular exponentiation extensively used in public-key cryptography
  • Encryption, decryption, and digital signatures
  • Example: In RSA, encryption of message m is c = m^e mod n, decryption is m = c^d mod n
• Trapdoor one-way functions central to public-key cryptography
  • Easy to compute in one direction, difficult to reverse without special information
  • Example: RSA encryption function easy to compute, but decryption without private key is computationally infeasible