Modularization

Raising to a power modulo is one of the operations on natural numbers - raising to a power , - performed modulo . Finds application in computer science , especially in the field of public key cryptography .

Modular exponentiation is the calculation of the remainder of dividing a positive integer b (base) raised to a power n ( exponent ) by a positive integer m (modulus). It is designated:

$c\equiv b^{n}{\pmod {m}}$ ${\ displaystyle c \ equiv b ^ {n} {\ pmod {m}}}$ ${\ displaystyle c \ equiv b ^ {n} {\ pmod {m}}}$

For example, let us be given b = 5, n = 3 and m = 13, then the solution c = 8 is the remainder of the division $5^{3}$ ${\ displaystyle 5 ^ {3}}$ $5 ^ {3}$ at 13.

If b , n and m are non-negative and b < m , then a unique solution c exists, and 0 ⩽ c < m .

Modularization can also be performed with a negative exponent n. To do this, find the number d inverse to b modulo m . This is easily done using the Euclidean algorithm . In this way,

c\equiv b^{n}\equiv d^{\left|n\right|}{\pmod {m}}

{\ displaystyle c \ equiv b ^ {n} \ equiv d ^ {\ left | n \ right |} {\ pmod {m}}}

{\ displaystyle c \ equiv b ^ {n} \ equiv d ^ {\ left | n \ right |} {\ pmod {m}}}

where n <0 and

b\cdot d\equiv 1{\pmod {m}}

{\ displaystyle b \ cdot d \ equiv 1 {\ pmod {m}}}

b \ cdot d \ equiv 1 {\ pmod {m}}

Modulo is pretty easy, even with large input values. But the calculation of the discrete logarithm , that is, finding the exponent n for given b , c and m , is much more complicated. This one-way behavior of a function makes it a candidate for use in cryptographic algorithms.

Content

Simple Method

The easiest way to raise to a power modulo is to directly calculate the number $b^{n}$ ${\ displaystyle b ^ {n}}$ , and then finding the remainder of dividing this number by m . We calculate c if b = 4, n = 13 and m = 497:

c\equiv 4^{13}{\pmod {497}}

{\ displaystyle c \ equiv 4 ^ {13} {\ pmod {497}}}

You can use the calculator to calculate 4 ¹³ , we get 67,108,864. Now take this number modulo 497 and get 445.

It should be noted that b has only one character in length, n has only two characters in length, and the value of b ⁿ has 8 characters in length.

In cryptography, b often has 256 bits (77 decimal digits). Consider b = 5 × 10 ⁷⁶ and e = 17, they both take on very real values. In this example, b is 77 characters long and n is 2 characters long, but the result of exponentiation is 1304 characters long. Such calculations are possible on modern computers, but the speed of computing such numbers is slow. The values of b and n are increased to achieve a greater level of security, which makes the value of b ⁿ cumbersome.

The time required for exponentiation depends on the operating system and processor. The method described above requires O ( e ⁿ ) multiplications.

A memory efficient method

This method requires more operations than the previous one. However, since memory is required less and operations take less time, the algorithm works much faster.

This algorithm is based on the fact that for given a and b, the following 2 equations are equivalent:

c\equiv (a\cdot b){\pmod {m}}

{\ displaystyle c \ equiv (a \ cdot b) {\ pmod {m}}}

c\equiv (a\cdot (b\ ({\mbox{mod}}\ m))){\pmod {m}}

{\ displaystyle c \ equiv (a \ cdot (b \ ({\ mbox {mod}} \ m))) {\ pmod {m}}}

The algorithm is as follows:

Let c = 1, n ′ = 0.
Increase n by 1.
Install $c\equiv (b\cdot c){\pmod {m}}$ ${\ displaystyle c \ equiv (b \ cdot c) {\ pmod {m}}}$ .
If n ′ <n, we return to step 2. Otherwise, c contains the correct answer $c\equiv b^{n}{\pmod {m}}$ ${\ displaystyle c \ equiv b ^ {n} {\ pmod {m}}}$ .

It should be noted that with each pass of step 3, the expression $c\equiv b^{n'}{\pmod {m}}$ ${\ displaystyle c \ equiv b ^ {n '} {\ pmod {m}}}$ right. After step 3 has been performed n times, c contains the desired value. Thus, the algorithm is based on counting n ′ until n ′ reaches e and multiplying by b modulo m in each turn of the loop (to ensure that the result is small).

