Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.9

- 1 min

Exercise 1.9

Compute as far as possible without a calculator. Where appropriate, make use of a smart decomposition of the exponent as shown in the example in Sect. 1.4.1:

  1. x = 32 mod 13
  2. x = 72 mod 13
  3. x = 310 mod 13
  4. x = 7100 mod 13
  5. 7x = 11, mod 13

The last problem is called a discrete logarithm and points to a hard problem which we discuss in Chap. 8. The security of many public-key schemes is based on the hardness of solving the discrete logarithm for large numbers, e.g., with more than 1000 bits.

Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

These can be performed by performing a smaller exponentiation and reducing:

1.

2.

3.

4.

5. Through trial and error, we can discover the value of :


Thomas Busby

Thomas Busby

I write about computing stuff

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora