Square roots. In this problem, well see that it is easy to compute square roots modulo a

Show that in any base b 2, the sum of any three single-digit numbers is at most two digits long

Show that any binary integer is at most four times as long as the corresponding decimal integer. For very large numbers, what is the ratio of these two lengths, approximately?

A d-ary tree is a rooted tree in which each node has at most d children. Show that any d-ary tree with n nodes must have a depth of \(\Omega(\log n / \log d)\). Can you give a precise formula for the minimum depth it could possibly have?

Show that log(n!) = (n log n). (Hint: To show an upper bound, compare n! with n n. To show a lower bound, compare it with (n/2)n/2 .)

Unlike a decreasing geometric series, the sum of the harmonic series 1, 1/2, 1/3, 1/4, 1/5, . . . diverges; that is, X i=1 1 i = . It turns out that, for large n, the sum of the first n terms of this series can be well approximated as Xn i=1 1 i ln n + , where ln is natural logarithm (log base e = 2.718 . . .) and is a particular constant 0.57721 . . .. Show that Xn i=1 1 i = (log n). (Hint: To show an upper bound, decrease each denominator to the next power of two. For a lower bound, increase each denominator to the next power of 2.)

Prove that the grade-school multiplication algorithm (page 24), when applied to binary numbers, always gives the right answer

How long does the recursive multiplication algorithm (page 25) take to multiply an n-bit number by an m-bit number? Justify your answer.

Justify the correctness of the recursive division algorithm given in page 26, and show that it takes time O(n 2 ) on n-bit inputs.

Starting from the definition of x y mod N (namely, that N divides xy), justify the substitution rule x x 0 mod N, y y 0 mod N x + y x 0 + y 0 mod N, and also the corresponding rule for multiplication.

Show that if a b (mod N) and if M divides N then a b (mod M).

Is 4 1536 9 4824 divisible by 35?

What is 2 2 2006 (mod 3)?

Is the difference of 5 30,000 and 6 123,456 a multiple of 31?

Suppose you want to compute the nth Fibonacci number \(F_n\), modulo an integer p. Can you find an efficient way to do this? (Hint: Recall Exercise 0.4.)

Determine necessary and sufficient conditions on x and c so that the following holds: for any a, b, if ax bx mod c, then a b mod c.

A salad is any combination of the following ingredients: (1) tomato, (2) lettuce, (3) spinach, (4) carrot, and (5) oil. Each salad must contain: (A) at least 15 grams of protein, (B) at least 2 and at most 6 grams of fat, (C) at least 4 grams of carbohydrates, (D) at most 100 milligrams of sodium. Furthermore, (E) you do not want your salad to be more than 50% greens by mass. The nutritional contents of these ingredients (per 100 grams) are Find a linear programming applet on the Web and use it to make the salad with the fewest calories under the nutritional constraints. Describe your linear programming formulation and the optimal solution (the quantity of each ingredient and the value). Cite the Web resources that you used.

Consider the problem of computing x y for given integers x and y: we want the whole answer, not modulo a third integer. We know two algorithms for doing this: the iterative algorithm which performs y 1 multiplications by x; and the recursive algorithm based on the binary expansion of y. Compare the time requirements of these two algorithms, assuming that the time to multiply an n-bit number by an m-bit number is O(mn).

Compute gcd(210, 588) two different ways: by finding the factorization of each number, and by using Euclid’s algorithm.

The Fibonacci numbers \(F_{0}, F_{1}, \ldots\) are given by the recurrence \(F_{n+1}=F_{n}+F_{n-1}, \ F_{0}=0, \ F_{1}=1\). Show that for any \(n \geq 1, \operatorname{gcd}\left(F_{n+1}, F_{n}\right)=1\).

Find the inverse of: 20 mod 79, 3 mod 62, 21 mod 91, 5 mod 23.

How many integers modulo \(11^{3}\) have inverses? (Note: \(11^{3}=1331\).)

Prove or disprove: If a has an inverse modulo b, then b has an inverse modulo a.

Show that if a has a multiplicative inverse modulo N, then this inverse is unique (modulo N).

If p is prime, how many elements of {0, 1, . . . , p n 1} have an inverse modulo p n?

Calculate \(2^{125}\) mod 127 using any method you choose. (Hint: 127 is prime.)

What is the least significant decimal digit of 171717 ? (Hint: For distinct primes p, q, and any a 6 0 (mod pq), we proved the formula a (p1)(q1) 1 (mod pq) in Section 1.4.2.)

Consider an RSA key set with p = 17, q = 23, N = 391, and e = 3 (as in Figure 1.9). What value of d should be used for the secret key? What is the encryption of the message M = 41?

In an RSA cryptosystem, p = 7 and q = 11 (as in Figure 1.9). Find appropriate exponents d and e.

