Information Technology Reference
In-Depth Information
CRYPTOGRAPHY:
While cryptography has been important for ages, it became a serious con-
cern of complexity theorists in the late 1970s and an active research area in the 1980s and
1990s. Some of the important cryptographic issues are a) how to exchange information se-
cretly without having to exchange a private key with each communicating agent, b) how to
identify with high assurance the sender of a message, and c) how to convince another agent
that you have the solution to a problem without transferring the solution to him or her.
As this brief history illustrates, theoretical computer science speaks to many different com-
putational issues. As the range of issues addressed by computer science grows in sophistication,
we can expect a commensurate growth in the richness of theoretical computer science.
1.2 Mathematical Preliminaries
In this section we introduce basic concepts used throughout the topic. Since it is presumed
that the reader has already met most of this material, this presentation is abbreviated.
1.2.1 Sets
A
set
A
is a non-repeating and unordered collection of elements. For example,
A
50s
=
{
}
is a set of elements that could be interpreted as the names of languages
designed in the 1950s. Because the elements in a set are unordered,
Cobol, Fortran, Lisp
{
}
Cobol, Fortran, Lisp
{
}
and
Lisp, Cobol, Fortran
denote the same set. It is very convenient to recognize the
empty
set
∅
, a set that does not have any elements. The set
B
=
{
0, 1
}
containing 0 and 1 is used
throughout this topic.
The notation
a
∈
A
50s
means that Cobol is a language invented in the 1950s. A set can be finite or infinite. The
cardinality
of a finite set
A
, denoted
∈
A
means that element
a
is contained in set
A
. For example, Cobol
|
A
|
, is the number of elements in
A
. We say that a set
A
is a
subset
of a set
B
, denoted
A
⊆
B
, if every element of
A
is an element of
B
.If
A
⊆
B
but
B
contains elements not in
A
, we say that
A
is a
proper subset
and write
A
⊂
B
.
The
union
of two sets
A
and
B
, denoted
A
∪
B
, is the set containing elements that
are in
A
,
B
or both. For example, if
A
0
=
{
1, 2, 3
}
and
B
0
=
{
4, 3, 5
}
,then
A
0
∪
B
0
=
{
5, 4, 3, 1, 2
}
.The
intersection
of sets
A
and
B
, denoted
A
∩
B
, is the set containing elements
that are in both
A
and
B
.Hence,
A
0
∩
B
0
=
{
}
.If
A
and
B
have no elements in common,
3
denoted
A
∩
B
=
∅
,theyaresaidtobe
disjoint sets
.The
difference
between sets
A
and
B
, denoted
A
−
B
, is the set containing the elements that are in
A
but not in
B
.Thus,
A
0
−
B
0
=
{
}
1, 2
.(SeeFig.
1.1
.)
A
B
A
∩
B
A
−
B
Figure 1.1
A Venn diagram showing the intersection and difference of sets
A
and
B
.Their
unionisthesetofelementsinboth
A
and
B
.
Search WWH ::
Custom Search