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

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

Compute without a calculator:

1. 1/5 mod 13
2. 1/5 mod 7
3. 3 · 2/5 mod 7

Solution

I haven’t yet verified this solution independently. If you spot any mistakes, please leave a comment in the Disqus box at the bottom of the page.

In order to perform a division by $x$, we must find the multiplicative inverse $x^{-1}$ and multiply by it.

1.

$$1 \div 5\,\mathrm{mod}\,13 \equiv 1 \times 5^{-1}\,\mathrm{mod}\,13 \\ \mathsf{where}\,5 \times 5^{-1} \,\mathrm{mod}\,13 \equiv 1\,\mathrm{mod}\,13$$ $$5 \times 8\,\mathrm{mod}\,13 \equiv 1\,\mathrm{mod}\,13 \\ 5^{-1}\,\mathrm{mod}\,13 \equiv 8\,\mathrm{mod}\,13$$ $$1 \div 5\,\mathrm{mod}\,13 \equiv 1 \times 8\,\mathrm{mod}\,13 \equiv 8\,\mathrm{mod}\,13$$

2.

$$1 \div 5\,\mathrm{mod}\,7 \equiv 1 \times 5^{-1}\,\mathrm{mod}\,7 \\ \mathsf{where}\,5 \times 5^{-1} \,\mathrm{mod}\,7 \equiv 1\,\mathrm{mod}\,7$$ $$5 \times 3\,\mathrm{mod}\,7 \equiv 1\,\mathrm{mod}\,7 \\ 5^{-1}\,\mathrm{mod}\,7 \equiv 3\,\mathrm{mod}\,7$$ $$1 \div 5\,\mathrm{mod}\,7 \equiv 1 \times 3\,\mathrm{mod}\,7 \equiv 3\,\mathrm{mod}\,7$$

3.

$$3 \times 2 \div 5\,\mathrm{mod}\,7 \equiv 3 \times 2 \times 5^{-1}\,\mathrm{mod}\,7 \\ \mathsf{where}\,2 \times 5^{-1} \,\mathrm{mod}\,7 \equiv 1\,\mathrm{mod}\,7$$ $$5 \times 3\,\mathrm{mod}\,7 \equiv 1\,\mathrm{mod}\,7 \\ 5^{-1}\,\mathrm{mod}\,7 \equiv 3\,\mathrm{mod}\,7$$ $$3 \times 2 \div 5\,\mathrm{mod}\,7 \equiv 3 \times 2 \times 3\,\mathrm{mod}\,7 \equiv 4\,\mathrm{mod}\,7 \\ \mathsf{because}\,3 \times 2 \times 3\,\mathrm{mod}\,7 \equiv 18\,\mathrm{mod}\,7 \equiv 4\,\mathrm{mod}\,7$$

---

Thomas Busby

I write about computing stuff

Tweet Share