https://www.rieselprime.de/z/index.php?title=Modular_arithmetic&feed=atom&action=historyModular arithmetic - Revision history2024-03-28T20:43:54ZRevision history for this page on the wikiMediaWiki 1.31.1https://www.rieselprime.de/z/index.php?title=Modular_arithmetic&diff=428&oldid=prevKarbon: restored2019-01-23T10:25:38Z<p>restored</p>
<p><b>New page</b></p><div>'''Modular arithmetic''' is the set of operations that can be done when working modulo N, where N is an [[integer]] greater than 1.<br />
<br />
Since almost all [[Factorization|factorization methods]] and [[Primality test|primality tests]] use modular arithmetic, reading this article is a prerequisite to understanding those methods.<br />
<br />
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&times;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 <b>Z</b>/12<b>Z</b>.<br />
<br />
When making these modular operations, the equal symbol is not used. We use the congruence symbol (<math>\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''.<br />
<br />
The set <b>Z</b>/n<b>Z</b> of numbers modulo n contains the numbers 0, 1, 2, 3, ..., n-2 and n-1. The following operations are defined:<br />
<br />
===Modular addition===<br />
Let A and B be numbers in <b>Z</b>/n<b>Z</b>. Then the addition is defined as:<br />
:<math>A + B \equiv C</math> (mod <math>n</math>)<br />
where:<br />
:<math>C = A + B</math> if <math>A + B < n</math><br />
:<math>C = A + B - n</math> if <math>A + B \geq n</math><br />
<br />
===Modular subtraction===<br />
The subtraction is defined as:<br />
:<math>A - B \equiv C</math> (mod <math>n</math>)<br />
where:<br />
:<math>C = A - B</math> if <math>A \geq B</math><br />
:<math>C = A - B + n</math> if <math>A < B</math><br />
<br />
===Modular multiplication===<br />
The multiplication is defined as:<br />
:<math>A * B \equiv C</math> (mod <math>n</math>)<br />
where C is the remainder of the division between A &times; B and n.<br />
<br />
===Modular exponentiation===<br />
The exponentiation is defined as:<br />
:<math>A^B \equiv C</math> (mod <math>n</math>)<br />
where <math>C = A*A*A*A*...*A</math> (B times). An efficient method to perform modular exponentiation is the binary method.<br />
<br />
Since reducing modulo <math>n</math> takes a lot of time, [[Montgomery multiplication]] is used in this context where only one modular reduction is needed.<br />
<br />
===Modular inversion===<br />
The inverse is defined as:<br />
:<math>A^{-1} \equiv B</math> (mod <math>n</math>)<br />
where B is the number such that <math>A * B = 1</math> (mod <math>n</math>).<br />
<br />
This operation is only defined when the numbers A and n are [[coprime]], i.e., when [[greatest common divisor|gcd]](A, n) = 1.<br />
<br />
The following algorithm to compute the multiplicative inverse n<sup>-1</sup> 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'').<br />
<br />
#Set i = q, h = n, v = 0, and d = 1.<br />
#Set t = i DIV h, where DIV is defined as integer division.<br />
#Set x = h.<br />
#Set h = i - tx.<br />
#Set i = x.<br />
#Set x = d.<br />
#Set d = v - tx.<br />
#Set v = x.<br />
#If h > 0, go to step 2.<br />
#Let n<sup>-1</sup> = v mod q.<br />
<br />
When the modulus is a power of 2, there is an easier method. Let the modulus be <math>2^m</math>, let the number to be inverted be <math>N</math> and let <math>k = \log_2 m</math> rounded to the next integer. Then the method is:<br />
<br />
# Set x = 1.<br />
# Perform k times: Set x = x(2-Nx) mod 2^m<br />
<br />
===Modular division===<br />
The division is defined as:<br />
:<math>A / B \equiv C</math> (mod <math>n</math>)<br />
where:<br />
:<math>C \equiv A * B^{-1}</math><br />
<br />
==External links==<br />
*[https://en.wikipedia.org/wiki/Modular_arithmetic Wikipedia]<br />
[[Category:Math]]</div>Karbon