Cryptography Reference
In-Depth Information
3.2
INTEGER ARITHMETIC
Mathematics is the queen of sciences and number theory is the queen of
mathematics.
— Carl Friedrich Gauss 12
As mentioned earlier, integer arithmetic elaborates on the ring
and its basic
properties. 13 This special (and comparably narrow) field of study is sometimes
also referred to as number theory . According to the quote given above, number
theory is a very important and fundamental mathematical topic that has had (and
continues to have) a deep impact on natural sciences. One fascinating aspect of
number theory is that many of its problems and theorems can be easily expressed
and understood even by nonmathematicians, but they are hard to solve (generally
without being able to prove the hardness property). This is in contrast to many other
areas of mathematics (where the relevant problems cannot easily be understood by
nonexperts). For example, the integer factorization problem (see Section 7.2.2) is
explained in a few words, whereas number theorists have tried to solve it without
success for several centuries.
In this section, we look at the aspects of integer arithmetic or number theory
that are relevant for the topic of this topic. More specifically, we address integer
division, common divisors and multiples, Euclidean algorithms, prime numbers,
factorization, and Euler's totient function.
Z
, + ,
·
3.2.1
Integer Division
In an algebraic structure with the multiplication operation, one usually divides two
elements by multiplying the first element with the (multiplicatively) inverse element
of the second. This can be formally expressed as follows:
a
b
= ab 1
Obviously, this construction requires that element b has an inverse element.
This is always the case in a group (or field). If, however, the algebraic structure is
only a monoid (or ring), then there are elements that have no inverse, and hence it
12
Carl Friedrich Gauss was a German mathematician who lived from 1777 to 1855.
13
What makes the integers unique (as compared to other rings and integral domains) is the order
relation
.
Search WWH ::




Custom Search