Some students may be less familiar with the notation used in this class (esp in the crypto portion). We now give a quick review of the notation so that the assigments (and lectures) might be more digestible. Also, please refer to the MOV text, starting at section 1.3.
A "set" is a collection of objects usually written in braces. For example, {0, 2, 4, 6} is a collection of 4 integers. The "size" or "cardinality" of a set is the number of objects it contains. Duplicates are not allowed (this would be called a "multiset"). If a set has an infinite number of objects it is called an "infinite set" and has infinite cardinality. We often list the objects of an infinite set by writing the beginning of a pattern and then writing dots; for example, the integers might be written {..., -2, -1, 0, 1, 2, 3, ...}.
To write a finite set with a pattern, we often use square brackets. For example, the integers from 0 to 5 might be written [0 .. 5]. Note that this is inclusive, so the set is {0, 1, 2, 3, 4, 5}.
We will sometimes want to make sequences of objects from a set. We do this with a superscript indicating the length. For example, the set of all 5-bit strings is denoted {0,1}5. And the set of all binary strings (including the empty string) is {0,1}* (where the asterisk represents 0 or more repetitions).
By a "natural number" or simply "number" we mean the nonnegative integers, typically denoted N. In other words, the numbers {0, 1, 2, ...}.
By a "string" we will usually mean a "binary string". This is a finite ordered sequence of 0's and 1's, called "bits".
For the definition of "functions" (aka "maps"), and "permutations", please see section 1.3 of the MOV book.
You will occasionally be asked to write a proof in this class. For those of you who have written a lot of proofs before, you will be on comfortable ground. Those with limited experience will find it more challenging.
A "proof" is a logical rigorous mathematical argument. Write your proofs to be succinct, clear, and air-tight. Do not assume non-trivial facts, and try whenever possible to use clear notation such as we defined above. Perhaps the best way to discuss what we want as a proof in this course is via an example. Let's consider the classical problem of proving that there are an infinite number of prime numbers.
Theorem: There are an infinite number of prime numbers.
Let's start with some arguments that do not constitute a proof. These are bad arguments:
Ok, here is a proper proof:
Proof: There are an infinite number of primes; if there were a finite number of them then we could write them down in increasing order like this: A = {P1,P2, P3, ..., Pn}. But now we construct a new number Q = P1*P2* P3* ...* Pn + 1. We argue that Q is both (1) not already contained in A and (2) has no divisors in A.
(1) Since 2 is a prime number, it must be in A. Therefore 2 * Pn is already larger than anything in A, so certainly Q is larger than Pn, the maximum of A. Thus Q cannot be contained in A.
(2) Q is not divisible by any member of A because Q divided by any member of A has a remainder of 1 (thus it does not go in evenly). But this means that Q is either divisible by some prime not in A, or Q is itself prime. Either of these means that A did not in fact include all the primes as we had asserted above. Therefore our assumption must be wrong that the number of primes is finite and thus there must be an infinite number of primes.