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

Saturday. 16 December 2017 - 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:

x = 3² mod 13
x = 7² mod 13
x = 3¹⁰ mod 13
x = 7¹⁰⁰ mod 13
7^x = 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:

\[3^2\,\mathrm{mod}\,13 \equiv 9\,\mathrm{mod}\,13\]

\[7^2\,\mathrm{mod}\,13 \equiv 49\,\mathrm{mod}\,13 \equiv 10\,\mathrm{mod}\,13\]

\[3^{10}\,\mathrm{mod}\,13 \equiv 9^5\,\mathrm{mod}\,13 \equiv 81^2 \times 9\,\mathrm{mod}\,13 \\ \equiv\,3^2 \times 9\,\mathrm{mod}\,13\equiv81\,\mathrm{mod}\,13\equiv3\,\mathrm{mod}\,13\]

\[7^{100}\,\mathrm{mod}\,13\] \[\equiv {7^2}^{50}\,\mathrm{mod}\,13\] \[\equiv 49^{50}\,\mathrm{mod}\,13\] \[\equiv 10^{50}\,\mathrm{mod}\,13\] \[\equiv {10^2}^{25}\,\mathrm{mod}\,13\] \[\equiv 100^{25}\,\mathrm{mod}\,13\] \[\equiv 9^{25}\,\mathrm{mod}\,13\] \[\equiv {9^2}^{12} \times 9\,\mathrm{mod}\,13\] \[\equiv 81^{12} \times 9\,\mathrm{mod}\,13\] \[\equiv 3^{12} \times 9\,\mathrm{mod}\,13\] \[\equiv {3^3}^{4} \times 9\,\mathrm{mod}\,13\] \[\equiv 27^{4} \times 9\,\mathrm{mod}\,13\] \[\equiv 1^{4} \times 9\,\mathrm{mod}\,13\] \[\equiv 9\,\mathrm{mod}\,13\]

5. Through trial and error, we can discover the value of \(x\):

\[7^5\,\mathrm{mod}\,13 \equiv 11\,\mathrm{mod}\,13\]

Previous Exercise Next Exercise

Thomas Busby

I write about computing stuff