Homework B

This homework is due 2011-11-07. It should be handed in at the beginning of class. The solutions must be printed, not handwritten. Solutions handed in late are not accepted and will not be graded.

Please remember that solutions need to be in English.

Problem 1 (7 pts)

Using the 0/1-principle for sorting networks, either show that the following sorting network correctly sorts 4 inputs, or find an input where it fails. In a compare element, the larger of the two values goes in the direction of the arrow.

Problem 2 (7 pts)

Crack RSA! Given the public RSA key (n, e) = (5192042249411, 3419183406883), find the decryption exponent d and find a number x that encrypts to your ten-digit personal number.

Your answer should include x as well as explain calculations used to obtain x.

If you wish, you may use big integer support in Java or python (but not functions or modules specificly tailored for RSA).

Note: in reality, RSA keys use a much larger modulus n.

Problem 3 (6pts)

Mulitply the following two polynomials using Karatsuba's algorithm.

x³ + 3x² + x - 1 and
2x³ - x² + 3

You only need to show the top-most call, what recursive calls are made from the top-mmost level, what those calls return and how the final result is computed.

Problem 4 (5 pts)

A positive odd integer n is a Carmichael number if

1. it is composite (that is, not a prime)
2. and for all numbers 1 ≤ a < n such that gcd(a,n)=1, it holds that a^n-1 ≡ 1 (mod n)

Show that it is easy to find a non-trivial factor of a Carmichael number. More precisely, there is a polynomial-time algorithm for finding a non-trivial factor with probability > 1/2.

Explain your algorithm, why it works, and analyze its complexity.

Hint: you can use the fact that the Miller–Rabin algorithm for primality testing reveals that a composite number is not prime with probability > 1/2. Of course, Miller–Rabin by itself does not find factors. It only answers probably prime or composite. Consider what happens in the execution of the algorithm when a Carmichael number is fond to be composiste (i.e.. when the result is not probably prime).