Need help on computing both of these questions. Compute 3^25 mod 35 using the al

Question

Need help on computing both of these questions.

Compute 3^25 mod 35 using the algorithm given on page 254 of the text for (fast) Modular Exponentiation (also discussed in class). Compute 3^205 mod 99 using the algorithm given on page 254 of the text for (fast) Modular Exponentiation (also discussed in class). The algorithm successively finds b mod m, b^2 mod m, b^4 mod m, ... and multiplies together those terms b^2j mod m where a_j = 1, finding of the product when divided by m after each multiplication. Pseudocode for is shown in Algorithm 5. Note that in Algorithm 5 we can use the most available to compute values of the mod function, not necessarily Algorithm 4. procedure modular exponentiation (b: integer, n = (a_K-1ak_2 ... a_1a_0)2, m: positive integers) x:= 1 power:= b mod m for i:= 0 to k - 1 if at = 1 then x:= (x middot power) mod m power:= (power middot power) mod m return equals b^n mod m} We illustrate how Algorithm 5 works in Example 12.

Explanation / Answer

Let us do a dry run, you will get your answer :)

a.

325 mod 35
therefore we have
      a4...a0 = 11001
      b = 3
      m = 35
      power = b mod m = 3
      x = 1

11 * 11 mod 35
= 121 mod 35
= 16

3 * 16 mod 35
= 48 mod 35
= 13

Therefore answer = 3

b.

3205 mod 99
therefore we have
      a7...a0 = 11001101
      b = 3
      m = 99
      power = b mod m = 3
      x = 1

Therefore the answer is 45
Hopefully this is clear enough!

i ai x power 1 3 0 1 1 * 3 mod 35
=3 mod 35
= 3 3 * 3 mod 35
= 9 mod 35
= 9 1 0 3 (No change) 9 * 9 mod 35
= 81 mod 35
= 11 2 0 3 (No change)

11 * 11 mod 35
= 121 mod 35
= 16

3 1

3 * 16 mod 35
= 48 mod 35
= 13

16 * 16 mod 35
=256 mod 35
=11 4 1 13 * 11 mod 35
=143 mod 35
=3 11 * 11 mod 35
= 121 mod 35
= 16

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.