Cryptography Reference
In-Depth Information
+
√
D
)
/
2] for some
c
form
Z
[
c
(
D
∈ N
. The integer
c
is called the
conductor
and the
discriminant of the order is
c
2
D
.
A.13 Binary strings
The binary representation of an integer
a
=
l
−
1
i
=
0
a
i
2
i
is written as
(
a
l
−
1
...a
1
a
0
)
2
or
a
l
−
1
...a
1
a
0
(A.1)
where
a
i
∈{
0
,
1
}
and
a
l
−
1
=
1. We say that the
bit-length
of
a
is
l
. An integer
a
∈ N
is
represented by a binary string of bit-length
log
2
(
a
)
+
1. The
least significant bit
of
a
is
LSB(
a
)
a
(mod 2). We call
a
i
the
i
th bit
or
bit
i
of
a
. The “most significant bit” is
trivially always one, but in certain contexts one uses different notions of MSB; for example
see Definition
21.7.1
.
Binary strings of length
l
are sequences
a
1
a
2
...a
l
with
a
i
∈{
=
a
0
=
. Such a sequence
is also called an
l
-bit string
.The
i
th bit is
a
i
. There is an ambiguity when one wants to
interpret a binary string as an integer; our convention is that
a
l
is the least significant bit.
2
We denote by
0
,
1
}
}
∗
the set of all binary
strings of arbitrary finite length. If
a
and
b
are binary strings then the exclusive-or (i.e.,
XOR
)
a
l
the set of all length
l
binary strings and
{
0
,
1
}
{
0
,
1
⊕
b
is the binary string whose
i
th bit is
a
i
+
b
i
(mod 2) for 1
≤
i
≤
l
.
A.14 Probability and combinatorics
We
briefly
recall
some
ideas
from
probability.
Good
references
are
Ross
[
451
],
Woodroofe [
569
] and Chapter 6 of Shoup [
497
].
The number of ways to choose
t
items from
n
without replacement, and where the
ordering matters, is
n
(
n
t
)!. The number of ways to
choose
t
items from
n
without replacement, and where the ordering does not matter, is
−
1)(
n
−
2)
···
(
n
−
t
+
1)
=
n
!
/
(
n
−
t
=
t
)!). The number of ways to choose
t
items from
n
with replacement and
where the ordering does not matter is
n
+
t
−
1
n
!
/
(
t
!(
n
−
t
−
1
.Wehave
n
m
n
m
m
ne
m
m
≤
≤
.
≈
√
2
πne
−
n
n
n
or log(
n
!)
Stirling's approximation to the factorial
is
n
!
≈
n
(log(
n
)
−
1) (where log denotes the natural logarithm). For proof see Section 5.4.1 of [
569
].
Let [0
,
1]
.A
distribution
onaset
S
is a function Pr mapping
“nice”
3
subsets of
S
to [0
,
1], with the properties that Pr(
={
x
∈ R
:0
≤
x
≤
1
}
∅
)
=
0, Pr(
S
)
=
1 and if
A,B
⊆
S
are disjoint and “nice” then Pr(
A
∪
B
)
=
Pr(
A
)
+
Pr(
B
). For
s
∈
S
we define Pr(
s
)
=
Pr(
{
s
}
)if
{
s
}
is “nice”. The
uniform distribution
on a finite set
S
is given by Pr(
s
)
=
1
/
#
S
.
⊆
An
event
is a “nice” subset
E
S
, and Pr(
E
) is called the probability of the event. We
¬
−
¬
=
−
≤
Pr(
E
1
∪
≤
define
E
to be
S
E
so that Pr(
E
)
1
Pr(
E
). We have Pr(
E
1
)
E
2
)
+
=
Pr(
E
1
∩
Pr(
E
1
)
Pr(
E
2
). We define Pr(
E
1
and
E
2
)
E
2
).
2
This means that the
i
th bit of a binary string is not the
i
th bit of the corresponding integer. This inconsistency will not cause
confusion in the topic.
3
Technically,
S
must be a set with a measure and the “nice” subsets are the measurable ones. When
S
is finite or countable then
every subset is “nice”.
