# 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.