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

- 1 min

## Exercise 1.9

Compute $x$ 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 $x$: