Currently there may be errors shown on top of a page, because of a missing Wiki update (PHP version and extension DPL3). |

**Navigation**

Topics | Register • News • History • How to • Sequences statistics • Template prototypes |

# Modular arithmetic

**Modular arithmetic** is the set of operations that can be done when working modulo N, where N is an integer greater than 1.

Since almost all factorization methods and primality tests use modular arithmetic, reading this article is a prerequisite to understanding those methods.

We can visualize this arithmetic using a clock. Suppose that the number 12 in the clock is replaced by zero. Then when we have to add an hour, we get, for example: 3+1 = 4, 10+1 = 11, 11+1 = 0. If we have to add three hours we get: 5+3 = 8, 11+3 = 2 (as in 11 AM + 3 hours = 2 PM). We can also subtract: 2-3 = 11 and even multiply: 5×4 = 8 (because 5+5+5+5 = 8). This is arithmetic modulo 12 and the set of numbers representing the hours 0, 1, 2, 3,..., 11 is known as **Z**/12**Z**.

When making these modular operations, the equal symbol is not used. We use the congruence symbol ([math]\displaystyle{ \equiv }[/math]) instead. Note that two numbers *A* and *B* are said to be congruent modulo *n* if *A*-*B* is a multiple of *n*.

The set **Z**/n**Z** of numbers modulo n contains the numbers 0, 1, 2, 3, ..., n-2 and n-1. The following operations are defined:

## Contents

### Modular addition

Let A and B be numbers in **Z**/n**Z**. Then the addition is defined as:

- [math]\displaystyle{ A + B \equiv C }[/math] (mod [math]\displaystyle{ n }[/math])

where:

- [math]\displaystyle{ C = A + B }[/math] if [math]\displaystyle{ A + B \lt n }[/math]
- [math]\displaystyle{ C = A + B - n }[/math] if [math]\displaystyle{ A + B \geq n }[/math]

### Modular subtraction

The subtraction is defined as:

- [math]\displaystyle{ A - B \equiv C }[/math] (mod [math]\displaystyle{ n }[/math])

where:

- [math]\displaystyle{ C = A - B }[/math] if [math]\displaystyle{ A \geq B }[/math]
- [math]\displaystyle{ C = A - B + n }[/math] if [math]\displaystyle{ A \lt B }[/math]

### Modular multiplication

The multiplication is defined as:

- [math]\displaystyle{ A * B \equiv C }[/math] (mod [math]\displaystyle{ n }[/math])

where C is the remainder of the division between A × B and n.

### Modular exponentiation

The exponentiation is defined as:

- [math]\displaystyle{ A^B \equiv C }[/math] (mod [math]\displaystyle{ n }[/math])

where [math]\displaystyle{ C = A*A*A*A*...*A }[/math] (B times). An efficient method to perform modular exponentiation is the binary method.

Since reducing modulo [math]\displaystyle{ n }[/math] takes a lot of time, Montgomery multiplication is used in this context where only one modular reduction is needed.

### Modular inversion

The inverse is defined as:

- [math]\displaystyle{ A^{-1} \equiv B }[/math] (mod [math]\displaystyle{ n }[/math])

where B is the number such that [math]\displaystyle{ A * B = 1 }[/math] (mod [math]\displaystyle{ n }[/math]).

This operation is only defined when the numbers A and n are coprime, i.e., when gcd(A, n) = 1.

The following algorithm to compute the multiplicative inverse n^{-1} mod q for n with 0 < n < q, where 0 < n-1 < q is based on the Extended Euclidean algorithm. All variables are integers (some programming languages call them *Big Integers*).

- Set i = q, h = n, v = 0, and d = 1.
- Set t = i DIV h, where DIV is defined as integer division.
- Set x = h.
- Set h = i - tx.
- Set i = x.
- Set x = d.
- Set d = v - tx.
- Set v = x.
- If h > 0, go to step 2.
- Let n
^{-1}= v mod q.

When the modulus is a power of 2, there is an easier method. Let the modulus be [math]\displaystyle{ 2^m }[/math], let the number to be inverted be [math]\displaystyle{ N }[/math] and let [math]\displaystyle{ k = \log_2 m }[/math] rounded to the next integer. Then the method is:

- Set x = 1.
- Perform k times: Set x = x(2-Nx) mod 2^m

### Modular division

The division is defined as:

- [math]\displaystyle{ A / B \equiv C }[/math] (mod [math]\displaystyle{ n }[/math])

where:

- [math]\displaystyle{ C \equiv A * B^{-1} }[/math]