Understanding Cryptography by Christof Paar and Jan Pelzl - Chapter 1 Solutions - Ex1.8
- 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.8
What is the multiplicative inverse of 5 in \(\mathbb{Z}_{11}\), \(\mathbb{Z}_{12}\), and \(\mathbb{Z}_{13}\)? You can do a trial-and-error search using a calculator or a PC.
With this simple problem we want now to stress the fact that the inverse of an integer in a given ring depends completely on the ring considered. That is, if the modulus changes, the inverse changes. Hence, it doesn’t make sense to talk about an inverse of an element unless it is clear what the modulus is. This fact is crucial for the RSA cryptosystem, which is introduced in Chap. 7. The extended Euclidean algorithm, which can be used for computing inverses efficiently, is introduced in Sect. 6.3.
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.
These are small enough sets that you can find their inverses (\(5 \times 5^{-1} \equiv 1\,\mathrm{mod}\,n\)) by trial and error:
\[5^{-1}\,\mathrm{mod}\,11 \equiv 9\,\mathrm{mod}\,11 \\ 5^{-1}\,\mathrm{mod}\,12 \equiv 5\,\mathrm{mod}\,12 \\ 5^{-1}\,\mathrm{mod}\,13 \equiv 8\,\mathrm{mod}\,13\]
Thomas Busby
I write about computing stuff