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
 
Search WWH ::




Custom Search