Answers to Review Questions for Prelim I

CS 280 - Fall 2002

A couple of mistakes have been corrected.

The exam takes place in class on Friday, October 4. 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, September 30.  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 long proofs given in the text or in class (although you should understand such proofs).

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.

Please let me know via email (chew@cs.cornell.edu) if you discover mistakes in my solutions.  Past experience indicates that I may have made some.

  1. Chinese Remainder Theorem
    For these examples, the inverses can be found easily using simple trial-and-error because the moduli are so small.
    1. x = 3 (mod 5)
      x = 2 (mod 7)
      x = 1 (mod 9)    What is x?
      We need the inverse of 7*9 = 63 = 3 (mod 5).  The inverse is 2.
      We need the inverse of 5*9 = 45 = 3 (mod 7).  The inverse is 5.
      We need the inverse of 5*7 = 35 = 8 (mod 9).  The inverse is 8.
      Thus 2*63 is 1 mod 5, but zero for the other two moduli.
      Similarly 5*45 is 1 mod 7 and zero otherwise; 8*35 is 1 mod 9 and zero otherwise.
      A solution is thus 3*2*63 + 2*5*45 + 1*8*35 = 378 + 450 + 280 = 1108.  The Chinese Remainder Theorem tells us there is only one solution between 0 and 5*7*9=315.  1108=163(mod 315), so 163 is the final answer.
    2. x = 4 (mod 5)
      x = 5 (mod 6)
      x = 6 (mod 7)    What is x?
      We need the inverse of 6*7 = 42 = 2 (mod 5).  The inverse is 3.
      We need the inverse of 5*7 = 35 = 5 (mod 6).  The inverse is 5.
      We need the inverse of 5*6 = 30 = 2 (mod 7).  The inverse is 4.
      A solution is thus 4*3*42 + 5*5*35 + 6*4*30 = 2099, but we want to stay below 5*6*7=210.  2099 mod 210 = 209, so 209 is the final answer.
       
  2. 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?
      (1, 1, 3, 2)
    2. What is the quadruple corresponding to 23?
      (2, 7, 5, 1)
    3. What is the quadruple corresponding to 23*57?
      It's easiest to find this by multiplying the two previous quadruples, resulting first in (2, 7, 15, 2) and then in (2, 7, 6, 2) (i.e., the 3rd entry is reduced modulo 9).
    4. What is the largest number that can be conveniently represented using this scheme?
      To decode a quadruple, we need to use the Chinese Remainder Theorem.  This result will be unique only for numbers between 0 and 7*8*9*11.  Thus the largest number that can be represented is 7*8*9*11 - 1 = 5543.
       
  3. Solve for x in each linear congruence:
    1. 15 x = 3 (mod 17)
      We need the inverse of 15 (mod 17).  The gcd pairs we get when using Euclid's Algorithm are
      gcd(15, 17)
      = gcd(15, 2)
      = gcd(1, 2)
      = gcd(1, 0)=1.
      Working backward on this list, we have
      1= 1(2) - 1(1) = 1(2) - 1(15 - 7*2) = 8(2) - 1(15) = 8(17-15) -1(15) = 8(17) -9(15).
      Thus the inverse of 15 (mod 17) is -9 = 8 (mod 17).  Multiplying each side of the original equation by the inverse, we get
      x = 24 = 7 (mod 17).
    2. 123 x = 2 (mod 16)
      We can rewrite this equation as
      11 x = 2 (mod 16).  The inverse (mod 16) of 11 is 3.  Multiplying through by the inverse, we get
      x = 6 (mod 16).
    3. 57 x = 33 (mod 95)
      We need the inverse of 57 (mod 95).  The gcd pairs using Euclid's Algorithm:
      gcd(57, 95)
      = gcd(57, 38)
      = gcd(19, 38)
      = gcd(19, 0) = 19.  Thus, 57 does not have a multiplicative inverse (mod 95) because for the inverse to exist, the gcd must be one.  We can show that there is no possible solution: If a solution existed then we would have 57x - 33 = 95 k, for some k, by definition of congruence.  This can be rewritten as 33 = 57x - 95k.  But this is impossible (assuming x and k are integers) since the right side is divisible by 19 and the left side is not.
    4. 27 x = 11 (mod 88)
      We need the inverse of 17 (mod 88).  The gcd pairs:
      gcd(27, 88)
      = gcd(27, 7)
      = gcd(6, 7)
      = gcd(6, 1) = 1.
      Working backward, we have
      1 = 0(6) + 1(1) = 0(6) + 1(7 - 6) = 1(7) - 1(6) = 1(7) - 1(27 - 3*7) = 4(7) - 1(27)
      = 4(88 - 3*27) - 1(27) = 4(88) - 13(27).
      Thus the inverse of 27 (mod 88) is -13.  Multiplying through by the inverse, we get
      x = -143 = 33 (mod 88).
       
  4. (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.)
      Suppose we are an adversary trying to determine the private keys.  Each public key looks like a pair (e, n) where n is a product of two large primes.  But because the primes are re-used, we should be able to find a pair of public keys (e, n) and (e', n') such that n and n' share a prime factor.  Once we have n and n', we can use Euclid's Algorithm to determine the prime factor that they have in common.  Since there are only 100 public keys, we can try all pairs (there are 4950 such pairs), using Euclid's Algorithm to find common factors.  Once all the prime factors are known we can generate all private keys and read any message we want.
    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.
      For this version, we know that for a given public key (e, n), the prime factors of n are two primes that are very close to each other.  So we can find the integer closest to sqrt(n) and then test all pairs of nearby integers to find the prime factors of n.  We know that we don't need to check any integers further than 2 log(sqrt(n)) from sqrt(n).  Rewriting this, we see that we need to check at most log n integers below sqrt(n) and at most log n integers above sqrt(n).  If we try all pairs of such integers, we see that we need (log n)2 divisibility tests.  Thus, we have a good algorithm.
       
  5. 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.
      is O( n2 )
    2. n log(n2 + 1) + n.
      is O( n log n )
    3. 22 log n + 100 n.
      is O( n2 )
    4. (n2 + n log n)(n2 + n log n).
      is O( n4 )
    5. (n log n)(n2 log n + n + log n).
      is O( n3 (log n)2 )
       
  6. 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.
      Consider a triple prime sequence (a, b, c).  This can be rewritten as (a, a+2, a+4).  Taking this (mod 3), we get (a, a+2, a+1) mod 3.  Note that one of these three numbers must be divisible by 3.  The only prime divisible by 3 is 3; thus (3, 5, 7) is the only triple prime sequence.
    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.
      Consider the term a + a*b.  This term appears in any such sequence, but it cannot be prime because it's divisible by a.  Thus, no such sequence can consist entirely of prime numbers.
    3. 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)?
      We can check all 10 possible digits that might appear in the units position and square them to see what happens.  The only possible units digits for a square are 0, 1, 4, 5, 6, and 9.  Thus, a perfect square cannot end with 2, 3, 7, or 8.
    4. 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.
      Working modulo n: (n2-1)1001(n2+1)1000 = (-1)1001(+1)1000 = -1 (mod n).  So to make the original term divisible by n, we just add one.
       
  7. 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
      gcd(6 ones, 10 ones) = gcd(6 ones, 4 ones) = gcd(2 ones, 4 ones) = 2 ones = 11.  Dividing by 11, we get 10101 / 101010101.
    2. 57 nines / 102 nines
      gcd(57 nines, 102 nines) = gcd(57 nines, 45 nines) = gcd(12 nines, 45 nines)
      = gcd(12 nines, 9 nines) = gcd(3 nines, 9 nines) = 3 nines = 999.  Dividing by 999, we get
      19 '001's / 34 '001's.
    3. 10 twos / 27 twos
      This time the gcd is 1 two = 2.  Thus, the reduced fraction is 10 ones / 27 ones.
       
  8. 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.
      Basis: We can create 9, 10, or 11 pieces.  To create 9, we first create 6 then divide one of the 6 pieces into 4.  To create 10, we first make 4 pieces then choose two of those pieces and divide them each into 4.  To create 11, we first make 6 pieces then we divide one of those pieces into 6.
      Induction Hypothesis: It's possible to make any number of pieces p for 8 < p < n.
      We need to show how to make n pieces.  If n is 9, 10, or 11 then we can proceed as described in the Basis Case.  Otherwise, consider n-3.  By the Induction Hypothesis, there is a way to make n-3 pieces.  We tear paper to make n-3 pieces then we choose one of those pieces and tear it into 4, producing three more pieces, making n pieces all together.
      Note that the Basis had to include 3 subcases for the induction work.
    2. Prove that every integer greater than 8 can be written as 3m+5n for some nonnegative integers m and n.
      This is really just a restatement of the previous problem.
    3. Find all integers n such that 2n > n!.  Use induction to prove that you've found all such integers.
      We can try numbers until we find that 2n < n!.  Then we use Induction to show that 2n < n! for all larger n.  Trying numbers, we get: 1, 2, 3, with failure at 4.  Claim 2n < n! for all n > 4.
      Basis: 16 < 24, so it holds for n = 4.
      Induction Hypothesis: 2k < k! for k > 4.
      Consider k+1.  2k+1 = 2* 2k < 2*k! by the Induction Hypothesis.
      Further, 2*k! < (k+1)*k! = (k+1)!.  Thus, 2k+1 < (k+1)! and the claim is proved.
       
  9. A function f(n) on the natural number is defined as follows: 
        f(0) = 2 
        f(n+1) = 2 f(n) + 1 
    Use induction to prove that f(n) = 2n+1 + 2n - 1 for n > 0.

    Basis: By formula f(0) = 21 + 20 -1 = 2 + 1 - 1 = 2 which agrees with the definition. 

    Induction Hypothesis: Assume that f(k) = 2k+1 + 2k -1 for some k > 0.

    Consider f(k+1).  
    f(k+1) = 2f(k) + 1 by definition.
    Thus, f(k+1) = 2(2k+1 + 2k -1) + 1 by the Induction Hypothesis.
    Multiplying out and adding, we have, f(k+1) = 2k+2 + 2k+1 - 1 which agrees with the formula.

     

  10. A picture is drawn on a piece of paper according to certain rules. The picture starts with two points and the line segment connecting them. There are three operations that can be used to change the picture: (1) a new point can be placed on an existing line segment, destroying the old segment and creating two new segments, (2) a new line segment between two existing points can be added, and (3) a new point not on an existing line segment can be created and then connected to an existing point by a new line segment. Line segments are not allowed to cross other line segments and are not allowed to intersect points other than their endpoints.

    Note that a valid picture divides the piece of paper into regions. For instance, one can make a picture with 5 regions: four triangular regions and a fifth region consisting of all the paper outside the drawing. A picture consisting of a single square would create two regions: one inside the square and one outside the square. A picture consisting of the single starting segment would have just one region. Let p represent the number of points, s represent the number of segments, and r represent the number of regions. Use induction on the number of operations to prove that p - s + r = 2 for any valid picture.

    Basis: For the starting segment, p=2, s=1, and r=1, confirming that p-s+r=2.

    Induction Hypothesis: After n operations, we have a picture with p-s+r=2.

    Consider a picture after n+1 operations.  Undo the last operation, leaving a picture made from n operations; by the Induction Hypothesis, this picture has p-s+r=2.  Now we execute the last operation.  There are 3 cases (we use p', s', and r' to represent the result after the (n+1)st operation):

    1. Adding a point on a segment: In this case s'=s+1, p'=p+1, and r'=r.  Easy to see that p'-s'+r' = 2.
    2. Adding a new segment: In this case s'=s+1, p'=p, and r'=r+1.  Easy to see that p'-s'+r' = 2.
    3. Adding a new point and new segment: In this case s'=s+1, p'=p+1, and r'=r.  Easy to see that p'-s'+r' = 2.

    Since each operation results in the same formula, the formula must hold for all valid pictures.

  11.  
    1. Claim: For all positive integers a, b, and c, it is the case that if a divides b and gcd(b, c) > 1 then gcd(a, c) > 1.
      Decide whether your think the claim is true or false and support your answer with an appropriate short proof or counterexample.
      False.  Let a=2, b=6, and c=9.  In this case a|b and gcd(b,c)=3 which is > 1, but gcd(a,c)=1.
    2. Claim: For all positive integers a, there exists a positive integer b, so that a + 10b is a prime number. 
      Decide whether your think the claim is true or false and support your answer with an appropriate short proof or counterexample.
      False.  Consider a=10.  It's clear that 10 | (a+10b), so (a+10b) cannot be prime regardless of b's value.
       
  12.  
    1. Find an integer y such that 5y = 22 (mod 91).
      We know gcd(5, 91) = gcd(5, 1) = 1.  Working backward, we have 
      1 = 0(5) + 1(1) = 0(5) + 1(91 - 18*5) = 1*91 -18*5.  
      Thus, the inverse of 5 (mod 91) is -18.  Multiplying both sides of the original congruence by -18, we have
      y = (-18)(5)y = (-18)(22) = -396 (mod 91).  So the answer is -396 or 59 [or -396 plus any multiple of 91]. 
    2. What is the last digit (i.e., the units digit) of 222333?
      222333 = 2333 (mod 10).  Now the powers of 2 (mod 10) are: 2, 4, 8, 6, 2,...  Note that they cycle after 4 steps.  Thus, 2333 = 2333 mod 4 = 21 = 2 (mod 10).  The last digit is 2.
    3. What is 1234567893 + (789789789 * 987654321 * 3333) mod 5?
      Taking the numbers mod 5, we have 43 + (4*1*3) = 64 + 12 = 4 + 2 = 1 (mod 5).
       
  13. For each of the following propositions, determine if it is satisfiable. Support your answer with a short proof. 
    1. not ( ( p and (not q) ) -> ( (not p) or q ) )
      This is satisfiable.  Consider p=T, q=F.  In this case, the implication is false (because it's T->F); thus the proposition is true.
    2. (p -> not q) xor (q -> (p -> (not p) ) )

      This is not satisfiable.  To show something is not satisfiable we need to show that there is no assignment of truth values that makes the statement true.  The easiest way to do this is with a truth table.

      p q p -> (not q) q -> (p -> (not p))
      T T T  F      F T  F   T  F      F
      T F T  T      T F  T   T  F      F
      F T F  T      F T  T   F  T      T
      F F F  T      T F  T   F  T      T
              *     *

      The two columns marked * agree, so when we apply exclusive-or to them, we get a column consisting entirely of F.  Thus the statement is not satisfiable.
       

  14. Let A be the set of song titles that contain the word "Me", and let B be the set of song titles that include the word "the".  Express each of the following sets as a combination of A and B.
    1. The set of song titles that do not contain the word "Me".
      Ac
    2. The set of song titles that contain both "Me" and "the".
      A intersect B
    3. The set of song titles that contain "Me", but not "the".
      A - B
    4. The set of song titles that contain neither "Me" nor "the".
      Ac intersect Bc [which is equivalent to (A union B)c]
    5. The set of song titles that contain "Me" or "the", but not both.
      A summetricDifference B