Wednesday 10 April 2019

Fields and Modular Arithmetic

I only recently became aware of the fact that a set of elements like {0, 1, 2, 3, 4, 5, 6} forms a field under modular arithmetic with modulus 7 (the number of elements in the set). The condition is that there are a prime number of elements in the set. Let's firstly define this idea of modular arithmetic:

Figure 1: extract from
https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html

Now what is a field? Here's a definition from http://www.applet-magic.com/field.htm:
A field \(F\) consists of a set \(S\) of elements and two binary functions \(f \) and \(g\) defined on \(S\) and whose values are in \(S.\) Both binary functions are associative, \(f(a, f(b,c)\) is equal to \(f( f(a, b), c)\) for all \(a\), \(b\) and \(c\) in \(S\) and likewise for \(g\). The binary function \(f\), called addition is necessarily commutative; i.e., \(f(a, b)\) is equal to \(f(b,a)\) for all \(a\) and \(b\) in \(S\). The other function \(g\), called multiplication, is not necessarily commutative. There is an identity for each functions; i.e. there exist \(e\) such that \(f(e, a)=a\) for all \(a\) in \(S\) and an \(l\) such that \(g(l, a)=a\) for all \(a\) in \(S\). There exist additive inverses for all elements of \(S\) and multiplicative inverses for all elements of \(S\) except the additive identity. This means that for any element \(a\) in \(S \) there exist \(a\) and \(b\) such that \(f(a, b)=e\). Such \(a\) \(b\) is denoted as \(−a\). For any element \(a\) in \(S \) that is not \(e \) there exists \(a\) and \(b \) such that \(g(a, b)\) is equal to \(l.\) The element \(b\) is usually denoted as \(a^{−1} \). Furthermore there is distributivity of multiplication with respect to addition; i.e. \( g(a, f(b, c)) \) is equal to \( f((g(a,b), g(a, c))  \) for all \(a,\), \(b \) and \(c\) in \(S\).
The set of \(n\) x \(n\) matrices is an example of a field in which multiplication is not commutative. Putting the whole business less formally, we can say that a set of elements form a field if the set is closed under the operations of addition, subtraction, multiplication and division. In other words, these operations when applied to two elements in the set always produce a third element that is also in the set. An example is {0, 1, 2, 3, 4, 5, 6} and it is easy to set up tables for all four operations verifying the set is indeed closed, as it is under all sets with a prime number of elements. Figure 2 shows what happens to the elements of the set under the operation of multiplication by 2:

Figure 2: mapping of elements of mod 7 under multiplication by 2

Figure 3 shows the full multiplication table:

Figure 3: multiplication table for mod 7

Of course, as stated above there is no multiplicative inverse for the additive identity element. In the case of the mod 7, this element is 0 and it means we can't divide by this element just as in regular arithmetic. Figure 4 shows the full division table:

Figure 4: division table for mod 7 with case of 5 divided by 3 highlighted

Figure 5 explains the condition for division to be possible in a modular system:

Figure 4: extract from
https://crypto.stanford.edu/pbc/notes/numbertheory/arith.html

No comments:

Post a Comment