3: Please clearly show how to compute 2144 mod 101 (without applying Fermat's Little Theorem or...

 

Transcribed Image Text:

3: Please clearly show how to compute 2144 mod 101 (without applying Fermat's Little Theorem or Euler's Theorem, if you already know them) using no more than 8 multiplications in Z/(101). Hint: It will turn out to be helpful to know the base 2 expansion of 101. Also, you might want to warm up with count how many squarings you need to compute 22, 24, and 28... 4: Consider the function ƒ : (Z/(43)) → (Z/(43)) defined by f(x) = 7x + 3. (Such a function is an example of a method of encryption called an affine cipher, combining the simpler ideas of adding or multiplying mod n.) For the example at hand, what function g would yield g(f(x)) = x for all x = {0,..., 42}? Hint: If you were over the rational numbers then this would be very easy. Perhaps you can do the same algebra over Z/(43), since you know fractions can sometimes be well-defined in Z/(N)? 3: Please clearly show how to compute 2144 mod 101 (without applying Fermat's Little Theorem or Euler's Theorem, if you already know them) using no more than 8 multiplications in Z/(101). Hint: It will turn out to be helpful to know the base 2 expansion of 101. Also, you might want to warm up with count how many squarings you need to compute 22, 24, and 28... 4: Consider the function ƒ : (Z/(43)) → (Z/(43)) defined by f(x) = 7x + 3. (Such a function is an example of a method of encryption called an affine cipher, combining the simpler ideas of adding or multiplying mod n.) For the example at hand, what function g would yield g(f(x)) = x for all x = {0,..., 42}? Hint: If you were over the rational numbers then this would be very easy. Perhaps you can do the same algebra over Z/(43), since you know fractions can sometimes be well-defined in Z/(N)?

Answer rating: 100% (QA)

3To answer the first question we can use the base 2 expansion of 101 to compute 2144 mod 101 with fe... View the full answer