PDF4PRO ⚡AMP

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

Example: marketing

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. Notethatmis the integer part of log2(b), so we need at most 2 log2(b) multiplications.(b) For example, 172 = 128 + 32 + 8 + 4, and34 81 (mod 191)38 67 (mod 191)316 96 (mod 191)332 48 (mod 191)364 12 (mod 191)3128 144 (mod 191)Therefore we combine these to see that3172 144 48 67 81 170 (mod 191).

Math 110 Homework 3 Solutions 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).

Loading..

Tags:

  Solutions, 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