Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.5
- 1 min- Return to index
- Exercise 1.1
- Exercise 1.2
- Exercise 1.3
- Exercise 1.4
- Exercise 1.5
- Exercise 1.6
- Exercise 1.7
- Exercise 1.8
- Exercise 1.9
- Exercise 1.10
- Exercise 1.11
- Exercise 1.12
- Exercise 1.13
- Exercise 1.14
Exercise 1.5
As we learned in this chapter, modular arithmetic is the basis of many cryptosystems. As a consequence, we will address this topic with several problems in this and upcoming chapters.
Compute the result without a calculator:
- 15 · 29 mod 13
- 2 · 29 mod 13
- 2 · 3 mod 13
- −11 · 3 mod 13
The results should be given in the range from 0,1,…, modulus-1. Briefly describe the relation between the different parts of the problem.
Solution
This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.
We can compute these by reducing the individual terms (since all members of an equivalence class behave the same), performing the arithmetic and then reducing the result:
1. \(15 \times 29\,\mathrm{mod}\,13 \equiv 2 \times 3\,\mathrm{mod}\,13 \equiv 6\,\mathrm{mod}\,13\)
2. \(2 \times 29\,\mathrm{mod}\,13 \equiv 2 \times 3\,\mathrm{mod}\,13 \equiv 6\,\mathrm{mod}\,13\)
3. \(2 \times 3\,\mathrm{mod}\,13 \equiv 6\,\mathrm{mod}\,13\)
4. \(-11 \times 3\,\mathrm{mod}\,13 \equiv 2 \times 3\,\mathrm{mod}\,13 \equiv 6\,\mathrm{mod}\,13\)
Thomas Busby
I write about computing stuff