The order of a modulo p

The Order of a Modulo p

Introduction to The Order of a Modulo p

  • The order of an integer modulo p is a basic concept in number theory.
  • It’s essentially the number of times we need to multiply the integer by itself in order to get a result equivalent to 1 modulo p.

What is Modulo?

  • To understand the order of a modulo p, one must be familiar with modular arithmetic.
  • The modulo of two numbers is the remainder of the Euclidean division of these numbers.
  • This means for numbers a and b, a modulo b (written as a mod b) is the remainder when a is divided by b.
  • If a = qp + r, where q and r are integers, then “a mod p” is equal to r.

Representation and Example

  • The order of a modulo p, for a positive integer a and prime number p, is denoted by “ord_p(a)”.
  • For example, let’s consider a=2 and p=7. The powers of 2 mod 7 are 2, 4, 1, 2, 4, 1, and so on. So, ord_7(2) = 3.

Fermat’s Little Theorem

  • Fermat’s little theorem is crucial to understanding the order of a modulo p.
  • The theorem states: If p is a prime number, then for any a, where 1 ≤ a ≤ (p-1), if we raise a to the power of (p-1) and then divide by p, the remainder we get is 1. In other words, a^(p-1) mod p = 1.

Euler’s Theorem and Euler’s Totient Function

  • Euler’s theorem is the generalisation of Fermat’s Little Theorem.
  • The theorem states: If a and m are integers with gcd(a, m) = 1 (i.e. a and m are coprime), then a^ϕ(m) mod m = 1, where ϕ(m) is Euler’s totient function, which counts the positive integers less than m that are relatively prime to m.
  • When m is a prime p, Euler’s theorem becomes Fermat’s Little Theorem because ϕ(p) = p-1 for any prime p.

Applications of Order in Cryptography

  • The ability to compute the order of an element modulo p is used in several cryptographic protocols.
  • Public key cryptography, such as RSA and ElGamal encryption, rely heavily on the difficulty of certain computations in modulo arithmetic.
  • Primality testing and integer factorisation are dependent on understanding the concept of the order of a modulo p.

Problems and Exercises

  • Solving problems related to determining the order of a modulo p, Euler’s theorem, Fermat’s little theorem, and Euler’s totient function will enhance your understanding of the topic.
  • Ensure you understand the underlying concepts beyond the formula, and can apply them to different problems in context.