## Math 310: Problem set 9 Solutions

Instructions: This problem set is due Thursday, November 16, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Show how to use Fermat's Theorem to efficiently compute [19]291010. (Hint: What is 1010 mod 28?)
2. Answer: 1010 = 28*36 + 2, so [19]291010 = ([19]2928)36[19]292 = [1]29[19]292, since Fermat's Theorem tells us that [19]2928 = [1]29, given that (19,29)=1. Thus [19]291010 = [19]292 = [192]29= [361]29 = [13]29.
3. Use Euler's Theorem to compute [3]281200000000000004. Explain how you did it.
4. Answer: Since (3,28)=1, Euler's Theorem tells us that [3]28phi(28) = [1]29. But phi(28)=phi(4)phi(7)=(4-2)(7-1)=12. Thus [3]281200000000000004 = ([3]2812)100000000000000[3]284 = [1]28100000000000000[3]284 = [3]284 = [81]28= [25]28.
5. Compute phi(37800). Explain how you did it.
6. Answer: First factor 37800 as 8*27*25*7. Since the factors are relatively prime, we have phi(37800) = phi(8)phi(27)phi(25)phi(7) = (8-4)(27-9)(25-5)(7-1) = 8640.
7. For this problem, you may use the web forms on the homework page to factor numbers, and to compute gcd's, but you should describe how you obtained your answers.
• Compute phi(9896401).
• Answer: Using the factoring web form we find that 9896401 factors as 2971*3331. These are prime factors, so phi(9896401) = phi(2971)phi(3331) = 2970*3330 = 9890100.
• Find gcd(2825743, phi(9896401)).
• Answer: Using the gcd web form we find 7*2825743 + -2* 9890100 = 1. Thus the gcd is 1.
• Solve 2825743x == 1 (mod phi(9896401)).
• Answer: From our previous answer, we see that x = 7 is a solution.
8. Here is a ciphertext: 421616, 2315355, 2676989, 3484668, 9020704, 9535054, 3938978, 6351955, 3247163, 4607436, 5567406, 6464964, 3065397. The original message is a famous quote. Each letter was converted into a 2-digit string from 01 to 26 according to the letter's position in the alphabet. Spaces were converted into 00. The resulting string of digits was broken into blocks of 6 digits each. Each block x was regarded as an element [x]m of Z/mZ, with m = 9896401. These blocks were then encrypted by replacing [x]m by [x]me, with encryption exponent e = 2825743. Your mission: recover the original quote! (I.e., break the code!) Explain how you did it. You may find it helpful to use the web form on the homework page which computes powers mod m.
9. Answer: The decryption exponent d is the solution to 2825743x == 1 (mod phi(9896401)), which above we found is 7. Thus we have too raise each of the numbers above to the 7th power mod 9896401. Using the powers mod m web form to do this gives the numbers 201500, 20500, 151800, 141520, 2015, 205, 2008, 12000, 91900, 200805, 1721, 51920, 91514 which gives the string 20 15 00 02 05 00 15 18 00 14 15 20 00 20 15 00 02 05 00 20 08 01 20 00 09 19 00 20 08 05 00 17 21 05 19 20 09 15 14, which converts to "To be or not to be that is the question".
10. You never want to use blocks which consist of a single letter. Then each block of your ciphertext represents a single letter, and you can use a language based approach to break the code. The method was described in a short story by Edgar Allan Poe, The Gold Bug: "Now, in English, the letter which most frequently occurs is e. Afterwards, the succession runs thus: a o i d h n r s t u y c f g l m w b k p q x z. E predominates so remarkably that an individual sentence of any length is rarely seen, in which it is not the prevailing character."
Use this method to decipher the following secret message (a quotation from a famous literary work). To help you, I've included counts of how often each letter appears in the ciphertext.

eqkk jt oaijqtk. agjt ntqsa qug- htcts johr igv kghu fsteoatkn- iqcohu kozzkt gs hg jghtn oh jn fxsat, qhr hgziohu fqszoexkqs zg ohztstaz jt gh aigst, o zigxuiz o vgxkr aqok qwgxz q kozzkt qhr att zit vqztsn fqsz gy zit vgskr. oz oa q vqn o iqct gy rsocohu gyy zit afktth qhr stuxkqzohu zit eosexkqzogh. vithtcts o yohr jnatky usgvohu usoj qwgxz zit jgxzi; vithtcts oz oa q rqjf, rsommkn hgctjwts oh jn agxk; vithtcts o yohr jnatky ohcgkxhzqsokn fqxaohu wtygst egyyoh vqstigxata, qhr wsohuohu xf zit stqs gy tctsn yxhtsqk o jttz; qhr tafteoqkkn vithtcts jn infga utz axei qh xffts iqhr gy jt, ziqz oz stdxosta q azsghu jgsqk fsoheofkt zg fstcthz jt ysgj rtkowtsqztkn aztffohu ohzg zit azsttz, qhr jtzigroeqkkn lhgelohu ftgfkt'a iqza gyy- zith, o qeegxhz oz ioui zojt zg utz zg atq qa aggh qa o eqh. zioa oa jn axwazozxzt ygs foazgk qhr wqkk. vozi q fiokgagfioeqk ykgxsoai eqzg zisgva iojatky xfgh ioa avgsr; o dxotzkn zqlt zg zit aiof. zitst oa hgziohu axsfsoaohu oh zioa. oy zitn wxz lhtv oz, qkjgaz qkk jth oh zitos rtustt, agjt zojt gs gzits, eitsoai ctsn htqskn zit aqjt yttkohua zgvqsra zit getqh vozi jt.

a: 53; b: 0; c: 13; d: 2; e: 18; f: 25; g: 62; h: 62; i: 51; j: 30; k: 45; l: 4; m: 2; n: 22; o: 80; p: 0; q: 57; r: 21; s: 56; t: 107; u: 24; v: 17; w: 9; x: 26; y: 22; z: 76
11. Answer: CALL me Ishmael. Some years ago- never mind how long precisely- having little or no money in my purse, and nothing particular to interest me on shore, I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen and regulating the circulation. Whenever I find myself growing grim about the mouth; whenever it is a damp, drizzly November in my soul; whenever I find myself involuntarily pausing before coffin warehouses, and bringing up the rear of every funeral I meet; and especially whenever my hypos get such an upper hand of me, that it requires a strong moral principle to prevent me from deliberately stepping into the street, and methodically knocking people's hats off- then, I account it high time to get to sea as soon as I can. This is my substitute for pistol and ball. With a philosophical flourish Cato throws himself upon his sword; I quietly take to the ship. There is nothing surprising in this. If they but knew it, almost all men in their degree, some time or other, cherish very nearly the same feelings towards the ocean with me.