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.
- Show how to use Fermat's Theorem to efficiently compute
291010. (Hint: What is 1010 mod 28?)
Answer: 1010 = 28*36 + 2, so 291010
= (2928)36292 = 29292, since
Fermat's Theorem tells us that 2928 =
29, given that (19,29)=1.
= 292 = 29=
29 = 29.
- Use Euler's Theorem to compute
Explain how you did it.
Answer: Since (3,28)=1, Euler's Theorem tells us that
29. But phi(28)=phi(4)phi(7)=(4-2)(7-1)=12.
= (2812)100000000000000284 = 28100000000000000284 = 284 = 28=
- Compute phi(37800). Explain how you did it.
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.
- 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.
- 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.
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".
- 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."
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.
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
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