Review Questions for Prelim I

CS 280 - Spring 2002

The exam takes place in class on Friday, February 22. I will try to arrive early so that we can start right at 1:25pm.

The use of extra material is not permitted during the exam (i.e., no textbook, no notes, no calculator, etc.).

The exam includes material from readings and lecture through Monday, February 18.  See the Schedule for a list of topics covered in lecture and for the corresponding readings; the topics and readings are also summarized below.  The exam will attempt to gauge your knowledge and understanding of course concepts. You shouldn't need to memorize specific code given in the text or in lecture.

The  topics covered on the exam (and the corresponding sections of the text) include:

The review questions given here are not meant to exhaust the possible topics for exam questions.  Consider reviewing both the homework assignments and the appropriate sections of the text.

  1. For each of the following statements, make the statement into a proposition, determine its negation, and write a sentence that corresponds to the negation.  An answer based on the strategy of using the phrase "It is not the case that" followed by the original sentence is not acceptable.  If the sentence has more than one interpretation then determine the result for each reasonable interpretation.  Remember that a propositional function can use more than a single variable.
    1. Every email is written by an annoying and ridiculous student.  (This sentence was suggested by one of the CS280 students in an email question.)
    2. Every Friday something is due for CS280.
    3. No cow has 5 legs and a cow has 4 more legs than no cow; thus, a cow has 9 legs.
    4. There is a kid of age 5 who doesn't like chocolate.
       
  2. Chinese Remainder Theorem
    1. x = 3 (mod 5)
      x = 2 (mod 7)
      x = 1 (mod 9)    What is x?
    2. x = 4 (mod 5)
      x = 5 (mod 6)
      x = 6 (mod 7)    What is x?
       
  3. Suppose we represent x as the ordered quadruple (x mod 7, x mod 8, x mod 9, x mod 11).
    1. What is the quadruple corresponding to 57?
    2. What is the quadruple corresponding to 23?
    3. What is the quadruple corresponding to 23*57?
    4. What is the largest number that can be conveniently represented using this scheme?
       
  4. Solve for x in each of the following  linear congruences:
    1. 15 x = 3 (mod 17)
    2. 123 x = 2 (mod 16)
    3. 57 x = 33 (mod 95)
    4. 27 x = 11 (mod 88)
       
  5. (from CS280, Problem Set  4, Fall 2000)
    A good algorithm is one for which the number of basic operations on an input n can be bounded by a function proportional to (log n)c, for some fixed exponent c (i.e., like c =1 or c =2).  A bad algorithm is one for which such a bound does not hold; intuitively, it’s an algorithm for which the running time on input n scales more like n than like the number of digits in n.  Thus, we saw that the elementary-school algorithms for addition and multiplication are good algorithms.  Much less obviously, Euclid’s Algorithm for greatest common divisors is a good algorithm.  On the other hand, to find the prime factors of a number n, the approach of trying all possible divisors is a bad algorithm; indeed, no good algorithm is known for factoring, and it’s suspected that no good algorithm exists. RSA can clearly be broken by a bad algorithm —simply factor the public key by brute force.  The real question is, can it be broken by a good algorithm?  Let’s explore this idea in more detail...
    1. The phone rings one day and you pick it up.  The voice at the other end says, “Hello, is this Professor Rivest?”  You mean to say “No,” but for some reason you say “Yes ”instead; the next thing you know, people from a mysterious company arrange to fly you out to the West Coast to advise them on their security system. “We have a system where we put 100 agents out in the field,” they explain to you, in a sub-basement surrounded by electromagnetic shielding.  “Each agent announces an RSA public key, and then they use the RSA cryptosystem to send messages to each other using these public keys.  We ’re not concerned about whether the agents know each other’s private keys or not —we ’re all on the same team, after all —but we’re very worried about outsiders learning the private keys. “Here’s the basic code we planned to use to assign a public key to each agent: 
      Method I: 
          For i =1 , 2 , ,...,100 
              Generate a prime number pi. 
              Generate a prime number qi.
              Use pi and qi to compute private and public keys for agent i.
      End 
      “After looking at this for a while, we thought: ‘Isn’t Method I sort of wasteful of primes?’ So we came up with Method II:
      Method II: 
          First generate prime numbers p1,p2,...,p101 
          For i =1 , 2 , ,...,100 
              Use pi and pi+1 to compute private and public keys for agent i. 
      End 
      “Notice how we only use about half as many primes in Method II.  But we’re worried that Method II is somehow insecure —that if our enemies knew we were using Method II to compute keys, they could compute the private keys from the public keys by a good algorithm.”  So here’s the question: show that in fact the company’s fears are well-founded.  Given a set of 100 public keys known to be generated by Method II, show how to compute the 100 corresponding private keys by a good algorithm. (Note. The point is that, in trying to break the keys, you know that Method II was used, but you (obviously) don ’t know at the outset what the primes p1,p2,...,p101 are.  Also, here is a crucial thing: your good algorithm is allowed to have a factor proportional to the number of agents in its running time, since this is simply the (small) constant 100.)
    2. Your discovery that Method II is insecure causes much uproar; but when this dies down, they remember another method for generating public keys they want to tell you about. “Basically, here’s how it goes.  For each agent i we start with a fresh prime number pi   Now we need a second prime qi to complete the construction of the keys.  So we start at 1+pi, and test each natural number in order for primality until we first find one that is prime.  We use this as the second prime qi.  If we try 2 log pi numbers and none of them is prime, then we decide this is taking too long and start over with a new choice of pi —but in practice this rarely happens. 
      Unfortunately, this method (call it Method III) is also insecure.  Given a set of 100 public keys known to be generated by Method III, show how to compute the 100 corresponding private keys by a good algorithm.
       
  6. Give a big-O estimate for each of the following functions.  Use a simple function of smallest possible order.
    1. n log(n2 + 1) + n2.
    2. n log(n2 + 1) + n.
    3. 22 log n + 100 n.
    4. (n2 + n log n)(n2 + n log n).
    5. (n log n)(n2 log n + n + log n).
       
  7. Some number theory problems:
    1. (from CS280, Problem Set 3, Fall 2000) A triple prime sequence is a sequence of three natural numbers (a, b, c)  such that b=a+2, c=b+2, and each of a, b, and c is a prime number.  For example, (3, 5, 7) is a triple prime sequence, but (1, 3, 5) is not since 1 is not prime.  Consider the following claim: (3, 5, 7) is the only triple prime sequence.
      Decide whether the claim is true or false and justify your answer with a proof.
    2. (from CS280, Problem Set 3, Fall 2000) An infinite arithmetic progression is a set of natural numbers of the form a, a+b, a+2b, a+3b, a+4b,...  Consider the following claim: There is an infinite arithmetic progression, all of whose elements are prime numbers.
      Decide whether the claim is true or false and justify your answer with a proof.
    3. (from CS280, Problem Set  4, Fall 2000)  We use fn to represent the nth Fibonacci number where f1=f2=1.  Consider the following claim: For every n > 2, the greatest common divisor of fn and fn-1 is equal to one.
      Decide whether the claim is true or false and justify your answer with a proof.
    4. Can the perfect square of a natural number end with 2?  Is it possible to write the square of a natural number using only the digits 2, 3, 7, and 8 (repetitions are allowed)?
    5. Find a number (not depending on n) such that when it's added to (n2-1)1001(n2+1)1000 the result is divisible by n.
       
  8. We use the phrase 6 ones to represent the number that is written as a string of six ones (i.e., 111111).  Reduce the following fractions to lowest terms:
    1. 6 ones / 10 ones
    2. 57 nines / 102 nines
    3. 10 twos / 27 twos
       
  9. Some problems on Induction:
    1. You are to tear paper into pieces, but only two kinds of tearing are allowed.  Given a piece of paper, you can tear it into either 4 or 6 new pieces.  Show that, following these rules and starting with a single piece of paper, it's possible to create any number of pieces greater than 8.
    2. Prove that every integer greater than 8 can be written as 3m+5n for some nonnegative integers m and n.
    3. Find all integers n such that 2n > n!.  Use induction to prove that you've found all such integers.
    4. Use induction to show 2n > n2 for n > 4.