Desert Rose: Modular exponentiation

Dec 13, 2012

Modular exponentiation

A second method to compute modular exponentiation requires more operations than the first method. Because the required memory is substantially less, however, operations take less time than before. The end result is that the algorithm is faster.
This algorithm makes use of the fact that, given two integers a and b, the following two equations are equivalent:

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

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

The algorithm is as follows:

Set c = 1, e′ = 0.
Increase e′ by 1.
Set $c \equiv (b \cdot c) \pmod{m}$ .
If e′ < e, goto step 2. Else, c contains the correct solution to $c \equiv b^e \pmod{m}$ .

Note that in every pass through step 3, the equation $c \equiv b^{e'} \pmod{m}$ holds true. When step 3 has been executed e times, then, c contains the answer that was sought. In summary, this algorithm basically counts up e′ by ones until e′ reaches e, doing a multiply by b and the modulo operation each time it adds one (to ensure the results stay small).
The example b = 4, e = 13, and m = 497 is presented again. The algorithm passes through step 3 thirteen times:

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

The final answer for c is therefore 445, as in the first met
The final answer for c is therefore 445, as in the first method.
Like the first method, this requires O(e) multiplications to complete. However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor of at least O(e) in this method.
In pseudocode, this method can be performed the following way:

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

wiki reference

Desert Rose

Dec 13, 2012

Modular exponentiation

No comments:

Game engines