Fastest algorithm to compute (a^(2^N))%m?

Question

There are well-known algorithms for cryptography to compute modular exponentiation (a^b)%c (like Right-to-left binary method here : http://en.wikipedia.org/wiki/Modular_exponentiation).

But do algorithm exist to compute modular exponentiation of the form (a^(2^N))%m faster than with "classical" algorithms ?

Thank you very much !

Note :

1) m can be a very large prime ... or not (so no optimization depending on m)

2) N can be as large as 2^32-1 (N < 2^32)

Ledoux

Did you know that Ronald L. Rivest's LCS35 Time Capsule Crypto-Puzzle is based on this problem? And that this problem was chosen because it is an inherently serial computation. Although it uses (2^(2^N))%m. – Batson

Note that if you know the factorization of M, you can compute the answer faster than exponentiation. – Batson

Answer 1

If m is a prime, you can compute this much faster.

You start with computing of p = 2^N % (m-1) with right-to-left binary method.

Then you use right-to-left binary method to compute a^p % m, which is equal to the original expression because of Fermat's little theorem.

---

If m is not prime, but small enough, so that it can be factored, you can compute Euler's totient function and use Euler's Theorem.

If no optimization depending on m is possible, probably the best you can do is using Montgomery reduction.

Meter

Answer 2

Also, as a generalization to Evgeny's answer: if you know the factorization of m: m = p1 * p2 * ... * p{n}, you can use Euler's theorem:

Calculate the totient phi(m)= (p1-1)*(p2-1)*...*(p{n}-1).

Then you can compute p = 2^N % phi(m) and find that a^(2^N) % m = a^p % m.

None of this uses the special form of 2^N, however.

Ornithology

Answer 3

Evgeny and Rasmus give great answers. To add to that, remember to use successive squaring for the powers. That is, write the exponent, say E, in base 2:

E = b0*1 + b1*2 + ... + bk*2^k

where each bi is either 0 or 1 and bk = 1 is the last nonzero bit. Then you can raise a number, say N, to the exponent E by

N^E (mod m) = n0^b0 * n1^b1 * ... * nk^bk (mod m)

where

n0 = N (mod m)
n1 = n0^2 (mod m)
n2 = n1^2 (mod m)
...
nk = n(k-1)^k (mod m)

For example, to compute 28^27 mod 76, you have N = 28, E = 27, m = 76, and the computation is

27 =  1 +  2 +  8 + 16
 E = b0 + b1 + b3 + b4

and

n0 = 28 (mod 76) 
n1 = 28^2 (mod 76) = 24
n2 = 24^2 (mod 76) = 44
n3 = 44^2 (mod 76) = 36
n4 = 36^3 (mod 76) =  4

and finally

28^27 (mod 76) = 28 * 24 * 36 *  4 (mod 76) = 20
 N^ E (mod  m) = n0 * n1 * n3 * n4 (mod 76)

Cementation

Answer 4

if you're using any platform that has 64-bit double-prec floating point as the underlying representation of numbers, e.g. Javascript or awk,

you can do 28^27 % 76 in very very few steps :

                 28 = a
                 76 = m
 10,578,455,953,408 = v = a^9

 28^27 % 76 := ( a^9     )^3 % m
             = ( a^9 % m )^3 % m
             = (   v % m )^3 % m
             -------------------
             = ( 20 )^3 % 76
             =  8000    % 76 
             ---------------
             =            20

or as a single end to end equation without overflowing :

( 28^9 % 76 )^3 % 76

An entirely different approach would be realizing both 28 and 76 are congruent to 0 (mod 4), making the underlying expression

 7^27 % 19 * 4^(27-1) % 19 * 4

since 7^3 % 19 => 1 (** 1), the entire piece of 7^27 % 19 goes to just 1, and you're simply calculating

 4^26 % 19 * 4

   4^26 % 19 * 4          4^27     % 76
 =         5 * 4      = ( 4^ 3 )^9 % 76
 ---------------   or = (  -12 )^9 % 76
 =            20      = (  -56 )^3 % 76
                      = (   20 )^3 % 76
                      -----------------
                      =              20
   

** 1 :

     7^3 + 19 = 343 + 19 = 362 =  19^2 + 1
                               =         1 (mod 19)

     7^3 - 19 = 343 - 19 = 324 =  18^2

                                 (18)^2    (mod 19)
                               = (-1)^2    (mod 19)
                               =         1 (mod 19)

Jammiejammin