PDF4PRO ⚡AMP

Modern search engine that looking for books and documents around the web

Example: bankruptcy

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.

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-

Loading..

Tags:

  Solutions, Chinese, Math, Homework, Theorem, Remainder, Chinese remainder theorem, Math 110 homework 3 solutions

Information

Domain:

Source:

Link to this page:

Please notify us if you found a problem with this document:

Spam in document Broken preview Other abuse

Transcription of Math 110 Homework 3 Solutions

Related search queries