For example, b = 4, n = 13 and m = 497. The algorithm goes through step 3 thirteen times.

n ′ = 1. c = (1 * 4) mod 497 = 4 mod 497 = 4 .
n ′ = 2. c = (4 * 4) mod 497 = 16 mod 497 = 16 .
n ′ = 3. c = (16 * 4) mod 497 = 64 mod 497 = 64 .
n ′ = 4. c = (64 * 4) mod 497 = 256 mod 497 = 256 .
n ′ = 5. c = (256 * 4) mod 497 = 1024 mod 497 = 30 .
n ′ = 6. c = (30 * 4) mod 497 = 120 mod 497 = 120 .
n ′ = 7. c = (120 * 4) mod 497 = 480 mod 497 = 480 .
n ′ = 8. c = (480 * 4) mod 497 = 1920 mod 497 = 429 .
n ′ = 9. c = (429 * 4) mod 497 = 1716 mod 497 = 225 .
n ′ = 10. c = (225 * 4) mod 497 = 900 mod 497 = 403 .
n ′ = 11. c = (403 * 4) mod 497 = 1612 mod 497 = 121 .
n ′ = 12. c = (121 * 4) mod 497 = 484 mod 497 = 484 .
n ′ = 13. c = (484 * 4) mod 497 = 1936 mod 497 = 445 .

The final answer c is 445, as in the first method.

As in the first method, O ( e ′ ⁿ ) multiplications are required to complete. However, since the numbers used in these calculations are much smaller, the execution time of this algorithm is reduced.

In pseudo code, it looks like this:

  function modular_pow (base, index_n, modulus)
     c: = 1
     for index_n_prime = 1 to index_n 
         c: = (c * base) mod modulus
     return c

Modular Fast Extensibility Algorithm

Using the fast exponentiation algorithm for 595 ⁷⁰³ (mod 991 ):

We have n = 703 = (1010111111) ₂ = 2 ⁰ +2 ¹ +2 ² +2 ³ +2 ⁴ +2 ⁵ + 2 ⁷ +2 ⁹ .

