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.
- Show how to use Fermat's Theorem to efficiently compute
[19]291010. (Hint: What is 1010 mod 28?)
- Use Euler's Theorem to compute
[3]281200000000000004.
Explain how you did it.
- Compute phi(37800). Explain how you did it.
- 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)).
- 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.
- 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