Cryptography Reference
In-Depth Information
number of failures before
r
successes). This and many other probability distributions
are implemented in Maple's package
Statistics
. In particular, Maple gives us
the result in the above proposition by setting:
> with(Statistics):
X := RandomVariable(Geometric(p));
ExpectedValue(X);
(-p + 1)/p
1 failures are expected before obtaining the first success, i.e., the
expected number of trials for the first success is 1
Thus
(
1
/
p
)
−
/
p
.
2.2 Integers and Divisibility
Let
be the set of integers. The usual operations of
addition and multiplication are defined in
Z ={
...,
−
2
,
−
1
,
0
,
1
,
2
,...
}
and give it the structure of a commutative
ring with identity (see the definition in Sect.
2.5
or in [45, 48]). In fact,
Z
(
Z
,
+
,
·
)
is
the prototypical ring from which this concept arises by abstraction. Actually,
is
a special type of commutative ring called a (commutative) domain because it has
no
zero divisors
, i.e., there are no nonzero elements
a
Z
,
∈ Z
=
0.
We assume that the basic properties of addition and multiplication (associativity,
commutativity, distributivity, etc.) are well known and start by studying the concept
of divisibility.
b
such that
ab
Definition 2.6
Let
a
0. We say that
a divides b
(or, in other
words, that
b is a multiple of a
) if there exists an integer
q
such that
b
,
b
∈ Z
such that
a
=
=
aq
.
If
a
divides
b
then
a
is called a
divisor
of
b
and we write
a
|
b
.If
a
is not a divisor
of
b
we write
a
b
. Some of the most basic properties of divisibility are collected in
the following proposition whose proof is left as an exercise.
Proposition 2.3
(i) If a
|
b and b
|
c then a
|
c (transitivity).
(ii) If a
|
b and b
|
a then a
=±
b.
(iii) If a
|
b and a
|
c, then a
|
(
bx
+
cy
)
for all x
,
y
∈ Z
.
Next, we recall a couple of important results whose proofs are straightforward and
can be found in any introductory number theory textbook (see, for example, [77]).
We start with the following fact, which shows that even if
b
a
, we can divide
b
into
a
obtaining a quotient and a remainder:
Theorem 2.1
(Division algorithm)
Let a
,
b
∈ Z
such that b
>
0
. Then there exist
unique integers q and r such that a
=
bq
+
r and
0
≤
r
<
b.
The integers
q
and
r
are, respectively, the
quotient
and the
remainder
when
a
is divided by
b
. The division algorithm is implemented in Maple by means of the
functions
irem
and
iquo
. For example