Math 310: Problem set 9

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. Use Euler's Theorem to compute [3]281200000000000004. Explain how you did it.
3. Compute phi(37800). Explain how you did it.
4. 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).
• Find gcd(2825743, phi(9896401)).
• Solve 2825743x == 1 (mod phi(9896401)).
5. 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.
6. 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