Modular Exponentiation
Dr. Arunachalam V
Associate Professor, SENSE
Introduction
• Modular exponentiation is the most time-consuming mathematical operation in
several cryptographic algorithms.
• The well-known RSA public-key cryptosystem is based on the fact that
computing = (1) is relatively easy, but recovering a from c, e
and N is difficult when N has at least two (unknown) large prime factors.
• The discrete logarithm problem is similar: here c, a and N are given, and one
looks for e satisfying Eqn. (1).
• In this case the problem is difficult when N has at least one large prime factor
(for example, N could be prime).
• The discrete logarithm problem is the basis of the El Gamal cryptosystem,
and a closely related problem is the basis of the Diffie-Hellman key exchange
protocol.
Chain of shortest length
• When the exponent e is fixed (or known to be small), an optimal sequence of
squarings and multiplications might be computed in advance.
• This is related to the classical addition chain problem: What is the smallest
chain of additions to reach the integer e, starting from 1? For example, if e =
15, a possible chain is: 1, 1 + 1 = 2, 1 + 2 = 3, 1 + 3 = 4, 3 + 4 = 7, 7 +
7 = 14, 1 + 14 = 15.
• The length of a chain is defined to be the number of additions needed to
compute it (the above chain has length 6).
• An addition chain readily translates to a multiplication chain: , ∙ = , ∙
= , ∙ = , ∙ = , ∙ = , ∙ = .
• A shorter chain for e = 15 is: 1, 1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 5 + 5 =
10, 5 + 10 = 15.
• This chain is the shortest possible for = 15, so we write 15 = 5, where
in general denotes the length of the shortest addition chain for e.
• In the case where e is small, and an addition chain of shortest length is
known for e, computing = may be performed in modular
multiplications.
Reduced modulo
• When e is large and (a,N) = 1, then e might be reduced modulo , where
is Euler’s totient function, i.e., the number of integers in [1,N] which are
relatively prime to N.
• This is because =1 whenever (a,N) = 1 (Fermat’s little
theorem).
• Since is a multiplicative function, it is easy to compute if we
know the prime factorisation of N.
• For example, 1001 = 7 ∙ 11 ∙ 13 = 7 − 1 11 − 1 13 − 1 = 720,
and 2009 = 569 720, so 17 = 17 1001.
• The different algorithms presented in this section save only a constant factor
compared to binary exponentiation.
• Remark: when a fits in one word but N does not, the shortest addition chain for
e might not be the best way to compute , since in this case
computing ∙ is cheaper than computing ∙ for ≥ 2.
Binary Exponentiation
• A simple (and not far from optimal) algorithm for modular exponentiation is
binary (modular) exponentiation.
• Two variants exist: left-to-right and right-to-left.
• Left-to-right binary exponentiation has two advantages over right-to-left
exponentiation:
• It requires only one auxiliary variable, instead of two for the right-to-left
exponentiation: one to store successive values of , and one to store the result;
• In the case where a is small, the multiplications ax at step 5 always involve a small
operand.
• If e is a random integer of + 1 bits, step 5 will be performed on average
/2 times, giving average cost 3 ( )/2.
• for the exponent e = 3 499 211 612, which is (1101 0000 1001 0001 1011
1011 0101 1100)2 in binary, Algorithm LeftToRightBinaryExp performs
31 squarings and 15 multiplications (one for each 1-bit, except the most
significant one).
Exponentiation With a Larger Base
• Example: consider the exponent = 3 499 211 612
• = 1101 0000 1001 0001 1011 0101 1100 . Algorithm BaseKExp performs
31 squarings independently of k.
• For k = 2, we have = 3 100 210 123 231130 : Algorithm BaseKExp
performs two multiplications to precompute and , and 11 multiplications for
the non-zero digits of e in base 4 (except for the leading digit), thus a total of 13.
• For k = 3, we have = 32 044 335 534 , and the algorithm performs 6
multiplications to precompute , , . . . , and 9 multiplications in step 6, thus a
total of 15.
BaseKexpOdd algorithm
• The last example illustrates two facts.
• First, if some digits (here 6 and 7) do not appear in the base-2 representation
of e, then we do not need to precompute the corresponding powers of a.
• Second, when a digit is even, say = 2, instead of doing three squarings and
multiplying by , we could do two squarings, multiply by a, and perform a
last squaring.
• These considerations lead to Algorithm BaseKExpOdd.
• The correctness of steps 7–9 follows from: =( )2 .
• On the previous example, with k = 3, this algorithm performs only four
multiplications in step 1 (to precompute then , , ), then nine
multiplications in step 8.
Reference
1. Chapter 2.6 of Richard P Brent and Paul Zimmerman, “Modern
Computer Arithmetic”, Cambridge University Press 2010.
Next Class
FLOATING POINT ARITHMETIC
Start reading the Chapters 17, 18, 19 and 20 of of Behrooz Parhami, “Computer
Arithmetic: Algorithms and Hardware Design”, (2/e) Oxford University Press 2015.