Let denote the set For each of the following families of hash functions, say whether or not it is universal, and determine how many random bits are needed to choose a function from the family. (a) , where m is a fixed prime and Notice that each of these functions has signature that is, it maps a pair of integers in to a single integer in . (b) H is as before, except that now is some fixed power of 2. (c) H is the set of all functions .

The grade-school algorithm for multiplying two n-bit binary numbers x and y consists of adding together n copies of x, each appropriately left-shifted. Each copy, when shifted, is at most 2n bits long. In this problem, we will examine a scheme for adding n binary numbers, each m bits long, using a circuit or a parallel architecture. The main parameter of interest in this question is therefore the depth of the circuit or the longest path from the input to the output of the circuit. This determines the total time taken for computing the function. To add two m-bit binary numbers naively, we must wait for the carry bit from position before we can figure out the bit of the answer. This leads to a circuit of depth . However carry lookaheads circuits (see wikipedia.com if you want to know more about this) can add in depth. (a) Assuming you have carry look ahead circuits for addition, show how to add n numbers each m bits long using a circuit of depth . (b) When adding three m-bit binary numbers There is a trick we can use to parallelize the process. Instead of carrying out the addition completely, we can re-express the result as the sum of just two binary numbers , such that the bits of r and s can be computed independently of the other bits. Show how this can be done. (Hint: One of the numbers represents carry bits.) (c) Show how to use the trick from the previous part to design a circuit of depth for multiplying two n-bit numbers.

Consider the problem of computing \(N !=1 \cdot 2 \cdot 3 \cdots N\). (a) If N is an n-bit number, how many bits long is N!, approximately (in \(\Theta(\cdot)\) form)? (b) Give an algorithm to compute N! and analyze its running time.

A positive integer N is a power if it is of the form q k , where q, k are positive integers and k > 1. (a) Give an efficient algorithm that takes as input a number N and determines whether it is a square, that is, whether it can be written as q 2 for some positive integer q. What is the running time of your algorithm? (b) Show that if N = q k (with N, q, and k all positive integers), then either k log N or N = 1. (c) Give an efficient algorithm for determining whether a positive integer N is a power. Analyze its running time.

Give an efficient algorithm to compute the least common multiple of two n-bit numbers x and y, that is, the smallest number divisible by both x and y. What is the running time of your algorithm as a function of n?

On page 38, we claimed that since about a 1/n fraction of n-bit numbers are prime, on average it is sufficient to draw O(n) random n-bit numbers before hitting a prime. We now justify this rigorously. Suppose a particular coin has a probability p of coming up heads. How many times must you toss it, on average, before it comes up heads? (Hint: Method 1: start by showing that the correct expression is P i=1 i(1 p) i1p. Method 2: if E is the average number of coin tosses, show that E = 1 + (1 p)E.)

Wilsons theorem says that a number N is prime if and only if (N 1)! 1 (mod N). (a) If p is prime, then we know every number 1 x < p is invertible modulo p. Which of these numbers are their own inverse? (b) By pairing up multiplicative inverses, show that (p 1)! 1 (mod p) for prime p. (c) Show that if N is not prime, then (N 1)! 6 1 (mod N). (Hint: Consider d = gcd(N,(N 1)!).) (d) Unlike Fermats Little theorem, Wilsons theorem is an if-and-only-if condition for primality. Why cant we immediately base a primality test on this rule?

Square roots. In this problem, we’ll see that it is easy to compute square roots modulo a prime p with \(p \equiv 3\) (mod 4). (a) Suppose \(p \equiv 3\) (mod 4). Show that (p + 1)/4 is an integer. (b) We say x is a square root of a modulo p if \(a \equiv x^{2}\) (mod p). Show that if \(p \equiv 3\) (mod 4) and if a has a square root modulo p, then \(a^{(p+1) / 4}\) is such a square root.

The Chinese remainder theorem. (a) Make a table with three columns. The first column is all numbers from 0 to 14. The second is the residues of these numbers modulo 3; the third column is the residues modulo 5. What do you observe? (b) Prove that if p and q are distinct primes, then for every pair (j, k) with 0 j < p and 0 k < q, there is a unique integer 0 i < pq such that i j mod p and i k mod q. (Hint: Prove that no two different is in this range can have the same (j, k), and then count.) (c) In this one-to-one correspondence between integers and pairs, it is easy to go from i to (j, k). Prove that the following formula takes you the other way: i = {j q (q 1 mod p) + k p (p 1 mod q)} mod pq. (d) Can you generalize parts (b) and (c) to more than two primes?

