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