Note: Due to changes in the Riesel prime template, most of those pages (and related) are not shown properly.
This will take some time!
Wanna help? Please move any Riesel prime page first, then edit/add the base parameter.
Navigation
Topics Register • News • History • How to • Sequences statistics • Template prototypes

Modular arithmetic

From Prime-Wiki
Jump to: navigation, search

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/12Z.

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/nZ of numbers modulo n contains the numbers 0, 1, 2, 3, ..., n-2 and n-1. The following operations are defined:

Modular addition

Let A and B be numbers in Z/nZ. 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).

  1. Set i = q, h = n, v = 0, and d = 1.
  2. Set t = i DIV h, where DIV is defined as integer division.
  3. Set x = h.
  4. Set h = i - tx.
  5. Set i = x.
  6. Set x = d.
  7. Set d = v - tx.
  8. Set v = x.
  9. If h > 0, go to step 2.
  10. 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:

  1. Set x = 1.
  2. 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]

External links