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

- 1 min

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:

  1. 15 · 29 mod 13
  2. 2 · 29 mod 13
  3. 2 · 3 mod 13
  4. −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.


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

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