PDF4PRO ⚡AMP

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

Example: biology

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

Loading..

Tags:

  Solutions, 2015, Math, Homework, 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