Transcription of Math 110 Homework 3 Solutions
{{id}} {{{paragraph}}}
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.
By the Chinese Remainder Theorem, we already knew that the map (Z=mnZ) ! (Z=mZ) (Z=nZ) c(mod nm) 7! c(mod m) ;c(mod n) is one-to-one and onto. Now we know that it maps every unit c(mod mn) to a pair of units c(mod m) ;c(mod n) , and conversely that every pair of units is in the image of a unit c(mod mn). We conclude that the map re-
Domain:
Source:
Link to this page:
Please notify us if you found a problem with this document:
{{id}} {{{paragraph}}}