Cryptography Reference
In-Depth Information
The natural numbers can be characterized by means of the axioms of
Giuseppe Peano (1858-1932), which coincide with our intuitive understanding of
the natural numbers:
(I)
The successors of two unequal natural numbers are unequal: From
n
=
m
it follows that
n
+
=
m
+
,forall
n, m ∈
N
.
(II)
Every natural number, with the exception of
0
, has a predecessor:
N
+
=
N
\{
0
}
.
(III)
The principle of
complete induction:
If
S ⊂
N
,
0
∈ S
,and
n ∈ S
always
imply
n
+
∈ S
,then
S
=
N
.
The principle of complete induction makes it possible to derive the arithmetic
operations with natural numbers in which we are interested. The fundamental
operations of addition and multiplication can be defined recursively as follows.
We begin with
addition
:
For every natural number
n
∈
N
there exists a function
s
n
from
N
N
to
such
that
(i)
s
n
(0) =
n
,
(ii)
s
n
x
+
=(
s
n
(
x
))
+
for all natural numbers
x ∈
N
.
The value of the function
s
n
(
x
)
is called the
sum
n
+
x
of
n
and
x
.
The existence of such functions
s
n
for all natural numbers
n ∈
N
must,
however, be proved, since the infinitude of natural numbers does not a priori
justify such an assumption. The existence proof goes back to the principle of
complete induction, corresponding to Peano's third axiom above (see [Halm],
Chapters 11-13). For
multiplication
one proceeds analogously:
For every natural number
n ∈
N
there exists a function
p
n
from
N
N
to
such
that
(i)
p
n
(0)=0
,
(ii)
p
n
x
+
=
p
n
(
x
)+
n
for all natural numbers
x
∈
N
.
The value of the function
p
n
(
x
)
is called the
product
n
x
of
n
and
x
.
As expected, multiplication is defined in terms of addition. For the arithmetic
operations thus defined one can prove, through repeated application of complete
induction on
x
in accordance with Axiom III, such well-known arithmetic laws as
associativity, commutativity, and distributivity (cf. [Halm], Chapter 13). Although
we usually use these laws without further ado, we shall help ourselves to them as
much as we please in testing our FLINT functions (see Chapters 13 and 18).
In a similar way we obtain a definition of
exponentiation
, which we give here
in view of the importance of this operation in what follows.
·
