DOC PREVIEW
MIT 6 006 - Modular Exponentiation

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

6.006 Intro to Algorithms Recitation 22 April 29, 2011Modular ExponentiationModular exponentiation is the problem of finding an efficient way of computing abmod n. Mod-ular exponentiation is applicable in many security measures, such as RSA. The naive approachto computing abmod n would be to calculate a mod n and then multiplying the result by a anadditional b − 1 times. This method requires using O(b) multiplications to get the intended result.One key observation to make is that we can create shortcuts by squaring results instead ofmultiplying by a one at a time. For example, if we want to calculate a10 mod n and we’ve alreadycalculated a5mod n, instead of multiplying the result by a 5 more times, we can square a5toget a10, getting to our intended result in just one multiplication instead of five. Squaring doublesthe exponent while multiplying increases the exponent by 1. Using a combination of squaring andmultiplying will result in modular exponentiation using O(log b) multiplications to get the intendedresult.To figure out what order of squaring/multiplying we want to execute, it helps to take a look atthe binary representation of b. Given a binary representation of b, (bk, bk−1, ..., b1, b0), we iteratethrough the digits of b from most significant to least significant. Every time we see a 1 digit, thatmeans we must multiply. Every time we see a 0 digit, we don’t multiply. Then, to shift to the nextbinary digit, we square the result. For example, to solve abmod n where b = 10, we break down binto its binary representation 1010. Then we just iterate through the binary representation:Start with 1 mod n (1)b3= 1, (1 ∗ a) mod n = a mod n (2)Shift to b2, (a)2mod n = a2mod n (3)b2= 0, a2mod n (4)Shift to b1, (a2)2mod n = a4mod n (5)b1= 1, (a4∗ a) mod n = a5mod n (6)Shift to b0, (a5)2mod n = a10mod n (7)b0= 0, a10mod n (8)Parallel AdditionAdding two n-bit numbers the naive way involves adding the least significant digits together, car-rying over a 1 if necessary, then repeating for all the other digits iteratively until all n bits havebeen added together. In this method, we cannot compute the ith bit of the sum before computingall the bits after it first since the ith bit depends on whether or not there was a carry involved.With a carry lookahead adder, we can add two n-bit numbers in O(lg n) time by taking ad-vantage of some clever anticipation of carries and parallelization. For the purposes of this recitationthough, we won’t go over the inner details of how it does this, though you can look online if you’reinterested in more details.6.006 Intro to Algorithms Recitation 22 April 29, 2011Instead, we’ll look at the carry-save adder, that allows us to reduce the problem of addingthree n-bit numbers to the problem of adding two n-bit numbers efficiently. Say the problem isto add three n-bit numbers, i.e. x + y + z. We will reduce this to the problem of adding twon-bit numbers, u + v. u is going to represent the sum of x, y, z ignoring all carries. v is going torepresent just the carries of x, y, z. For example:0 0 0 1 1 1 0 1 = x1 1 0 0 0 1 0 1 = y1 0 0 1 0 1 1 0 = z--------------------0 1 0 0 1 1 1 0 = u1 0 0 1 0 1 0 1 = vNote that u and v can be computed completely independently from each other. Before we wereconcerned about whether or not the sum would be impacted by carries or not, but now that we’vecompletely separated the carries from the actual addition, we can compute u and v separately. Notonly that, each digit of u and v can be computed separately.• ui= parity(xi, yi, zi) (= xi+ yi+ zimod 2)• vi+1= majority(xi, yi, zi) (= 0 if there are more 0s than 1s, =1 if there are more 1s than 0s)With this observation, if we have n separate processes that can compute parity and majority,we can compute u and v in O(1) time since u and v both have O(n) bits. Once we’ve reducedthe three sum problem to the two sum problem, we can use our carry lookahead adder to finishthe job. Note that even though we can make O(1) time reductions to the two sum problem, ourrunning time is still O(lg n) because of the bottleneck of the carry lookahead adder at the very end.Asymptotically, this isn’t better than using two carry lookahead adders to calculate x + y and then(x + y) + z, but practically it is faster since we’re using fewer carry lookahead additions.The speed up is even more apparent if we are trying to add n n-bit numbers together. Likebefore, we will try to make O(1) time reductions until we have reduced the problem into addingtwo n-bit numbers together, from where we can use a carry lookahead adder to finish the job.The idea is to use a Wallace tree to keep applying the same 3-to-2 sum reductions until theproblem has been reduced to a sum of two numbers. At every step, if we have k sum problem, wecan use approximately k/3 carry-save adders to reduce the problem to an approximately 2k/3 sumproblem. Below is an example of what the tree may look like.6.006 Intro to Algorithms Recitation 22 April 29, 2011Since each carry-save adder removes one sum from the problem, we will need O(n) carry-saveadders to reduce the problem down to a two sum problem. Then we apply a single O(lg n) timecarry lookahead adder to finish the sum. Since all the carry-save adders take O(1) time assumingn processors, the total runtime of summing n n-bit numbers is


View Full Document

MIT 6 006 - Modular Exponentiation

Documents in this Course
Quiz 1

Quiz 1

7 pages

Quiz 2

Quiz 2

12 pages

Quiz 2

Quiz 2

9 pages

Quiz 1

Quiz 1

10 pages

Quiz 2

Quiz 2

11 pages

Quiz 1

Quiz 1

12 pages

Graphs

Graphs

27 pages

Load more
Download Modular Exponentiation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Modular Exponentiation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Modular Exponentiation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?