To see if a number, say 562437487, is divisible by 3, you just add up the digits of its decimal representation, and see if the result is divisible by 3. (5 + 6 + 2 + 4 + 3 + 7 + 4 + 8 + 7 = 46, so it is not divisible by 3.) To see if the same number is divisible by 11, you can do this: subdivide the number into pairs of digits, from the right-hand end (87, 74, 43, 62, 5), add these numbers, and see if the sum is divisible by 11 (if its too big, repeat). How about 37? To see if the number is divisible by 37, subdivide it into triples from the end (487, 437, 562) add these up, and see if the sum is divisible by 37. This is true for any prime p other than 2 and 5. That is, for any prime p 6= 2, 5, there is an integer r such that in order to see if p divides a decimal number n, we break n into r-tuples of decimal digits (starting from the right-hand end), add up these r-tuples, and check if the sum is divisible by p. (a) What is the smallest such r for p = 13? For p = 17? (b) Show that r is a divisor of p 1.

Give a polynomial-time algorithm for computing a b c mod p, given a, b, c, and prime p.

Show that if x is a nontrivial square root of 1 modulo N, that is, if \(x^{2} \equiv 1\) mod N but \(x \not \equiv \pm 1\) mod N, then N must be composite. (For instance, \(4^{2} \equiv 1\) mod 15 but \(4 \not \equiv \pm 1\) mod 15; thus 4 is a nontrivial square root of 1 modulo 15.)

Quadratic residues. Fix a positive integer N. We say that a is a quadratic residue modulo N if there exists x such that a identical to x squared space m o d space N . (a) Let N be an odd prime and a be a non-zero quadratic residue modulo N. Show that there are exactly two values in {0, 1, …, N-1} satisfying x squared identical to a space m o d space N . (b) Show that is N is an odd prime, there are exactly (N+1)/2 quadratic residues in {0, 1, …, N-1}. (c) Give an example of positive integers a and N such that x squared identical to a space m o d space N has more than two solutions in {0, 1, …, N-1}.

Suppose that instead of using a composite N = pq in the RSA cryptosystem (Figure 1.9), we simply use a prime modulus p. As in RSA, we would have an encryption exponent e, and the encryption of a message m mod p would be me mod p. Prove that this new cryptosystem is not secure, by giving an efficient algorithm to decrypt: that is, an algorithm that given p, e, and me mod p as input, computes m mod p. Justify the correctness and analyze the running time of your decryption algorithm.

In the RSA cryptosystem, Alices public key (N, e) is available to everyone. Suppose that her private key d is compromised and becomes known to Eve. Show that if e = 3 (a common choice) then Eve can efficiently factor N.

Alice and her three friends are all users of the RSA cryptosystem. Her friends have public keys (Ni , ei = 3), i = 1, 2, 3, where as always, Ni = piqi for randomly chosen n-bit primes pi , qi . Show that if Alice sends the same n-bit message M (encrypted using RSA) to each of her friends, then anyone who intercepts all three encrypted messages will be able to efficiently recover M. (Hint: It helps to have solved problem 1.37 first.)

RSA and digital signatures. Recall that in the RSA public-key cryptosystem, each user has a public key P = (N, e) and a secret key d. In a digital signature scheme, there are two algorithms, sign and verify. The sign procedure takes a message and a secret key, then outputs a signature . The verify procedure takes a public key (N, e), a signature , and a message M, then returns true if could have been created by sign (when called with message M and the secret key corresponding to the public key (N, e)); false otherwise. (a) Why would we want digital signatures? (b) An RSA signature consists of sign(M, d) = Md (mod N), where d is a secret key and N is part of the public key. Show that anyone who knows the public key (N, e) can perform verify((N, e), Md , M), i.e., they can check that a signature really was created by the private key. Give an implementation and prove its correctness. (c) Generate your own RSA modulus N = pq, public key e, and private key d (you dont need to use a computer). Pick p and q so you have a 4-digit modulus and work by hand. Now sign your name using the private exponent of this RSA modulus. To do this you will need to specify some one-to-one mapping from strings to integers in [0, N 1]. Specify any mapping you like. Give the mapping from your name to numbers m1, m2, . . . mk, then sign the first number by giving the value md 1 (mod N), and finally show that (md 1 ) e = m1 (mod N). (d) Alice wants to write a message that looks like it was digitally signed by Bob. She notices that Bobs public RSA key is (17, 391). To what exponent should she raise her message?

Digital signatures, continued. Consider the signature scheme of Exercise 1.45. (a) Signing involves decryption, and is therefore risky. Show that if Bob agrees to sign anything he is asked to, Eve can take advantage of this and decrypt any message sent by Alice to Bob. (b) Suppose that Bob is more careful, and refuses to sign messages if their signatures look suspiciously like text. (We assume that a randomly chosen messagethat is, a random number in the range {1, . . . , N 1}is very unlikely to look like text.) Describe a way in which Eve can nevertheless still decrypt messages from Alice to Bob, by getting Bob to sign messages whose signatures look random.