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

- 3 mins

Exercise 1.7

We consider the ring Z4. Construct a table which describes the addition of all elements in the ring with each other:

  1. Construct the multiplication table for .
  2. Construct the addition and multiplication tables for .
  3. Construct the addition and multiplication tables for .
  4. There are elements in Z4 and Z6 without a multiplicative inverse. Which elements are these? Why does a multiplicative inverse exist for all non-zero elements in ?

Solution

This solution is verified as correct by the official Solutions for Odd-Numbered Questions manual.

1. Multiplication table for :

2. Addition and Multiplication Tables for :

3. Addition and Multiplication Tables for :

4. To determine whether an element has a multiplicative inverse, we must check if it can be multiplied with another element to produce 1:

Elements without a multiplicative inverse in are 2 and 0

Elements without a multiplicative inverse in are 2, 3, 4 and 0

For all non-zero elements of , there exists a multiplicative inverse because 5 is a prime. Hence, all non-zero elements smaller than 5 are relatively prime to 5.


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