IST 3/5/25

Modular Arithmetic

  • Modulus Definition: Modular arithmetic deals with integers wrapping around upon reaching a certain value, called the modulus.

  • Examples:

    • 0 mod 5 = 0

    • 1 mod 15 = 1, 1 mod 3 = 1, 1 mod 5 = 1

    • 2 mod 3 = 2, 2 mod 5 = 2

  • Wrapping Around:

    • For numbers greater than the modulus, they will start wrapping around.

    • Example:

      • 3 mod 3 = 0

      • 4 mod 3 = 1

      • 4 mod 5 = 4

      • 5 mod 3 = 2, 5 mod 5 = 0

Chinese Remainder Theorem

  • Theorem Overview: The Chinese Remainder Theorem states that if you have two or more moduli that are coprime, you can find a unique solution to simultaneous congruences.

  • Dimensional Representation:

    • The notation involves treating the problem as a one-dimensional representation, but it can correspond to a multi-dimensional structure.

    • Example using integers modulo 3 and 5 shows how they wrap around differently, leading to unique solutions.

  • Finding Solutions:

    • For instance, calculating 14 mod 3 = 2, 14 mod 5 = 4 corresponds to unique wrapping of congruences.

Cyclic Groups

  • Definition: A cyclic group is a group formed by rotating elements in a uniform way, generated by one element.

  • Group Formation:

    • Example with numbers on a clock (mod 12).

    • Clock numbers include 0 to 11, with various elements (like 1, 11) generating the entire group.

  • Identifying Generators:

    • Elements 1, 5, 7, and 11 are coprime to 12 and generate cyclic groups in this context.

Group Properties

  • Prime Factor Impact:

    • When numbers are not coprime, they wrap around simultaneously leading to less unique group formations.

  • Addition and Multiplication:

    • Understanding how different operations can generate elements is crucial for determining group characteristics.

Logarithmic Functions and Exponentiation

  • Definition: Logarithmic functions can invert exponentiation within a modular framework.

  • Trapdoor Functions: These are easy to compute one way (like multiplication or exponentiation) but difficult to reverse (like factoring or logarithm).

Fast Exponentiation

  • Process: Fast exponentiation avoids direct calculation of powers; instead using binary representations to achieve results through squaring.

  • Efficiency: Using this method drastically reduces the number of multiplications needed to calculate large power outcomes.

  • Importance of Modulus: Using a modulus in exponentiation ensures resultant calculations remain manageable in size.

Diffie-Hellman Key Exchange

  • Secure Key Agreement Protocol: Allows two parties to share a secret key without directly sending it across a public channel, which could be intercepted.

  • Process Overview:

    • Agree on a prime number and primitive root publicly.

    • Each party selects a secret number, calculates a public value, and exchanges it.

    • Eventually both parties compute the same secret key from the exchanged values without disclosing their secrets.

Applications in Cryptography

  • Secure Communications: The principles behind modular arithmetic and cyclic groups form the foundational elements behind various cryptographic practices, ensuring secure transmission of data online.

  • Trapdoor Information: Detecting prime factors or unravelling log relations is computationally intensive, making them suitable for secure communication protocols.