6 Modular Exponentiation
Dr Kulothungan
Learning Objectives
Ø To review the concept of Modular Exponentiation
Ø To define the purpose of Modular Exponentiation in cryptography
Ø To discuss about the inverse multiplication
Ø To understand these concepts with some examples
7.1 Introduction
Modular exponentiation is an exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography.
Consider the following scenario,
AB mod C = ( (A mod C)B ) mod C
Often we want to calculate AB mod C for large values of B.
Unfortunately, AB becomes very large for even modest sized values for B.
For Example:
290 = 1237940039285380274899124224
7256 = 221359540004604815545018861547494593716251705026007306991636639052470
4974007989996848003433
837940380782794455262312607598867363425940560014856027866381946458951
20583737911647366324673350968 0721264246243189632348313601
These huge values cause our calculators and computers to return overflow errors and also it would take a long time to find the mod of these huge numbers directly.In order to implement exponentiation relative some modulo needs to be done a lot. So this operation better be doable, and fast.
7.2 Fast Modular Exponentiation
For real-life needs of number theoretic computations, just raising numbers to large exponents isn’t very useful, because extremely huge numbers start appearing very quickly, and these don’t have much use. What’s much more useful is modular exponentiation, raising integers to high powers . In such case, we can reuse the efficient algorithms developed in the previous article, with very few modifications to perform modular exponentiation as well. This is possible because of some convenient properties of modular arithmetic. In order to implement exponentiation relative some modulo needs to be done a lot. So this operation better be doable, and fast.
1) Q: How is it even possible to compute 28533397 mod 4559 ?
After all, 28533397 has approximately 3397·4 digits!
A: By taking the mod after each multiplication.
example:
233 mod 30 = -73 (mod 30)
= (-7)2 ·(-7) (mod 30) 49 · (-7) (mod 30) 19·(-7) (mod 30) -133 (mod 30)
=17 (mod 30)
Therefore, 233 mod 30 = 17.
2) Q: What if had to figure out 2316 mod 30. Same way tedious: need to multiply 15 times. Is there a better way?
A: Better way. Notice that 16 = 2·2·2·2 so that 2316 = 232·2·2·2 = (((232)2)2)2
Therefore:
2316 mod 30 (((-72)2)2)2 (mod 30)
=(((49)2)2)2 (mod 30)= (((-11)2)2)2 (mod 30)
=((121)2)2 (mod 30) =((1)2 )2 (mod 30)
=(1)2 (mod 30) = 1(mod 30)
Which implies that 2316 mod 30 = 1.
3) Q: How about 2325 mod 30 ?
A: The previous method of repeated squaring works for any exponent that’s a power of 2. 25. However, we can break 25 down as a sum of such powers: 25 = 16 + 8 + 1. Apply repeated squaring to each part, and multiply the results together. Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30 2316+8+1 (mod 30)
The previous method of repeated squaring works for any exponent that’s a power of
2. 25. However, we can break 25 down as a sum of such powers: 25 = 16 + 8 + 1. Apply repeated squaring to each part, and multiply the results together. Previous calculation:
238 mod 30 = 2316 mod 30 = 1
Thus: 2325 mod 30 2316+8+1 (mod 30) 2316·238·231 (mod 30) 1·1·23 (mod 30)
Final answer: 2325 mod 30 = 23
4) Q: How could we have figured out the decomposition 25 = 16 + 8 + 1 from the binary (unsigned) representation of 25?
A: 25 = (11001)2 This means that
25 = 1·16+1·8+0·4+0·2+1·1 = 16+8+1
Can tell which powers of 2 appear by where the 1’s are. This follows from the definition of binary representation.
7.3 Properties of Modular Arithmetic
1. [(a mod n) + (b mod n)] mod n = (a + b) mod n
2. [(a mod n) – (b mod n)] mod n = (a – b) mod n
3. [(a mod n) x (b mod n)] mod n = (a x b) mod n
7.3.1 Proof of property 1.
Let (a mod n) = Ra and (b mod n) = Rb. Then, we can write a = Ra + jn for some integer j and b = Rb + kn for some integer k.
(a + b) mod n = (Ra + jn + Rb + kn) mod n
= [Ra + Rb + (k + j) n] mod n
= (Ra + Rb) mod n
= [(a mod n) + (b mod n)] mod n
7.3.2 Example
11 mod 8 = 3; 15 mod 8 = 7
[(11 mod 8 ) + (15 mod 8)] mod 8 = 10 mod 8 = 2
(11 + 15) mod 8 = 26 mod 8 = 2
[(11 mod 8 ) – (15 mod 8)] mod 8 = -4 mod 8 = 4
(11 – 15) mod 8 = -4 mod 8 = 4
[(11 mod 8 ) x (15 mod 8)] mod 8= 21 mod 8 = 5
(11 x 15) mod 8 = 165 mod 8 = 5
7.4 Exponentiation
Exponentiation is done by repeated multiplication, as in ordinary arithmetic. A good thing about modular arithmetic is that the numbers you are working with will be kept relatively small. At each stage of an algorithm, the mod function should be applied.
Thus to multiply 39 * 15 mod 11 we first take mods to get
39 mod 11 = 6 and 15 mod 11= 4
The multiplication required is now
6*4 mod 11 = 24 mod 11 = 2
7.5 Modular Division
Modular division is defined when modular inverse of the divisor exists. The inverse of an integer ‘x’ is a another integer ‘y’ such that (x*y) % m = 1 where m is the modulus. When does inverse exist? Inverse a number ‘a’ exists under modulo ‘m’ if ‘a’ and ‘m’ are co-prime, i.e., GCD of them is 1.
What is 5 ÷ 3 mod 11?
A: We need to multiply 5 by the inverse of 3 mod 11.When you multiply a number by its inverse, the answer is 1.
Thus the inverse of 2 is ½ since 2* ½ = 1
The inverse of 3 mod 11 is 4 since 3*4=1 mod 11
Thus 5 ÷ 3 mod 11 = 5*4 mod 11 = 9 mod 11
7.6 Euclidean algorithm
The Euclidean algorithm or Euclid’s algorithm is an efficient method for computing the greatest common divisor (GCD) of two numbers, the largest number that divides both of them without leaving a remainder. It is named after the ancient Greek mathematician Euclid, who first described it in Euclid’s Elements (c. 300 BC). It is an example of an algorithm, a step-by-step procedure for performing a calculation according to well-defined rules, and is one of the oldest algorithms in common use. It can be used to reduce fractions to their simplest form, and is a part of many other number-theoretic and cryptographic calculations.
gcd(a,b) = gcd(b, b mod a)
int Euclid(int a, int b) {
if (b == 0) return a;
else return Euclid(b, b % a)
}
7.6.1 Finding Inverses in Zn
The numbers that have inverses in Zn are relatively prime to n. We can use the Euclidean Algorithm to see if a given “x” is relatively prime to “n”; then we know that an inverse does exist. How can we find the inverse without looking at all the remainders? A problem for large n.For example if we are trying to find x with 4 x ≡ 1 ( mod 13 ) 4x≡1(mod13). Since you already have 13 = 4 ⋅ 3 + 1 13=4⋅3+1, it follows that 4 ⋅ 3 ≡ − 1 ( mod 13 ) 4⋅3≡−1(mod13). That’s almost, but not quite what you need.
So let’s multiply left and right by -1. Then you get:
4 ⋅ − 3 ≡ 1 ( mod 13 )
4⋅−3≡1(mod13) Much closer.
It follows that 4−1≡−3≡10(mod13).
7.6.2 Using the Extended Euclidean Algorithm
The extended Euclidean algorithm is particularly useful when a and b are coprime, since x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a. Similarly, the polynomial extended Euclidean algorithm allows one to compute the multiplicative inverse in algebraic field extensions and, in particular in finite fields of non prime order. It follows that both extended Euclidean algorithms are widely used in cryptography.
- Formalizing the backward steps we get this formula:
y0 = 0
y1 = 1
yi = (yi-2 – [yi-1 * qi-2]); i > 1
Related to the “Magic Box” method
Using the Extended Euclidean Algorithm
y0 = 0
y1 = 1
yi = (yi-2 – [yi-1 * qi-2]); i > 1
Try it for…
1) 13 mod 22
2) 17 mod 97
A: 13 mod 22
22 = 1 * 13 + 9 y[0]=0
13 = 1 * 9 + 4 y[1]=1
9 = 2 * 4 + 1 y[2]=0 – 1 * 1 mod 22 = 21
4 = 4 * 1 + 0 y[3]=1 – 21 * 1 mod 22 = 2
Last Step: y[4]=21 – 2 * 2 mod 22 = 17
Check: 17 * 13 = 221 = 1 mod 22
A: 17 mod 97
97 = 5 * 17 + 12 x[0]=0
17 = 1 * 12 + 5 x[1]=1
12 = 2 * 5 + 2 x[2]=0 – 1 * 5 mod 97 = 92
5 = 2 * 2 + 1 x[3]=1 – 92 * 1 mod 97 = 6
2 = 2 * 1 + 0 x[4]=92 – 6 * 2 mod 97 = 80
Last Step: x[5]=6 – 80 * 2 mod 97 = 40
Check: 40 * 17 = 680 = 1 mod 97
Summary
- Outlined the purpose of Modular Exponentiation
- Discussed about the inverse multiplication and extended Euclidean
- Discussed about the fast exponentiation method
- Worked with various examples related with modular exponentiation and inverse.
| you can view video on Modular Exponentiation | |
