9

I am trying to implement the SAFER+ algorithm. The algorithm requires finding the modulus of a power function as follows:

pow(45, x) mod 257

The variable x is a byte, and thus can range from 0 to 255. Accordingly, the result of the power function can be VERY big resulting in incorrect values if implemented using 32- or 64-bit integers.

How can I perform this calculation?

AakashM
  • 62,551
  • 17
  • 151
  • 186
Eng. Aws
  • 169
  • 1
  • 2
  • 7
  • 1
    @esskar: If I'm not completely mistaken and remember correctly that there are special formulas for computing powers in modulus spaces, modulus calculus is the important part of the question, so the question is language-agnostic. – thiton Nov 27 '11 at 16:48
  • Introductory reading: [The multiplicative group of integers](http://en.wikipedia.org/wiki/Multiplicative_group_of_integers_modulo_n#Powers_of_odd_primes). This is too long ago for me to answer, but maybe someone remembers. – thiton Nov 27 '11 at 16:50
  • There's a SAFER+ implementation written in C which you can study here: http://www.schneier.com/book-applied-source.html – Robert Harvey Nov 27 '11 at 16:51

4 Answers4

23

some pseudo code

function powermod(base, exponent, modulus) {
    if (base < 1 || exponent < 0 || modulus < 1)
        return -1

    result = 1;
    while (exponent > 0) {
       if ((exponent % 2) == 1) {
           result = (result * base) % modulus;
       }
       base = (base * base) % modulus;
       exponent = floor(exponent / 2);
    }
    return result;
}

and call

powermod(45, x, 257)
esskar
  • 10,638
  • 3
  • 36
  • 57
13

Perform the exponentiation by repeated squaring, reducing by the modulus after each operation. This is a very standard technique.

A worked example: 45^13 mod 257:

  1. First compute 45^2, 45^4, 45^8 mod 257:

    45^2 mod 257 = 2025 mod 257 = 226

    45^4 mod 257 = 226^2 mod 257 = 51076 mod 257 = 190

    45^8 mod 257 = 190^2 mod 257 = 36100 mod 257 = 120

  2. Then use the binary expansion of 13 to combine these to get the result:

    45^13 mod 257 = 45^1 * 45^4 * 45^8 mod 257

    45^13 mod 257 = 45 * 190 * 120 mod 257

    45^13 mod 257 = 8550 * 120 mod 257

    45^13 mod 257 = 69 * 120 mod 257

    45^13 mod 257 = 8280 mod 257

    45^13 mod 257 = 56

Note that the intermediate results of the computation are never larger than 257*257, so this can easily be performed in a 32-bit integer type.

Stephen Canon
  • 103,815
  • 19
  • 183
  • 269
5

The basic approach is to square-or-multiply depending on the exponent bit, and perform the modular reduction at each step. The algorithm is called (binary) modular exponentiation.

Brett Hale
  • 21,653
  • 2
  • 61
  • 90
3

Consider the simple identity:

mod(A^2,p) = mod(A,p)*mod(A,p)

Also note that

A^4 = (A^2)^2

Other powers are trivially computed if you know the binary representation of the final exponent you wish to compute.