Countable Sets

Link to the following exercise sheet: Countable Sets. In considering the problems on this sheet, note that a map from one set to another which "maps" or matches every element of the first set with an element of the second, if this forms what we called a one-to-one matching up of the elements (in other words, no two elements of the first set every match up with the same element of the second, and every element of the second set is matched up with someone from the first), then this is called a bijection, which is the term used in the exercise sheet. The squiggly "bijection" symbol used in the first line of the text exactly means that the sets are in bijection, namely that there is such a one-to-one matching up of all the elements.

Note that this exercise sheet contains some exercises similar to things that we covered and some that are somewhat harder. You are only expected to use this sheet to practice and think. Consider the following questions: Exercises 1, 2, and 3.a on page 1, Exercise 4 on page 2, True/False questions i. and ii. on page 4.

Paradoxes

Consider the following paradoxes and attempt to find a solution to each.

Rectangle paradox (and scroll down to look at the following, Chessboard Paradox as well).

Zeno's paradox.

The test-score paradox. When national test grades appear, a Nebraskan newspaper proudly reports

Both headlines are absolutely true. Can you find an explanation of the seeming contradiction?

Hint: some statistics may help. Say ten percent of middle school students taking the exam in Nebraska have English as a second language, and their average score on the test was 62/100. For the ninety percent of native English speakers, the average score on the test was 85/100. In New York, where twenty percent of the students come from foreign-language backgrounds, the average performance of this group on the test was 65/100, whereas the average of the English-speaking students was 87/100. Can you compute and compare the statewide averages?

The election paradox is so well-known in the USA as not even to constitute a surprise to the citizens, even as mouths drop open across the world. We have seen this paradox in action not so long ago, represented by the following three statements: The USA is a democracy, Al Gore received a majority of the popular vote across the country, Al Gore lost the presidential election.

Of course, this paradox is due to the incredibly complicated state-by-state delegate-style winner-take-all election system developed historically in this country to give individual states greater independence. It was probably not expected that the above paradoxical situation was every likely to occur, but it has occurred in American history no less than three times. Namely, Rutherford Hayes was elected in 1876 over Samuel Tilden, losing the popular vote by almost 300,000 votes out of about 8,000,000 voters; Benjamin Harrison was elected in 1888 over Grover Cleveland, who held an edge of about 100,000 votes in a total of about 11,000,000 voters; and finally of course George Bush beat Al Gore in 2000 (with some help from the Supreme Court), although Gore held an edge of about 543,000 votes out of a total of 101,500,000 voters.

Can you explain in what sense this paradox is analogous to the one above?

Coding and Cryptography

We will work with the following three public keys: (1111,69), (1261,223), (4891,97).

(1) Convert the following numbers to binary form: 69, 223, 97.

Answers: 1000101, 11011111,1100001.

Now, you wish to let each of the three owners of the public keys above that the apocalyptic BEAST is about to appear on earth, by encoding the secret message 666 for each of the three. This is done in the two steps shown in the two following problems.

(2) For each of the three public keys (n,e), make a list of length m=the length of the binary expansion of e, where the first the first entry in the list is T0=666 mod n, and the successive entries are equal to the previous one squared mod n. In other words, if T0 = 666 mod n is the first entry, the second entry will be T1 = T0² mod n, the third entry will be T2 = T1² mod n and so on until Tm is reached.

Answers: for (1111,69), we have m=7 and the list is (666,267,185,895,1105,36,185). For (1261,223), we have m=9 and the list is (666,945,237,685,133,35,1225,35). For (4891,97), we have m=7 and the list is (666,3366,2400,3293,502,2563,356).

(3) Compute the encoded message T^e mod n by the binary method, namely match up each of the lists of length m above with the corresponding binary number written backwards:

Answers: For (1111,69), the result is 667*185*185 mod 1111 = 574. For (1261,223) the product 666*945*237*685*133*1225*35 is very long, so it is better to take the remainder at each step: 666*945 mod 1261 = 131, then 131*237 mod 1261 = 783, then 783*685 mod 1261 = 430, then 430*133 mod 1261 = 445, then 445*1225 mod 1261 = 373, finally 373*35 mod 1261 = 445. Finally, in the third example only three numbers need to be multiplied, so we can either directly compute 666*2563*356 = 607677048 and take the result mod 4891, yielding the encoded message 4419, or (if this number is too long for our calculator), we can take 666*2563 mod 4891 = 4890, then 4890*356 mod 4891, which is again equal to 4535.

(4) Break each of the three public keys above by finding the secret private key. For this, you first have to factor n=pq, then calculate the three corresponding quantities (p-1)(q-1).

Answers: 1111=11*101, 1261=13*97, 4891=67*73, then (p-1)(q-1) is 1000 for 1111, 1152 for 1261, 4752 for 4891.

Now you need to search for the private key d, which is the first odd number greater than 1 such that de mod (p-1)(q-1) = 1. As we saw in class and on the RSA website, the best way to search for d is to search for a value of x, starting at x=1 and increasing one by one, such that ((p-1)(q-1)x+1)/e is an integer (i.e. such that (p-1)(q-1)x+1 is evenly divisible by e). Then, the value of d will be exactly ((p-1)(q-1)x+1)/e.

Answers: for (1111,69), the value x=2 works, yielding d=29. For (1261,223), the value of x=6 works, yielding d=31. Finally, for (4891,97), the value of x=1 works and yields d=49.

(5) Using your code-breaking private keys, decrypt the three following messages received by each of the public key owners: 572 (for (1111,69)), 468 (for (1261,223)), 4177 (for (4891,97)). Transform each of the answers into an alphabetical message by using the simplest alphabet code: a=1, b=2,...,z=26, and line up the three decoded messages for the response to your warning.

Answers: No, I'm not telling you.

LIST OF PRIME NUMBERS: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101

LIST OF POWERS OF 2: