Math 110 Homework 3 Solutions
math 110 Homework 3 SolutionsJanuary 29, 20151. (a) Describe the method in Section for efficiently computing exponentialsab(modn), and verifythe book s claim that this can be done in at most 2 log2(b) multiplications.(b) Use this method to compute 3172(mod 191).Solution:(a) The basic idea is thata2mcan be calculated inm 1 multiplications, asa2m a2m 1 a2m 1(modn) so you can multiply the exponent by two by doing one multiplication. In general, writeb=cm 2m+cm 1 2m 1+...+c12 +c0whereci {0,1}. Then computea,a2,a4,...,a2m(modn)by multiplying the previous element in this list with itself. This takesm 1 multiplications. Finallycomputeacm2m acm 12m 1 ... a2c1 ac0 ab(modn)This requires at mostmmultiplications, as each term is either 1 or one of the precomputeda2i.
January 29, 2015 1. (a) Describe the method in Section 3.5 for e ciently computing exponentials ab (mod n), and verify the book’s claim that this can be done in at most 2log 2 (b) multiplications. (b) Use this method to compute 3172 (mod 191). Solution: (a) The basic idea is that a2m can be calculated in m 1 multiplications, as a2m a2m 1 a2m 1
Download Math 110 Homework 3 Solutions
Information
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document: