Main content
Computer science
Course: Computer science > Unit 2
Lesson 5: Modular arithmetic- What is modular arithmetic?
- Modulo operator
- Modulo Challenge
- Congruence modulo
- Congruence relation
- Equivalence relations
- The quotient remainder theorem
- Modular addition and subtraction
- Modular addition
- Modulo Challenge (Addition and Subtraction)
- Modular multiplication
- Modular multiplication
- Modular exponentiation
- Fast modular exponentiation
- Fast Modular Exponentiation
- Modular inverses
- The Euclidean Algorithm
© 2023 Khan AcademyTerms of usePrivacy PolicyCookie Notice
Fast modular exponentiation
How can we calculate A^B mod C quickly if B is a power of 2 ?
Using modular multiplication rules:
i.e. A^2 mod C = (A * A) mod C = ((A mod C) * (A mod C)) mod C
We can use this to calculate 7^256 mod 13 quickly
7^1 mod 13 = 7
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
7^2 mod 13 = (7^1 *7^1) mod 13 = (7^1 mod 13 * 7^1 mod 13) mod 13
We can substitute our previous result for 7^1 mod 13 into this equation.
7^2 mod 13 = (7 *7) mod 13 = 49 mod 13 = 10
7^2 mod 13 = 10
7^2 mod 13 = 10
7^4 mod 13 = (7^2 *7^2) mod 13 = (7^2 mod 13 * 7^2 mod 13) mod 13
We can substitute our previous result for 7^2 mod 13 into this equation.
7^4 mod 13 = (10 * 10) mod 13 = 100 mod 13 = 9
7^4 mod 13 = 9
7^4 mod 13 = 9
7^8 mod 13 = (7^4 * 7^4) mod 13 = (7^4 mod 13 * 7^4 mod 13) mod 13
We can substitute our previous result for 7^4 mod 13 into this equation.
7^8 mod 13 = (9 * 9) mod 13 = 81 mod 13 = 3
7^8 mod 13 = 3
7^8 mod 13 = 3
We continue in this manner, substituting previous results into our equations.
...after 5 iterations we hit:
7^256 mod 13 = (7^128 * 7^128) mod 13 = (7^128 mod 13 * 7^128 mod 13) mod 13
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
7^256 mod 13 = (3 * 3) mod 13 = 9 mod 13 = 9
7^256 mod 13 = 9
This has given us a method to calculate A^B mod C quickly provided that B is a power of 2.
However, we also need a method for fast modular exponentiation when B is not a power of 2.
How can we calculate A^B mod C quickly for any B ?
Step 1: Divide B into powers of 2 by writing it in binary
Start at the rightmost digit, let k=0 and for each digit:
- If the digit is 1, we need a part for 2^k, otherwise we do not
- Add 1 to k, and move left to the next digit
Step 2: Calculate mod C of the powers of two ≤ B
5^1 mod 19 = 5
5^2 mod 19 = (5^1 * 5^1) mod 19 = (5^1 mod 19 * 5^1 mod 19) mod 19
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^2 mod 19 = (5 * 5) mod 19 = 25 mod 19
5^2 mod 19 = 6
5^4 mod 19 = (5^2 * 5^2) mod 19 = (5^2 mod 19 * 5^2 mod 19) mod 19
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^4 mod 19 = (6 * 6) mod 19 = 36 mod 19
5^4 mod 19 = 17
5^8 mod 19 = (5^4 * 5^4) mod 19 = (5^4 mod 19 * 5^4 mod 19) mod 19
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^8 mod 19 = (17 * 17) mod 19 = 289 mod 19
5^8 mod 19 = 4
5^16 mod 19 = (5^8 * 5^8) mod 19 = (5^8 mod 19 * 5^8 mod 19) mod 19
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^16 mod 19 = (4 * 4) mod 19 = 16 mod 19
5^16 mod 19 = 16
5^32 mod 19 = (5^16 * 5^16) mod 19 = (5^16 mod 19 * 5^16 mod 19) mod 19
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^32 mod 19 = (16 * 16) mod 19 = 256 mod 19
5^32 mod 19 = 9
5^64 mod 19 = (5^32 * 5^32) mod 19 = (5^32 mod 19 * 5^32 mod 19) mod 19
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
5^64 mod 19 = (9 * 9) mod 19 = 81 mod 19
5^64 mod 19 = 5
Step 3: Use modular multiplication properties to combine the calculated mod C values
5^117 mod 19 = ( 5^1 * 5^4 * 5^16 * 5^32 * 5^64) mod 19
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
5^117 mod 19 = ( 5^1 mod 19 * 5^4 mod 19 * 5^16 mod 19 * 5^32 mod 19 * 5^64 mod 19) mod 19
5^117 mod 19 = ( 5 * 17 * 16 * 9 * 5 ) mod 19
5^117 mod 19 = 61200 mod 19 = 1
5^117 mod 19 = 1
Notes:
More optimization techniques exist, but are outside the scope of this article. It should be noted that when we perform modular exponentiation in cryptography, it is not unusual to use exponents for B > 1000 bits.
Want to join the conversation?
Is there a tutorial/challenge for writing numbers in binary? If not that would be a great addition!(32 votes)
This link no longer works. Is there another video perhaps?(6 votes)
Why isn't this math on the learning dashboard, say in the world of math mission?(18 votes)
what if the exponent has four digits(2 votes)
In Notes They said that if B>1000 some good technique is used.
so what is the name of that techniques?(4 votes)
Could one take the 5^117mod19=(5*17*16*9*5)mod 19 and make it equal to ((5*17)mod19)*(16*9)mod19*5mod19)mod19?(5 votes)
What if the modulo operation has some exponent ?? For example-
1000 mod 17^2.
Is there any way to simplify it?(3 votes)- Given: 'A mod B'
Typically, it isn't a big issue if B is large, because if A < B then 'A mod B = A'
On the other hand, if A is large then we do need techniques to simplify 'A mod B', because we don't have such a simple result.
That being said, in certain circumstances, it may be useful to break B into coprime factors and find A mod each coprime factor and reassemble them again using the Chinese Remainder Theorem. (This, however, would not allow you to split up B if it was a prime taken to an exponent, as each of the factors would not be coprime to eachother)(3 votes)
So basically, 8 bit binary would represent if numbers like are in the whole number (going to use semicolons to space things):
128 : 64 : 32 : 16 : 8 : 4 : 2 : 1
0 0 0 0 0 0 0 0
So writing 112 would look like:
01110000
Since 64 + 32 + 16 = 112 since I included those numbers in the..... binary snippet?
Is my calculation correct?(3 votes)- Yes,it is correct.(1 vote)
Can anyone tell how to convert digits into binary?(2 votes)- Here's the lessons for converting between bases:
https://www.khanacademy.org/math/pre-algebra/applying-math-reasoning-topic/alternate-number-bases/v/number-systems-introduction
Here is specifically for decimal to binary
(you may need to look at the videos earlier on in the lessons for converting between bases to understand it ) :
https://www.khanacademy.org/math/pre-algebra/applying-math-reasoning-topic/alternate-number-bases/v/decimal-to-binary(4 votes)
I was doing some RSA exercises and had a problem when solving modular exponentiation. For example, 978^325 mod 1711. I tried the method above but it is still somehow hard to calculate. Is there any faster way to deal with it? Or did I miss some other important mathematical background of modular exponentiation so that it makes me feel hard to solve?(2 votes)- It still requires some work, but it is a lot less working than trying to calculate 978^325 ( which would be a ridiculously big number) and then finding the value of the result mod 1711.
Writing a program to automate the process also helps.(3 votes)
Why do we convert 117 into binary? How does that work?(1 vote)- We convert the exponent (in this case 117) into binary because we can quickly calculate the x^y mod C if y is a power of 2. The article shows that we can do this by repeatedly taking squares mod C
i.e. x^(2 * y) mod C = (x^y mod C * x^y mod C) mod C.
To take advantage of that, we break our number (in this case 5^117) into the product of x^y where y is a power of 2.
We then combine the result using the properties of modular multiplication
Hope this makes sense(5 votes)