Cryptography Reference
In-Depth Information
√
2
For instance,
=1.
Now we are able to revisit the full summation property and break it apart.
−
1
/
2
=
−
1,
1
/
2
=0,
−
1
.
5
=
−
2, and
Proposition A.2
If
n
∈
N
, then
(a)
n/
2
i
=0
2
i
=2
n
−
1
,
and
(b)
(
n
+1)
/
2
j
=1
n
2
j
−
1
=2
n
−
1
.
Proof
. See [167, Proposition 1.2.2, pages 21 and 22].
✷
Now that we have the notion of the floor function, it is valuable to know
some of its properties.
Theorem A.7
(
Properties of the Greatest Integer Function)
−
≤
(a)
x
1
<
x
x
.
(b)
x
+
n
=
x
+
n
for any
n
∈
Z
.
(c)
x
+
y
≤
x
+
y
≤
x
+
y
+1.
=
0
if
x
∈
Z
,
(d)
x
+
−
x
−
1
otherwise
.
Proof
. See [167, Theorem 1.2.4, page 22].
✷
We not only need the floor function but also the following close cousin. (See
Appendix F on pages 555 and 556, for instance.)
Definition A.16
(
The Least Integer Function — The Ceiling)
If
x
m<x
+1
.
We say that
m
is the
least integer greater than or equal to
x
or
the ceiling
of
x
, denoted by
∈
R
, then there is a unique integer
m
∈
Z
such that
x
≤
x
=
n
.
Theorem A.8
(
Properties of the Least Integer Function)
(a) If
x
∈
R
, then
−−
x
=
x
.
(b) If
x
∈
R
, then
x
=
x
+ 1 if and only if
x
∈
Z
.
Proof
. See [167, Exercises 1.3.1 and 1.3.2, page 40].
✷
An important fundamental result involving binomial coeGcients that we will
need in the text is the following.
Search WWH ::
Custom Search