595 ⁷⁰³ = ((((((((595 ² ) ² * 595) ² ) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= (((((((238 ² * 595) ² ) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= (((((((261 ² ) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= ((((((733 ² * 595) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= ((((((167 * 595) ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= (((((265 ² * 595) ² * 595) ² * 595) ² * 595) ² * 595

= (((342 ² * 595) ² * 595) ² * 595) ² * 595

= ((605 ² * 595) ² * 595) ² * 595

= (733 ² * 595) ² * 595

= (167 * 595) ² * 595

= 265 ² * 595

= 342 .

Right-to-Left Scheme

Another option is a right-to-left scheme. It can be represented by the following formula:

$d=a^{n}=$ ${\ displaystyle d = a ^ {n} =}$

$=a^{\sum _{i=0}^{k}m_{i}*2^{i}}=$ ${\ displaystyle = a ^ {\ sum _ {i = 0} ^ {k} m_ {i} * 2 ^ {i}} =}$

$=a^{m_{0}}*a^{2m_{1}}*a^{2^{2}*m_{2}}*...*a^{2^{k}*m_{k}}=$ ${\ displaystyle = a ^ {m_ {0}} * a ^ {2m_ {1}} * a ^ {2 ^ {2} * m_ {2}} * ... * a ^ {2 ^ {k} * m_ {k}} =}$

$=a^{m_{0}}*(a^{2})^{m_{1}}*(a^{2^{2}})^{m_{2}}*...*(a^{2^{k}})^{m_{k}}=$ ${\ displaystyle = a ^ {m_ {0}} * (a ^ {2}) ^ {m_ {1}} * (a ^ {2 ^ {2}}) ^ {m_ {2}} * ... * (a ^ {2 ^ {k}}) ^ {m_ {k}} =}$

$=\prod _{i=0}^{k}{(a^{2^{i}})^{m_{i}}}$ ${\ displaystyle = \ prod _ {i = 0} ^ {k} {(a ^ {2 ^ {i}}) ^ {m_ {i}}}}$

An example . Using a simple binary scheme of raising to a power of the “right to left” type, we calculate the value 175 ²³⁵ mod 257 .

Imagine the number 235 in binary form:

235 ₁₀ = 11101011 ₂ .

1 . d: = 1 * 175 mod 257 = 175,

t: = 175 ² mod 257 = 42;

2 . d: = 175 * 42 mod 257 = 154,

t: = 42 ² mod 257 = 222;

3 . t: = 222 ² mod 257 = 197;

4 . d: = 154 * 197 mod 257 = 12,

t: = 197 ² mod 257 = 2;

5 . t: = 2 ² mod 257 = 4;

6 . d: = 12 * 4 mod 257 = 48,

t: = 4 ² mod 257 = 16;

7 . d: = 48 * 16 mod 257 = 254,

t: = 16 ² mod 257 = 256;

8 . d: = 254 * 256 mod 257 = 3,

9 . → d = 3. It took 7 squared and 6 multiplications.

Matrices

The Fibonacci numbers modulo n can be effectively found by calculating A ^m (mod n) for a certain m and a certain matrix A. The listed methods can be easily applied in this algorithm. This provides a good simplicity test for large (500 bit) n numbers.

Pseudo-code

The recurrence algorithm for ModExp (A, b, c) = A ^b (mod c), where A is a square matrix.

  matrix ModExp (matrix A, int b, int c) {
    if (b == 0) return I;  // Unit matrix
    if (b% 2 == 1) return (A * ModExp (A, b-1, c))% c; 
    matrix D = ModExp (A, b / 2, c);
    return (D * D)% c;
 }

Finiteness of cyclic groups

The Diffie-Hellman key exchange uses exponentiation in finite cyclic groups. The above method of raising a matrix to a power fully extends to cyclic groups. Matrix multiplication modulo C = AB (mod n) is simply replaced by group multiplication c = ab .

Reverse and quantum exponentiation modulo

In quantum computing, exponentiation modulo is part of the Shore algorithm . Also, in this algorithm, you can find out the basis and exponent for each call, which allow various modifications of the circuit ^[3] .

In programming languages

Modularization is an important operation in computer science and there are efficient algorithms (see above), which are much faster than a simple raising to a degree and subsequent taking of the remainder. In programming languages, there are libraries that contain a special function for raising to a power modulo:

Python contains a built-in pow () function ^[4]
The .NET Framework contains the BigInteger class, which includes ModPow () ^[5]
Java contains the java.math.BigInteger class, which includes modPow () ^[6]
Perl contains a Math :: BigInt module that includes the bmodpow () method ^[7]
Go contains a big.Int type that includes the Exp () method ^[8]
PHP contains the BC Math library, which includes the bcpowmod () function ^[9]
The GNU Multi-Precision Library (GMP) library contains the mpz_powm () function ^[10]

Notes

↑ Theoretical minimum and digital signature algorithms, 2010 , p. 56-57.
↑ Schneier 1996 , p. 244.
↑ Igor L. Markov, Mehdi Saeedi, “Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation”, Quantum Information and Computation, Vol. 12, No. 5 & 6, pp. 0361-0394, 2012. http://arxiv.org/abs/1202.6614
↑ Built-in Functions: official site .
↑ BigInteger.ModPow Method: official site .
↑ Class BigInteger: official site .
↑ Math :: BigInt: official site .
↑ Package big: official site .
↑ bcpowmod: official site .
↑ Exponentiation Functions: official site .

Literature

Moldovyan N. A. Theoretical minimum and digital signature algorithms. - SPb. : BVH-Petersburg: Book House "LIBROCOM", 2010. - 304 p. - ISBN 978-5-9775-0585-7 .
Schneier, Bruce. Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition. - 2nd. - Wiley, 1996 .-- ISBN 978-0-471-11709-4 .
Valitskas A. I. Lecture notes on discipline: Elements of abstract and computer algebra. // Tobolsk , TSPI them. D.I. Mendeleev , 2004 .
Gabidulin E. M, Kshevetsky A. S, Kolybelnikov A. I, Vladimirov S. M. Information Security (Tutorial): Modularization (p. 253) // MIPT , 2014.

[_7e8222600cd9f359-1] Theoretical minimum and digital signature algorithms, 2010 , p. 56-57.

[schneier96p244-2] Schneier 1996 , p. 244.

[3] Igor L. Markov, Mehdi Saeedi, “Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation”, Quantum Information and Computation, Vol. 12, No. 5 & 6, pp. 0361-0394, 2012. http://arxiv.org/abs/1202.6614

[4] Built-in Functions: official site .

[5] BigInteger.ModPow Method: official site .

[6] Class BigInteger: official site .

[7] Math :: BigInt: official site .

[8] Package big: official site .

[9] wmod: official site .

[10] Exponentiation Functions: official site .