Solutions Manual

User Manual: Pdf

Open the PDF directly: View PDF PDF.
Page Count: 223 [warning: Documents this large are best viewed by clicking the View PDF Link!]

An Introduction to Mathematical
Cryptography
Solution Manual
Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman
c
°2008 by J. Hoffstein, J. Pipher, J.H. Silverman
July 31, 2008
Chapter 1
An Introduction to
Cryptography
Exercises for Chapter 1
Section. Simple substitution ciphers
1.1. Build a cipher wheel as illustrated in Figure 1.1, but with an inner wheel
that rotates, and use it to complete the following tasks. (For your convenience,
there is a cipher wheel that you can print and cut out at www.math.brown.
edu/~jhs/MathCrypto/CipherWheel.pdf.)
(a) Encrypt the following plaintext using a rotation of 11 clockwise.
“A page of history is worth a volume of logic.”
(b) Decrypt the following message, which was encrypted with a rotation of 7
clockwise.
AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLALZAOHALCLYFIVKFNBLZZLZ
(c) Decrypt the following message, which was encrypted by rotating 1 clock-
wise for the first letter, then 2 clockwise for the second letter, etc.
XJHRFTNZHMZGAHIUETXZJNBWNUTRHEPOMDNBJMAUGORFAOIZOCC
Solution to Exercise 1.1.
(a) apageofhistoryisworthavolumeoflogic
LALRPZQSTDEZCJTDHZCESLGZWFXPZQWZRTN
This quote is in a court decision of Oliver Wendell Holmes, Jr. (1921).
(b) therearenosecretsbetterthanthesecretsthateverybodyguesses
AOLYLHYLUVZLJYLAZILAALYAOHUAOLZLJYLAZAOHALCLYFIVKFNBLZZLZ
There are no secrets better than the secrets that everybody
guesses.
This quote is due to George Bernard Shaw, Mrs. Warren’s Profession (1893)
1
2 Exercises for Chapter 1
(c) whenangrycounttenbeforeyouspeakifveryangryanhundred
XJHRFTNZHMZGAHIUETXZJNBWNUTRHEPOMDNBJMAUGORFAOIZOCC
When angry, count ten before you speak; if very angry, an hundred.
This quote is due to Thomas Jefferson, A Decalogue of Canons. . . (1825).
1.2. Decrypt each of the following Caesar encryptions by trying the various
possible shifts until you obtain readable text.
(a) LWKLQNWKDWLVKDOOQHYHUVHHDELOOERDUGORYHOBDVDWUHH
(b) UXENRBWXCUXENFQRLQJUCNABFQNWRCJUCNAJCRXWORWMB
(c) BGUTBMBGZTFHNLXMKTIPBMAVAXXLXTEPTRLEXTOXKHHFYHKMAXFHNLX
Solution to Exercise 1.2.
(a) ithinkthatishallneverseeabillboardlovelyasatree
LWKLQNWKDWLVKDOOQHYHUVHHDELOOERDUGORYHOBDVDWUHH
I think that I shall never see, a billboard lovely as a tree.
This quote is due to Ogden Nash, Many Long Years Ago (1945), Song of the
Open Road.
(b) loveisnotlovewhichalterswhenitalterationfinds
UXENRBWXCUXENFQRLQJUCNABFQNWRCJUCNAJCRXWORWMB
Love is not love which alters when it alteration finds.
This quote is due to William Shakespeare, Sonnet 116.
(c) inbaitingamousetrapwithcheesealwaysleaveroomforthemouse
BGUTBMBGZTFHNLXMKTIPBMAVAXXLXTEPTRLEXTOXKHHFYHKMAXFHNLX
In baiting a mousetrap with cheese, always leave room for the
mouse.
This quote is due to H.H. Munro (Saki), The Square Egg (1924).
1.3. For this exercise, use the simple substitution table given in Table 1.11.
(a) Encrypt the plaintext message
The gold is hidden in the garden.
(b) Make a decryption table, that is, make a table in which the ciphertext
alphabet is in order from Ato Zand the plaintext alphabet is mixed up.
(c) Use your decryption table from (b) to decrypt the following message.
IBXLX JVXIZ SLLDE VAQLL DEVAU QLB
Solution to Exercise 1.3.
(a)
Exercises for Chapter 1 3
abcdefghijklmnopqrstuvwxyz
SCJAXUFBQKTPRWEZHVLIGYDNMO
Table 1.1: Simple substitution encryption table for exercise 1.3
thegoldishiddeninthegarden
IBXFEPAQLBQAAXWQWIBXFSVAXW
Breaking it into five letter blocks gives the ciphertext
IBXFE PAQLB QAAXW QWIBX FSVAX W
(b)
dhbwoguqtcjsyxzlimakfrnevp
ABCDEFGHIJKLMNOPQRSTUVWXYZ
(c)
thesecretpasswordisswordfish
IBXLXJVXIZSLLDEVAQLLDEVAUQLB
Putting in word breaks gives the plaintext
The secret password is swordfish.
1.4. Each of the following messages has been encrypted using a simple sub-
stitution cipher. Decrypt them. For your convenience, we have given you a
frequency table and a list of the most common bigrams that appear in the
ciphertext. (If you do not want to recopy the ciphertexts by hand, they can
be downloaded or printed from the web site listed in the preface.)
(a) “A Piratical Treasure”
JNRZR BNIGI BJRGZ IZLQR OTDNJ GRIHT USDKR ZZWLG OIBTM NRGJN
IJTZJ LZISJ NRSBL QVRSI ORIQT QDEKJ JNRQW GLOFN IJTZX QLFQL
WBIMJ ITQXT HHTBL KUHQL JZKMM LZRNT OBIMI EURLW BLQZJ GKBJT
QDIQS LWJNR OLGRI EZJGK ZRBGS MJLDG IMNZT OIHRK MOSOT QHIJL
QBRJN IJJNT ZFIZL WIZTO MURZM RBTRZ ZKBNN LFRVR GIZFL KUHIM
MRIGJ LJNRB GKHRT QJRUU RBJLW JNRZI TULGI EZLUK JRUST QZLUK
EURFT JNLKJ JNRXR S
The ciphertext contains 316 letters. Here is a frequency table:
R J I L Z T N Q B G K U M O S H W F E D X V
Freq 33 30 27 25 24 20 19 16 15 15 13 12 12 10 9 8 7 6 5 5 3 2
4 Exercises for Chapter 1
The most frequent bigrams are: JN (11 times), NR (8 times), TQ (6 times),
and LW,RB,RZ, and JL (5 times each).
(b) “A Botanical Code”
KZRNK GJKIP ZBOOB XLCRG BXFAU GJBNG RIXRU XAFGJ BXRME MNKNG
BURIX KJRXR SBUER ISATB UIBNN RTBUM NBIGK EBIGR OCUBR GLUBN
JBGRL SJGLN GJBOR ISLRS BAFFO AZBUN RFAUS AGGBI NGLXM IAZRX
RMNVL GEANG CJRUE KISRM BOOAZ GLOKW FAUKI NGRIC BEBRI NJAWB
OBNNO ATBZJ KOBRC JKIRR NGBUE BRINK XKBAF QBROA LNMRG MALUF
BBG
The ciphertext contains 253 letters. Here is a frequency table:
B R G N A I U K O J L X M F S E Z C T W P V Q
Freq 32 28 22 20 16 16 14 13 12 11 10 10 8 8 7 7 6 5 3 2 1 1 1
The most frequent bigrams are: NG and RI (7 times each), BU (6 times),
and BR (5 times).
(c) In order to make this one a bit more challenging, we have removed all
occurrences of the word “the” from the plaintext.
“A Brilliant Detective”
GSZES GNUBE SZGUG SNKGX CSUUE QNZOQ EOVJN VXKNG XGAHS AWSZZ
BOVUE SIXCQ NQESX NGEUG AHZQA QHNSP CIPQA OIDLV JXGAK CGJCG
SASUB FVQAV CIAWN VWOVP SNSXV JGPCV NODIX GJQAE VOOXC SXXCG
OGOVA XGNVU BAVKX QZVQD LVJXQ EXCQO VKCQG AMVAX VWXCG OOBOX
VZCSO SPPSN VAXUB DVVAX QJQAJ VSUXC SXXCV OVJCS NSJXV NOJQA
MVBSZ VOOSH VSAWX QHGMV GWVSX CSXXC VBSNV ZVNVN SAWQZ ORVXJ
CVOQE JCGUW NVA
The ciphertext contains 313 letters. Here is a frequency table:
V S X G A O Q C N J U Z E W B P I H K D M L R F
Freq 39 29 29 22 21 21 20 20 19 13 11 11 10 8 8 6 5 5 5 4 3 2 1 1
The most frequent bigrams are: XC (10 times), NV (7 times), and CS,OV,
QA, and SX (6 times each).
Solution to Exercise 1.4.
(a) The message was encrypted using the table:
abcdefghijklmnopqrstuvwxyz
IEBHRWDNTPXUOQLMAGZJKVFCSY
The plaintext reads:
“These characters, as one might readily guess, form a cipher—that is to
say, they convey a meaning; but then, from what is known of Captain Kidd,
I could not suppose him capable of constructing any of the more abstruse
cryptographs. I made up my mind, at once, that this was of a simple species—
such, however, as would appear, to the crude intellect of the sailor, absolutely
insoluble without the key.” (The Gold-Bug, 1843, Edgar Allan Poe)
(b) The message was encrypted using the table:
Exercises for Chapter 1 5
abcdefghijklmnopqrstuvwxyz
RVCXBFSJKQPOEIAWDUNGLTZYMH
The plaintext reads:
“I was, I think, well educated for the standard of the day. My sister and
I had a German governess. A very sentimental creature. She taught us the
language of flowers—a forgotten study nowadays, but most charming. A yellow
tulip, for instance, means Hopeless Love, while a China Aster means I die of
Jealousy at your feet.” (The Four Suspects, 1933, Agatha Christie)
(c) The message was encrypted using the table:
abcdefghijklmnopqrstuvwxyz
SDJWVEHCGLRUZAQPTNOXIMKYBF
The plaintext reads (all occurrences of the word “the” were omitted from the
text before encryption):
I am fairly familiar with all forms of secret writing, and am myself (the)
author of a trifling monograph upon (the) subject, in which I analyze one
hundred separate ciphers, but I confess that this is entirely new to me. (The)
object of those who invented this system has apparently been to conceal that
these characters convey a message, and to give (the) idea that they are (the)
mere random sketches of children. (The Adventure of the Dancing Men, 1903,
Sir Arthur Conan Doyle)
1.5. Suppose that you have an alphabet of 26 letters.
(a) How many possible simple substitution ciphers are there?
(b) A letter in the alphabet is said to be fixed if the encryption of the letter
is the letter itself. How many simple substitution ciphers are there that
leave:
(i) no letters fixed?
(ii) at least one letter fixed?
(iii) exactly one letter fixed?
(iv) at least two letters fixed?
(Part (b) is quite challenging! You might try doing the problem first with an
alphabet of four or five letters to get an idea of what is going on.)
Solution to Exercise 1.5.
(a) We can assign Ato any of 26 letters, then Bto any of the remaining 25
letters, etc. So there are 26! = 403291461126605635584000000 different simple
substitution ciphers.
(b) Let S(n, k) denote the number of permutations of nelements that fix at
least kelements. You might guess that since there are ¡n
k¢ways to choose k
elements to fix and (nk)! permutations of the remaining nkelements,
S(n, k) = µn
k(nk)! Incorrect Formula.(1.1)
6 Exercises for Chapter 1
But this overcounts because any permutation fixing more than nkele-
ments will be counted multiple times. We can, however, get a useful formula
out of this mistake by modifying it somewhat. If we let R(n, k) denote the
number of permutations of nelements that fix exactly kelements, and !(nk)
(the subfactorial of (nk)) denote the number of permutations of nkele-
ments that fix no elements (such permutations are called derangements), then
the following equation holds:
R(n, k) = µn
k!(nk).(1.2)
How can we compute !n? One way would be to consider cycle decompo-
sitions of permutations of n elements, since any derangement of nelements
decomposes into a disjoint union of cycles, with the size of the cycles summing
to n. This, however, is only feasible for relatively small n. It would also be
possible to formulate a recurrence relation, but a method following that tack
would take several steps. We’ll instead use the following fact:
!n=n!#{permutations that fix at least 1 element}.(1.3)
Now if we notice that
#{permutations that fix at least 1 element}=
#{permutations that fix element 1}
∪{permutations that fix element 2}
··· ∪ {permutations that fix element n}(1.4)
and use an analogue of the following formula in probability (often called the
inclusion–exclusion principle):
P(E1E2∪ ··· ∪ En) =
n
X
i=1
P(Ei) + X
i1<i2
P(Ei1Ei2) + . . .
+(1)r+1 X
i1<i2<···<ir
P(Ei1Ei2Eir) + . . .
+(1)n+1P(E1E2∩ ··· ∩ En) (1.5)
we see that
!n=
n
X
i=1
#{permutations that fix element i}
n
X
i1<i2
#{permutations that fix elements i1and i2}+. . .
+(1)r+1 X
i1<i2<···<ir
#{permutations that fix elements i1,i2, . . . ir}+. . .
+(1)n+1#{permutations that fix everything}.(1.6)
Exercises for Chapter 1 7
Given kelements, the number of permutations fixing them is (nk)!
regardless of which kelements you fix, and there are ¡n
k¢ways to choose k
elements to fix. So the above equation becomes
!n=µn
1(n1)! µn
2(n2)! + . . .
+(1)k+1µn
k(nk)! + ··· + (1)n+1(nn)!.(1.7)
Now noticing that
µn
k(nk)! = n!
(nk)!k!(nk)! = n!
k!,(1.8)
the formula (??) becomes
!n=n!
n
X
k=0
(1)k
k!.(1.9)
This sum is somewhat cumbersome to compute when nis large, but notice
that it resembles the series for e1. Thus
n
X
k=0
(1)k
k!=e1
X
k=n+1
(1)k
k!.
Since the series is alternating and the terms are decreasing in magnitude, each
term is larger than the sum of the remaining terms (alternating series test).
So
¯¯¯
n
X
k=0
(1)k
k!e1¯¯¯<1
(n+ 1)!.
Multiplying by n! and using (??) yields
¯¯¯!nn!
e¯¯¯<1
n+ 1.
Hence !nis the closest integer to n!/e.
Now that we’re able to compute !n, we can compute
R(n, k) = µn
k!(nk) = µn
k¹(nk)!
e¼,
and then we can compute S(n, k) using
S(n, k) =
n
X
j=k
R(n, j) = n!
k1
X
j=0
R(n, j).(1.10)
8 Exercises for Chapter 1
(b-i) No letters fixed is R(n, 0) =!nis the nth derangement number. For n=
26 we get
R(26,0) =!26 = b26!/ee=b148362637348470135821287824.964e
= 148362637348470135821287825.
(b-ii) At least one letter fixed is n! minus no letters fixed, so
S(n, 1) = n!R(n, 0) = n!!n=n!− bn!/ee.
Hence
S(26,1) = 26! − b26!/ee= 254928823778135499762712175.
(b-iii) Exactly 1 letter fixed is
R(n, 1) = n·!(n1) = n¹(n1)!
e¼,
so
R(26,1) = 26 ¹25!
e¼= 148362637348470135821287824.
(b-iv) At least two letters fixed is n! minus zero or one letters fixed, so
S(n, 1) = n!R(n, 0) R(1,0) = n!!nn·!(n1)
=n!− bn!/ee − nb(n1)!/ee.
Hence
S(26,1) = 26! − b26!/ee − 26 · b25!/ee= 106566186429665363941424351.
Section. Divisibility and greatest common divisors
1.6. Let a, b, c Z. Use the definition of divisibility to directly prove the
following properties of divisibility. (This is Proposition 1.4.)
(a) If a|band b|c, then a|c.
(b) If a|band b|a, then a=±b.
(c) If a|band a|c, then a|(b+c) and a|(bc).
Solution to Exercise 1.6.
(a) By definition we have b=aA and c=bB for some integers Aand B.
Multiplying gives bc =aAbB, and dividing by byields c=aAB. (Note that b
is nonzero, since zero is not allowed to divide anything.) Hence cis an integer
multiple of a, so a|c.
(b) By definition we have b=aA and a=bB for some integers Aand B.
Multiplying gives ab =aAbB, and dividing by ab yields 1 = AB. (Note that a
Exercises for Chapter 1 9
and bare nonzero, since zero is not allowed to divide anything.) But the only
way for two integers to have product 1 is for A=B=±1.
(c) By definition we have b=au and c=av for some integers uand v. Then
b±c=au ±av =a(u±v),
so both b+cand bcare integer multiples of a. Hence both are divisible
by a.
1.7. Use a calculator and the method described in Remark 1.9 to compute
the following quotients and remainders.
(a) 34787 divided by 353.
(b) 238792 divided by 7843.
(c) 9829387493 divided by 873485.
(d) 1498387487 divided by 76348.
Solution to Exercise 1.7.
(a) a= 34787, b= 353, a/b = 98.54674221, q= 98, r=ab·q= 193.
(b) a= 238792, b= 7843, a/b = 30.44651281, q= 30, r=ab·q= 3502.
(c) a= 9829387493, b= 873485, a/b = 11253.06959249, q= 11253, r=
ab·q= 60788.
(d) a= 1498387487, b= 76348, a/b = 19625.75950909, q= 19625, r=
ab·q= 57987.
1.8. Use a calculator and the method described in Remark 1.9 to compute
the following remainders, without bothering to compute the associated quo-
tients.
(a) The remainder of 78745 divided by 127.
(b) The remainder of 2837647 divided by 4387.
(c) The remainder of 8739287463 divided by 18754.
(d) The remainder of 4536782793 divided by 9784537.
Solution to Exercise 1.8.
(a) a= 78745, b= 127, a/b = 620.03937008.
r127 ·0.03937008 4.99999889,so r= 5.
(b) a= 2837647, b= 4387, a/b = 646.83086392.
r4387 ·0.83086392 3644.99997317,so r= 3645.
(c) a= 8739287463, b= 18754, a/b = 465995.91889730.
r18754 ·0.91889730 17232.99996420,so r= 17233.
(d) a= 4536782793, b= 9784537, a/b = 463.66862254.
r9784537 ·0.66862254 6542161.98166398,so r= 6542162.
10 Exercises for Chapter 1
1.9. Use the Euclidean algorithm to compute the following greatest common
divisors.
(a) gcd(291,252).
(b) gcd(16261,85652).
(c) gcd(139024789,93278890).
(d) gcd(16534528044,8332745927).
Solution to Exercise 1.9.
(a) gcd(291,252) = 3.
(b) gcd(16261,85652) = 161.
(c) gcd(139024789,93278890) = 1.
(d) gcd(16534528044,8332745927) = 43.
1.10. For each of the gcd(a, b) values in Exercise 1.9, use the extended
Euclidean algorithm (Theorem 1.11) to find integers uand vsuch that
au +bv = gcd(a, b).
Solution to Exercise 1.10.
(a) 291 ·13 252 ·15 = 3
(b) 16261 ·85573 85652 ·16246 = 161
(c) 139024789 ·6944509 93278890 ·10350240 = 1
(d) 16534528044 ·81440996 8332745927 ·161602003 = 43
1.11. Let aand bbe positive integers.
(a) Suppose that there are integers uand vsatisfying au +bv = 1. Prove that
gcd(a, b) = 1.
(b) Suppose that there are integers uand vsatisfying au +bv = 6. Is it nec-
essarily true that gcd(a, b) = 6? If not, give a specific counterexample,
and describe in general all of the possible values of gcd(a, b)?
(c) Suppose that (u1, v1) and (u2, v2) are two solutions in integers to the equa-
tion au +bv = 1. Prove that adivides v2v1and that bdivides u2u1.
(d) More generally, let g= gcd(a, b) and let (u0, v0) be a solution in integers
to au +bv =g. Prove that every other solution has the form u=u0+
kb/g and v=v0ka/g for some integer k. (This is the second part of
Theorem 1.11.)
Solution to Exercise 1.11.
(a) Let g= gcd(a, b). Then a=gA and b=gB for some integers Aand
B. Substituting into the given equation au +bv = 1 yields
1 = au +bv =gAu +gBv =g(Au +Bv).
Thus gdivides 1, so we must have g= 1.
(c) No, au+bv = 6 does not imply gcd(a, b) = 6. For example, if gcd(a, b) = 1,
then we can solve aU +bV = 1, and multiplying this equation by 6 gives
a(6U)+b(6V) = 6. For a specific counterexample, take a= 3 and b= 2. Then
Exercises for Chapter 1 11
a·6 + b·(6) = 6,
but gcd(a, b) = 1.
In general, if au +bv =chas a solution, then cdivides gcd(a, b). To see
this, let g= gcd(a, b) and divide cby gwith remainder, say
c=gq +rwith 0 r < g.
We know that we can find a solution to g=ax +by, so we get
au +bv =c=gq +r= (ax +by)q+r.
Rearranging this yields
a(uxq) + b(vyq) = r.
In other words, we have a solution to aX +bY =rwith 0 r < g. The
left-hand side is divisible by g. (Remember that g= gcd(a, b), so gdivides
both aand b.) Hence g|r. But the only rsatisfying 0 r < g and g|ris
r= 0. Therefore c=gq, which completes the proof that gcd(a, b) divides c.
(d) We are given that
au +bv =gand au0+bv0=g.
Subtracting and rearranging yields
a(uu0) = b(vv0).
Dividing both sides by ggives
a
g(uu0) = b
g(vv0).
We observe that gcd(a/g, b/g) = 1. (To see this, we note that (a/g)u0+
(b/g)v0= 1, so (a) tells us that gcd(a/g, b/g) = 1.) Thus a/g divides (b/g)(v
v0) and is relatively prime to (b/g), so it must divide vv0. Hence
vv0=a
gxfor some integer x.
The same reasoning tells us that
uu0=b
gyfor some integer y.
Hence
u=u0+b
gyand v=v0+a
gx.
Substituting into the equation a
g(uu0) = b
g(vv0) from above yields
12 Exercises for Chapter 1
a
g
b
gy=b
g
a
gx,
so y=x. If we use the letter kinstead of the letter y, we have shown that
u=u0+b
gkand v=v0a
gk,
which is exactly what we were trying to prove.
1.12. The method for solving au +bv = gcd(a, b) described in Section 1.2 is
somewhat inefficient. This exercise describes a method to compute uand v
that is well suited for computer implementation. In particular, it uses very
little storage.
(a) Show that the following algorithm computes the greatest common divi-
sor gof the positive integers aand b, together with a solution (u, v) in
integers to the equation au +bv = gcd(a, b).
1. Set u= 1,g=a,x= 0, and y=b
2. If y= 0, set v= (gau)/b and return the values (g, u, v)
3. Divide gby ywith remainder, g=qy +t, with 0t < y
4. Set s=uqx
5. Set u=xand g=y
6. Set x=sand y=t
7. Go To Step (2)
(b) Implement the above algorithm on a computer using the computer lan-
guage of your choice.
(c) Use your program to compute g= gcd(a, b) and integer solutions to the
equation au +bv =gfor the following pairs (a, b).
(i) (527,1258)
(ii) (228,1056)
(iii) (163961,167181)
(iv) (3892394,239847)
(d) What happens to your program if b= 0? Fix the program so that it deals
with this case correctly.
(e) It is often useful to have a solution with u > 0. Modify your program so
that it returns a solution with u > 0 and uas small as possible. [Hint.
If (u, v) is a solution, then so is (u+b/g, v a/g).] Redo (c) using your
modified program.
Solution to Exercise 1.12.
(a) A solution for this exercise is not currently available.
(b) A solution for this exercise will not be provided.
(c) and (e): (i) 527 ·43 1258 ·18 = 17
(ii) 228 ·51 1056 ·11 = 12
(iii) 163961 ·4517 167181 ·4430 = 7
Exercises for Chapter 1 13
(iv) 3892394 ·59789 239847 ·970295 = 1
(d) If b= 0, then there is a “division by zero” error in step 2. So the program
should check if b= 0, if in that case it should return (a, 1,0).
1.13. Let a1, a2, . . . , akbe integers with gcd(a1, a2, . . . , ak) = 1, i.e., the
largest positive integer dividing all of a1, . . . , akis 1. Prove that the equa-
tion
a1u1+a2u2+··· +akuk= 1
has a solution in integers u1, u2, . . . , uk. (Hint. Repeatedly apply the extended
Euclidean algorithm, Theorem 1.11. You may find it easier to prove a more
general statement in which gcd(a1, . . . , ak) is allowed to be larger than 1.)
Solution to Exercise 1.13.
We prove more generally that for any integers a1, . . . , ak(not all zero),
there is a solution to
a1u1+a2u2+··· +akuk= gcd(a1, . . . , ak).
We give the proof using induction on k. If k= 1 there is nothing to prove,
since a1·1 = gcd(a1). For k= 2, this is already proven in the extended
Euclidean algorithm. So assume now that we know the result for fewer than k
integers, where k3, and we want to prove it for kintegers. By the induction
hypothesis, we can find a solution to
a1u1+a2u2+··· +ak1uk1= gcd(a1, . . . , ak1).
To ease notation, we let b= gcd(a1, . . . , ak1). We apply the extended Eu-
clidean algorithm to the two numbers band ak, which gives us a solution
to
bv +akw= gcd(b, ak).
Multiplying the earlier equation by vand subtituting this equation gives
a1u1v+a2u2v+··· +ak1uk1v= gcd(a1, . . . , ak1)v
=bv by definition of b,
=akw+ gcd(b, ak).
Hence
a1u1v+a2u2v+··· +ak1uk1v+akw= gcd(b, ak).
This completes the proof, since from the definition of gcd as the largest integer
dividing all of the listed integers, it’s clear that
gcd(b, ak) = gcd¡gcd(a1, . . . , ak1), ak¢= gcd(a1, . . . , ak1, ak).
Section. Modular arithmetic
14 Exercises for Chapter 1
1.14. Let m1 be an integer and suppose that
a1a2(mod m) and b1b2(mod m).
Prove that
a1±b1a2±b2(mod m) and a1·b1a2·b2(mod m).
(This is Proposition 1.13(a).)
Solution to Exercise 1.14.
1.15. Write out the following tables for Z/mZand (Z/mZ), as we did in
Figures 1.4 and 1.5.
(a) Make addition and multiplication tables for Z/3Z.
(b) Make addition and multiplication tables for Z/6Z.
(c) Make a multiplication table for the unit group (Z/9Z).
(d) Make a multiplication table for the unit group (Z/16Z).
Solution to Exercise 1.15.
(a)
+ 0 1 2
0 0 1 2
1 1 2 0
2 2 0 1
·012
0 0 0 0
1 0 1 2
2 0 2 1
(b)
+ 012345
0 012345
1 123450
2 234501
3 345012
4 450123
5 501234
·012345
0 000000
1 012345
2 024024
3 030303
4 042042
5 054321
(c)
·124578
1 124578
2 248157
4 487215
5 512784
7 751842
8 875421
Exercises for Chapter 1 15
(d)
·1 3 5 7 9 11 13 15
1 1 3 5 7 9 11 13 15
3 3 9 15 5 11 1 7 13
5 5 15 9 3 13 7 1 11
7 7 5 3 1 15 13 11 9
9 9 11 13 15 1 3 5 7
11 11 1 7 13 3 9 15 5
13 13 7 1 11 5 15 9 3
15 15 13 11 9 7 5 3 1
1.16. Do the following modular computations. In each case, fill in the box
with an integer between 0 and m1, where mis the modulus.
(a) 347 + 513 (mod 763).
(b) 3274 + 1238 + 7231 + 6437 (mod 9254).
(c) 153 ·287 (mod 353).
(d) 357 ·862 ·193 (mod 943).
(e) 5327 ·6135 ·7139 ·2187 ·5219 ·1873 (mod 8157).
(Hint. After each multiplication, reduce modulo 8157 before doing the
next multiplication.)
(f) 1372(mod 327).
(g) 3736(mod 581).
(h) 233·195·114(mod 97).
Solution to Exercise 1.16.
(a) 347 + 513 97 (mod 763).
(b) 3274 + 1238 + 7231 + 6437 8926 (mod 9254).
(c) 153 ·287 139 (mod 353).
(d) 357 ·862 ·193 636 (mod 943).
(e) 5327 ·6135 ·7139 ·2187 ·5219 ·1873 603 (mod 8157).
(f) 1372130 (mod 327).
(g) 3736463 (mod 581).
(h) 233·195·11493 (mod 97).
1.17. Find all values of xbetween 0 and m1 that are solutions of the
following congruences. (Hint. If you can’t figure out a clever way to find the
solution(s), you can just substitute each value x= 1, x= 2,. . . , x=m1
and see which ones work.)
(a) x+ 17 23 (mod 37).
(b) x+ 42 19 (mod 51).
(c) x23 (mod 11).
(d) x22 (mod 13).
(e) x21 (mod 8).
16 Exercises for Chapter 1
(f) x3x2+ 2x20 (mod 11).
(g) x1 (mod 5) and also x2 (mod 7). (Find all solutions modulo 35,
that is, find the solutions satisfying 0 x34.)
Solution to Exercise 1.17.
(a) x23 17 6 (mod 37).
(b) x19 42 ≡ −23 28 (mod 51).
(c) The squares modulo 11 are 020, 121, 224, 329, 4216 5,
etc. The full list is {0,1,4,9,5,3,3,5,9,4,1}. Thus 522 (mod 11) and
622 (mod 11), so there are two solutions, x= 5 and x= 6 .
(d) The squares modulo 13 are {0,1,4,9,3,12,10,10,12,3,9,4,1}. Thus x2
2 (mod 13) has no solutions .
(e) The solutions to x21 (mod 8) are x= 1, x= 3, x= 5 and x= 7 .
(f) Plugging x= 0,1,2, . . . , 10 into x3x2+ 2x2 and reducing modulo 11,
we find the three solutions x= 1, x= 3, and x= 8 .
(g) One method is to try all values x= 0,1,2, . . . , 34. A faster method is
to list the solutions to x1 (mod 5), namely 1,6,11,16,21,26,31, . . . and
reduce them modulo 7 to see which ones are congruent to 2 modulo 7. Thus
working modulo 7,
11,66,11 4,16 2,21 0,26 5,31 3.
Thus the solution is x= 16 .
1.18. Suppose that ga1 (mod m) and that gb1 (mod m). Prove that
ggcd(a,b)1 (mod m).
Solution to Exercise 1.18.
The extended Euclidean algorithm says that there are integers uand v
satisfying au +bv = gcd(a, b). Then
ggcd(a,b)gau+bv (ga)u·(gb)v1u·1v1 (mod p).
1.19. Prove that if a1and a2are units modulo m, then a1a2is a unit modulo
m.
Solution to Exercise 1.19.
By definition of unit, there are numbers b1and b2so that
a1b11 (mod m) and a2b21 (mod m).
Then
(a1a2)(b1b2)(a1b1)(a2b2)1·11 (mod m),
so a1a2is a unit. Its inverse is b1b2.
Exercises for Chapter 1 17
1.20. Prove that mis prime if and only if φ(m) = m1, where φis Euler’s
phi function.
Solution to Exercise 1.20.
Suppose first that mis prime. Let kbe any number between 1 and m1
and let d= gcd(k, m). Then d|m, so the fact that mis prime tells us that
either d= 1 or d=m. But also d|kand 1 k < m, so we have d <
m. Hence d= 1. This proves that every number kbetween 1 and m1
satisfies gcd(k, m) = 1. Hence
φ(m) = #©1k < m : gcd(k, m) = 1ª= #{1,2,3, . . . , m 1}=m1.
Next suppose that φ(m) = m1. This means that every number kbe-
tween 1 and m1 satisfies gcd(k, m) = 1. Suppose that ddivides mand
that d6=m. Then 1 dm1, so gcd(d, m) = 1. But the fact that d
divides mimplies that gcd(d, m) = d. Hence d= 1. This proves that the only
divisors of mare 1 and m, so mis prime.
1.21. Let mZ.
(a) Suppose that mis odd. What integer between 1 and m1 equals 21mod m?
(b) More generally, suppose that m1 (mod b). What integer between 1
and m1 is equal to b1mod m?
Solution to Exercise 1.21.
(a) The fact that mis odd means that m+1
2is an integer, and clearly
2·m+ 1
2=m+ 1 1 (mod m).
(b) The assumption that m1 (mod b) means that m1
bis an integer, so
we have
b·m1
b=m1≡ −1 (mod m).
This is almost what we want, so multiply by 1 to get
b·1m
b= 1 m1 (mod m).
Unfortunately, 1m
bis negative, but we can add on multiples of mwithout
changing its value modulo m. Thus 1m
b+m=1+(b1)m
bis an integer and
b·1+(b1)m
b= 1 + (b1)m1 (mod m).
Hence b1mod mis equal to 1+(b1)m
b.
1.22. Let mbe an odd integer and let abe any integer. Prove that 2m+a2
can never be a perfect square. (Hint. If a number is a perfect square, what
are its possible values modulo 4?)
18 Exercises for Chapter 1
Solution to Exercise 1.22.
Any number squared is either 0 or 1 modulo 4. But
2m+a22 + a2(2 + 0 2 if ais even,
2 + 1 3 if ais odd.
Thus 2m+a2is either 2 or 3 modulo 4, so it can never be a perfect square.
1.23. (a) Find a single value xthat simultaneously solves the two congruences
x3 (mod 7) and x4 (mod 9).
(Hint. Note that every solution of the first congruence looks like x= 3+7y
for some y. Substitute this into the second congruence and solve for y;
then use that to get x.)
(b) Find a single value xthat simultaneously solves the two congruences
x13 (mod 71) and x41 (mod 97).
(c) Find a single value xthat simultaneously solves the three congruences
x4 (mod 7), x 5 (mod 8),and x11 (mod 15).
(d) Prove that if gcd(m, n) = 1, then the pair of congruences
xa(mod m) and xb(mod n)
has a solution for any choice of aand b. Also give an example to show
that the condition gcd(m, n) = 1 is necessary.
Solution to Exercise 1.23.
(a) x= 31 (b) x= 5764 (c) x= 221
(d) The solutions to the first congruence look like x=a+my for any
integer y. Substituting into the second congruence yields
a+my b(mod n),
so we want to find a value of zsuch that
a+my b=nz.
In other words, we need integers yand zsatisfying
my nz =ba.
We are given that gcd(m, n) = 1, so we can find integers uand vsatisfying
mu +nv = 1. Multiplying this by bagives
mu(ba) + nv(ba) = ba,
Exercises for Chapter 1 19
so we can take y=u(ba) and z=v(ba). Then we have x=a+my =
a+mu(ba).
To summarize, we first solve mu +nv = 1 and then we take
x=a+mu(ba) = a+ (1 nv)(ba) = b+nv(ba).
The two expressions for xshow that xa(mod m) and xv(mod n).
This exercise is a special case of the Chinese remainder theorem, which is
covered in Chapter 2.
1.24. Let N,g, and Abe positive integers (note that Nneed not be
prime). Prove that the following algorithm, which is a low-storage variant
of the square-and-multiply algorithm described in Section 1.3.2, returns the
value gA(mod N). (In Step 4 we use the notation bxcto denote the greatest
integer function, i.e., round xdown to the nearest integer.)
Input. Positive integers N,g, and A.
1. Set a=gand b= 1.
2. Loop while A > 0.
3. If A1 (mod 2), set b=b·a(mod N).
4. Set a=a2(mod N) and A=bA/2c.
5. If A > 0, continue with loop at Step 2.
6. Return the number b, which equals gA(mod N).
Solution to Exercise 1.24.
*** fill in solution
1.25. Use the square-and-multiply algorithm described in Section 1.3.2, or the
more efficient version in Exercise 1.24, to compute the following powers.
(a) 17183 (mod 256).
(b) 2477 (mod 1000).
(c) 11507 (mod 1237).
Solution to Exercise 1.25.
(a) 183 = 1 + 2 + 22+ 24+ 25+ 27,17183 (mod 256) = 113 .
(b) 477 = 1 + 22+ 23+ 24+ 26+ 27+ 28,2477 (mod 1000) = 272
(c) 507 = 1 + 2 + 23+ 24+ 25+ 26+ 27+ 28,11507 (mod 1237) = 322 .
Section. Prime numbers, unique factorization, and finite fields
1.26. Let {p1, p2, . . . , pr}be a set of prime numbers, and let
N=p1p2···pr+ 1.
20 Exercises for Chapter 1
Prove that Nis divisible by some prime not in the original set. Use this fact
to deduce that there must be infinitely many prime numbers. (This proof of
the infinitude of primes appears in Euclid’s Elements. Prime numbers have
been studied for thousands of years.)
Solution to Exercise 1.26.
Let qbe any prime that divides N. (Since N2, we know that it must
be divisible by some prime.) Suppose that qwere equal to some pi. Then we
would have
1 = Np1p2···pr0 (mod q),
since qwould divide both of the terms Nand p1···pr. But then q|1, which
is impossible. Therefore qis not equal to any of the pi’s.
Next suppose that there were only finitely many primes. That means we
can list them, say p1, p2, . . . , pr. But from the first part of the exercise, we can
create a new prime that’s not in our list. This contradicts the assumption that
there are finitely many primes, and hence proves that there must be infinitely
many primes.
1.27. Without using the fact that every integer has a unique factorization
into primes, prove that if gcd(a, b) = 1 and if a|bc, then a|c. (Hint. Use the
fact that it is possible to find a solution to au +bv = 1.)
Solution to Exercise 1.27.
From the extended Euclidean algorithm, we can solve au+bv = 1. Multiply
by cto get acu +bcv =c. We are given that a|bc, so there is an integer d
satisfying bc =ad. Substituting this gives acu +adv =c. Thus a(cu +dv) = c,
which shows that a|c.
1.28. Compute the following ordpvalues:
(a) ord2(2816).
(b) ord7(2222574487).
(c) ordp(46375) for each of p= 3, 5, 7, and 11.
Solution to Exercise 1.28.
(a) ord2(2816) = 8.
(b) ord7(2222574487) = 5.
(c) Let a= 46375. Then ord3(a) = 0, ord5(a) = 3, ord7(a) = 1,
ord11(a) = 0.
1.29. Let pbe a prime number. Prove that ordphas the following proper-
ties.
(a) ordp(ab) = ordp(a) + ordp(b). (Thus ordpresembles the logarithm func-
tion, since it converts multiplication into addition!)
(b) ordp(a+b)min©ordp(a),ordp(b)ª.
(c) If ordp(a)6= ordp(b), then ordp(a+b) = min©ordp(a),ordp(b)ª.
A function satisfying properties (a) and (b) is called a valuation.
Exercises for Chapter 1 21
Solution to Exercise 1.29.
(a) By definition of ordp, we have
a=pordp(a)Aand b=pordp(b)Bwith p-Aand p-B.
Then
ab =pordp(a)A·pordp(b)B=pordp(a)+ordp(b)AB with p-AB,
so by definition,
ordp(ab) = ordp(a) + ordp(b).
(b) We continue with the notation from (a) and, without loss of generality,
we switch aand bif necessary so that ordp(a)ordp(b). Then
a+b=pordp(a)A+pordp(b)B=pordp(b)³pordp(a)ordp(b)A+B´.
Thus pordp(b)|a+b, so by definition of ordpwe have
ordp(a+b)ordp(b).
(Note that we’ve set things up so that ordp(b) = min{ordp(a),ordp(b)}, so
this is the result that we want.)
(c) We continue with the notation from (a) and (b), but for this part we are
given that ordp(a)>ordp(b). We also know that p-B, so it follows that
p-³pordp(a)ordp(b)A+B´,
since the exponent of pon the first term is positive. Hence pordp(b)is the
largest power of pdividing a+b, which proves that
ordp(a+b) = ordp(b).
Section. Powers and primitive roots in finite fields
1.30. For each of the following primes pand numbers a, compute a1mod p
in two ways: (i) Use the extended Euclidean algorithm. (ii) Use the fast power
algorithm and Fermat’s little theorem. (See Example 1.28.)
(a) p= 47 and a= 11.
(b) p= 587 and a= 345.
(c) p= 104801 and a= 78467.
Solution to Exercise 1.30.
(a) (i) We use the extended Euclidean algorithm to solve
11u+ 47v= 1.
22 Exercises for Chapter 1
The solution is (u, v) = (17,4), so 111≡ −17 30 (mod 47). (ii) Fermat’s
little theorem gives
1111145 30 (mod 47).
(b) (i) We use the extended Euclidean algorithm to solve
345u+ 587v= 1.
The solution is (u, v) = (114,67), so 3451114 (mod 587). (ii) Fermat’s
little theorem gives
3451345585 114 (mod 587).
(c) (i) We use the extended Euclidean algorithm to solve
78467u+ 104801v= 1.
The solution is (u, v) = (1763,1320), so 7846711763 (mod 104801). (ii)
Fermat’s little theorem gives
78467178467104799 1763 (mod 104801).
1.31. Let pbe a prime and let qbe a prime that divides p1.
(a) Let aF
pand let b=a(p1)/q. Prove that either b= 1 or else bhas
order q. (Recall that the order of bis the smallest k1 such that bk= 1
in F
p.Hint. Use Proposition 1.30.)
(b) Suppose that we want to find an element of F
pof order q. Using (a), we
can randomly choose a value of aF
pand check whether b=a(p1)/q
satisfies b6= 1. How likely are we to succeed? In other words, compute
the value of the ratio
#{aF
p:a(p1)/q 6= 1}
#F
p
.
(Hint. Use Theorem 1.31.)
Solution to Exercise 1.31.
(a) Let kbe the order of b, i.e., the smallest exponent such that bk= 1. We
know that bq=ap1= 1 from Fermat’s little theorem. Then Proposition 1.30
tells us that kdivides q, and since qis prime, it follows that either k=q
or k= 1. Thus either bhas order q, or else it has order 1, in which case b=
b1= 1.
(b) Let gF
pbe a primitive root. Then every aF
phas the form gifor
some 0 i < p 1. We’ll count the number of awith a(p1)/q = 1. Thus
Exercises for Chapter 1 23
#{aF
p:a(p1)/q = 1}= #{0i < p 1 : (gi)(p1)/q = 1}
= #{0i < p 1 : gi(p1)/q = 1}.
Since ghas order p1, we have gk= 1 if and only if p1|k. Hence
gi(p1)/q = 1 p1|i(p1)/q q|i.
Hence
#{aF
p:a(p1)/q = 1}= #{0i < p 1 : q|i}=p1
q.
It follows that
#{aF
p:a(p1)/q 6= 1}=p1#{aF
p:a(p1)/q = 1}
=p1p1
q= (p1) µ11
q.
Hence #{aF
p:a(p1)/q 6= 1}
#F
p
= 1 1
q,
so if qis large, we have a very good chance of succeeding on our first try.
1.32. Recall that gis called a primitive root modulo pif the powers of ggive
all nonzero elements of Fp.
(a) For which of the following primes is 2 a primitive root modulo p?
(i) p= 7 (ii) p= 13 (iii) p= 19 (iv) p= 23
(b) For which of the following primes is 3 a primitive root modulo p?
(i) p= 5 (ii) p= 7 (iii) p= 11 (iv) p= 17
(c) Find a primitive root for each of the following primes.
(i) p= 23 (ii) p= 29 (iii) p= 41 (iv) p= 43
(d) Find all primitive roots modulo 11. Verify that there are exactly φ(10) of
them, as asserted in Remark 1.33.
(e) Write a computer program to check for primitive roots and use it to find
all primitive roots modulo 229. Verify that there are exactly φ(229) of
them.
(f) Use your program from (e) to find all primes less than 100 for which 2 is
a primitive root.
(g) Repeat the previous exercise to find all primes less than 100 for which 3
is a primitive root. Ditto to find the primes for which 4 is a primitive
root.
Solution to Exercise 1.32.
(a) (i) No. (ii) Yes. (iii) Yes. (iv) No.
(b) (i) Yes. (ii) Yes. (iii) No. (iv) Yes.
(c) In each case, we list the smallest primitive root
24 Exercises for Chapter 1
(i) p= 23, g= 5. (ii) p= 29, g= 2. (iii) p= 41, g= 6. (iv) p= 43, g= 3.
(d) The primitive roots modulo 11 are {2,6,7,8}. There are φ(10) = 4 of
them.
(e) The primitive roots modulo 229 are
{6,7,10,23,24,28,29,31,35,38,39,40,41,47,50,59,63,65,66,
67,69,72,73,74,77,79,87,90,92,96,98,102,105,110,112,113,
116,117,119,124,127,131,133,137,139,142,150,152,155,156,157,
160,162,163,164,166,170,179,182,188,189,190,191,194,198,200,
201,205,206,219,222,223}.
There are exactly φ(228) = 72 of them.
(f) 2 is a primitive root modulo pfor p∈ {3,5,11,1319,29,37,53,59,61,67,83}
and for no other primes less than 100. It is conjectured that 2 is a primitive
root for infinitely many primes (Artin’s conjecture).
(g) 3 is a primitive root modulo pfor p∈ {5,7,17,19,29,31,43,53,79,89}
and for no other primes less than 100. On the other hand, there are no primes
for which 4 is a primitive root. This is because 4 = 22is a square, so the
powers of 4 can hit at most half of the possible nonzero values modulo p.
1.33. Let pbe a prime such that q=1
2(p1) is also prime. Suppose that g
is an integer satisfying
g6≡ ±1 (mod p) and gq6≡ 1 (mod p).
Prove that gis a primitive root modulo p.
Solution to Exercise 1.33.
Let nbe the order of g, i.e., the smallest power of gthat is congruent to 1.
Then ndivides p1 from Proposition 1.30. Since p1 = 2qwith qprime,
this means that
n= 1 orn= 2 orn=qorn= 2q.
We are given that g6≡ ±1 (mod p), so n6= 1 and n6= 2, and we are also given
that gq6≡ ±1 (mod p), so n6=q.The only value left is n= 2q. This proves
that n=p1, so gis a primitive root modulo p.
1.34. This exercise begins the study of squares and square roots modulo p.
(a) Let pbe an odd prime number and let bbe an integer with p-b. Prove
that either bhas two square roots modulo por else bhas no square roots
modulo p. In other words, prove that the congruence
X2b(mod p)
has either two solutions or no solutions in Z/pZ. (What happens for p=
2? What happens if p|b?)
Exercises for Chapter 1 25
(b) For each of the following values of pand b, find all of the square roots
of bmodulo p.
(i) (p, b) = (7,2) (ii) (p, b) = (11,5)
(iii) (p, b) = (11,7) (iv) (p, b) = (37,3)
(c) How many square roots does 29 have modulo 35? Why doesn’t this con-
tradict the assertion in (a)?
(d) Let pbe an odd prime and let gbe a primitive root modulo p. Then
any number ais equal to some power of gmodulo p, say agk(mod p).
Prove that ahas a square root modulo pif and only if kis even.
Solution to Exercise 1.34.
(a) If X=a1and X=a2are square roots of bmodulo p, then pdivides
a2
1band pdivides a2
2b, so pdivides their difference
(a2
1b)(a2
2b) = a2
1a2
2= (a1a2)(a1+a2).
It follows that pdivides either a1a2or a1+a2. If the former, then a1a2
(mod p), and if the latter, then a1≡ −a2(mod p). Thus there are at most
two possibilities.
Further, if there is one solution aand if p3, then pais a second
solution different from a, so if there are any solutions, then there are exactly
two solutions. On the other hand, if p= 2, then X2b(mod p) always has
exactly one solution, namely X=b.
(b) (i) 3 and 4.
(ii) 4 and 7.
(iii) None.
(iv) 15 and 22.
(c) 8, 13, 22, and 27 are all solutions to X229 (mod 35), so 29 has four
square roots modulo 35. This does not contradict (a), since the modulus 35
is not prime.
(d) Suppose first that kis even, say k= 2j. Then
agkg2j(gj)2(mod p),
so ais a square modulo p.
Next suppose ais a square, say ab2(mod p). Since gis a primitive root,
we can write bgi(mod p) for some exponent i. Then
gkab2(gi)2g2i(mod p).
Thus gk2i1 (mod p), and the fact that gis a primitive root implies
that p1 divides k2i. But p1 is even, hence 2 divides k2i, so 2
divides k.
1.35. Let p3 be a prime and suppose that the congruence
X2b(mod p)
has a solution.
26 Exercises for Chapter 1
(a) Prove that for every exponent e1 the congruence
X2b(mod pe) (1.11)
has a solution. (Hint. Use induction on e. Build a solution modulo pe+1
by suitably modifying a solution modulo pe.)
(b) Let X=αbe a solution to X2b(mod p). Prove that in (a), we can find
a solution X=βto X2b(mod pe) that also satisfies βα(mod p).
(c) Let βand β0be two solutions as in (b). Prove that ββ0(mod pe).
(d) Use Exercise 1.34 to deduce that the congruence (1.14) has either two
solutions or no solutions modulo pe.
Solution to Exercise 1.35.
We do (a), (b), and (c) simultaneously. We are given that X=αis a
solution to X2b(mod p). We are going to prove by induction that for
every e1 there is a unique value βmod pesatisfying both
β2b(mod pe) and βα(mod p).
The case e= 1 is given to us, we must take β=α. Now suppose that we
have a value of βthat works for e, and we ask for all solutions that work for
e+ 1. Note that if γis a solution for e+ 1, then γmod peis a solution for e.
So by the uniqueness part of the induction hypothesis, we would need to have
γβ(mod pe). In other words, if there are any solutions γfor e+ 1, then γ
is forced to have the form
γ=β+ypefor some integer y.
What we want to do is show that there is a unique value of ymodulo pthat
makes γinto a solution of X2b(mod pe+1).
We also want to use the fact that βis a solution to X2b(mod pe). This
means that
β2=b+peBfor some integer B.
Now we substitute γ=β+ypeinto the congruence X2b(mod pe+1) and
try to solve for y. Thus
(β+ype)2b(mod pe+1)
β2+ 2ype+y2p2eb(mod pe+1)
β2+ 2ypeb(mod pe+1) since 2ee+ 1,
b+peB+ 2ypeb(mod pe+1) since β2=b+peB,
pe(B+ 2y)0 (mod pe+1).
Thus we need to solve
B+ 2y0 (mod p).
Exercises for Chapter 1 27
This has a unique solution for y. (Note that pis assumed to be an odd prime.
If p= 2, the argument does not work.) We can even solve explicitly,
yp1
2B(mod p).
This completes the proof that for every e1 there exists a unique value of β
(mod pe) satisfying
β2b(mod pe) and βα(mod p),
which gives all of the statements in (a), (b), and (b).
(d) From the earlier exercise we know that X2b(mod p) has either 0
or 2 solutions. If it has no solutions, there there certainly aren’t any solutions
to X2b(mod pe) for e2, since any such solution could always be
reduced modulo p. On the other hand, if X2b(mod p) has two solutions,
then (a), (b), and (c) together imply that there are also two solutions to
X2b(mod pe) for each e1, since the solutions to X2b(mod p) are
matched up one-to-one with the solutions to X2b(mod pe).
This exercise is a very special case of Hensel’s lemma.
1.36. Compute the value of
2(p1)/2(mod p)
for every prime 3 p < 20. Make a conjecture as to the possible values of
2(p1)/2(mod p) when pis prime and prove that your conjecture is correct.
Solution to Exercise 1.36.
p= 3 21= 2 2
p= 5 22= 4 4
p= 7 23= 8 1
p= 11 25= 32 10
p= 13 26= 64 12
p= 17 28= 256 1
p= 19 29= 512 18
Conjecture: 2(p1)/2is congruent to either 1 or p1 modulo p.
Proof : Let a= 2(p1)/2. Then a22p11 (mod p) by Fermat’s little
theorem. Therefore a≡ ±1 (mod p). To see this last fact, note that p|(a21),
so p|(a1)(a+ 1), so since pis prime, it divides one of a1 or a+ 1, which
is just another way of saying that a≡ ±1 (mod p).
Section. Cryptography by hand
28 Exercises for Chapter 1
1.37. Write a 2 to 5 page paper on one of the following topics, including both
cryptographic information and placing events in their historical context:
(a) Cryptography in the Arab world to the 15th century.
(b) European cryptography in the 15th and early 16th centuries.
(c) Cryptography and cryptanalysis in Elizabethan England.
(d) Cryptography and cryptanalysis in the 19th century.
(e) Cryptography and cryptanalysis during World War I.
(f) Cryptography and cryptanalysis during World War II.
(Most of these topics are too broad for a short term paper, so you should
choose a particular aspect on which to concentrate.)
Solution to Exercise 1.37.
A solution for this exercise will not be provided.
1.38. Ahomophonic cipher is a substitution cipher in which there may be
more than one ciphertext symbol for each plaintext letter. Here is an example
of a homophonic cipher, where the more common letters have several possible
replacements.
a b c d e f g h i j k l m n o p q r s t u v w x y z
! 4 # $ 1 % & * ( ) 3 2 = + [ 9 ] { } : ; 7<>5?
6%♦ ∧ & 8 ⊗ ♠
Θ • ¯ ⊕ ⇐
. ⇒ -
Decrypt the following message.
( % ♠ ⇒ # 4 :6% ¯ [8%2[7⇓ ♣ & ♥ 5¯ ∇
Solution to Exercise 1.38.
( % ♠ ⇒ # 4 :6% ¯ [8
I f m u s i c b e t h e f o o d o
% 2 [ 7 ♣ & ♥ 5¯ ∇
f l o v e p l a y o n
From Shakespeare’s Twelfth Night:If music be the food of love, play
on...
1.39. Atransposition cipher is a cipher in which the letters of the plaintext
remain the same, but their order is rearranged. Here is a simple example in
which the message is encrypted in blocks of 25 letters at a time.1Take the
given 25 letters and arrange them in a 5-by-5 block by writing the message
horizontally on the lines. For example, the first 25 letters of the message
Now is the time for all good men to come to the aid...
is written as
1If the number of letters in the message is not an even multiple of 25, then extra random
letters are appended to the end of the message.
Exercises for Chapter 1 29
NOWIS
THETI
MEFOR
ALLGO
ODMEN
Now the cipehrtext is formed by reading the letters down the columns, which
gives the ciphertext
NTMAO OHELD WEFLM ITOGE SIRON.
(a) Use this transposition cipher to encrypt the first 25 letters of the message
Four score and seven years ago our fathers...
(b) The following message was encrypted using this transposition cipher. De-
crypt it.
WNOOA HTUFN EHRHE NESUV ICEME
(c) There are many variations on this type of cipher. We can form the letters
into a rectangle instead of a square, and we can use various patterns to
place the letters into the rectangle and to read them back out. Try to
decrypt the following ciphertext, in which the letters were placed hor-
izontally into a rectangle of some size and then read off vertically by
columns. WHNCE STRHT TEOOH ALBAT DETET SADHE
LEELL QSFMU EEEAT VNLRI ATUDR HTEEA
(For convenience, we’ve written the ciphertext in 5 letter blocks, but that
doesn’t necessarily mean that the rectangle has a side of length 5.)
Solution to Exercise 1.39.
(a) Ciphertext: FCNER OODNS URSYA REEEG SAVAO
F O U R S
C O R E A
N D S E V
E N Y E A
R S A G O
(b) Plaintext: When in the course of human events it becomes necessary...
Hopefully everyone recognizes the first few words of the American Decla-
ration of Independence.
W H E N I
N T H E C
O U R S E
O F H U M
A N E V E
30 Exercises for Chapter 1
(c) Plaintext: We hold these truths to be self-evident, that all men
are created equal, that they are endowed by their Creator...
Another excerpt from the Declaration of Independence. It was encrypted
using a 15-by-4 rectangle.
W E H O L D T H E S E T R U T
H S T O B E S E L F E V I D E
N T T H A T A L L M E N A R E
C R E A T E D E Q U A L T H A
Section. Symmetric ciphers and asymmetric ciphers
1.40. Encode the following phrase (including capitalization, spacing and
punctuation) into a string of bits using the ASCII encoding scheme given
in Table 1.10.
Bad day, Dad.
Solution to Exercise 1.40.
Bad day,
66 97 100 32 100 97 121 44
01000010 01100001 01100100 00100000 01100100 01100001 01111001 00101100
D a d .
32 68 97 100 46
00100000 01000100 01100001 01100100 00101110
Thus the phrase “Bad day, Dad.” becomes the ASCII list of bits
0100001001100001011001000010000001100100011000010111
1001001011000010000001000100011000010110010000101110
1.41. Consider the affine cipher with key k= (k1, k2) whose encryption and
decryption functions are given by (1.11) on page 43.
(a) Let p= 541 and let the key be k= (34,71). Encrypt the message m=
204. Decrypt the ciphertext c= 431.
(b) Assuming that pis public knowledge, explain why the affine cipher is
vulnerable to a chosen plaintext attack. (See Property 4 on page 38.)
How many plaintext/ciphertext pairs are likely to be needed in order to
recover the private key?
(c) Alice and Bob decide to use the prime p= 601 for their affine cipher. The
value of pis public knowledge, and Eve intercepts the ciphertexts c1=
324 and c2= 381 and also manages to find out that the corresponding
plaintexts are m1= 387 and m2= 491. Determine the private key and
then use it to encrypt the message m3= 173.
(d) Suppose now that pis not public knowledge. Is the affine cipher still
vulnerable to a chosen plaintext attack? If so, how many plaintext/cipher-
text pairs are likely to be needed in order to recover the private key?
Exercises for Chapter 1 31
Solution to Exercise 1.41.
(a) The encryption of m= 204 is c34·204+71 7007 515 (mod 541).
The inverse of k1is 341366 (mod 541). The decryption of c= 431 is
m366(431 71) 297 (mod 541).
(b) Given two plaintext/ciphertext pairs, one can solve the two linear con-
gruences
c1k1·m1+k2(mod p) and c2k1·m2+k2(mod p)
for the two unknowns k1and k2.
(c) Eve knows that
324 k1·387 + k2(mod 601) and 381 k1·491 + k2(mod 601)
She subtracts the first equation from the second to get
57 k1·104 (mod 601).
She computes 1041549 (mod 601), and hence
k157 ·104141 (mod 601).
Then she uses either of the above congruences to recover k2,
k2324 k1·387 83 (mod 601).
Eve now knows Alice and Bob’s private key, so she can encrypt a message,
c3k1·m3+k241 ·173 + 83 565 (mod 601).
(d) Yes. Suppose that we have three plaintext/ciphertext pairs,
(m1, c1),(m2, c2),(m3, c3).
This gives us a system of three congruences
c1k1m1+k2(mod p)
c2k1m2+k2(mod p)
c3k1m3+k2(mod p)
We can write this in suggestive matrix and vector notation at
c1m11
c2m21
c3m31
¡1k1k2¢¡0 0 0¢(mod p).
Using linear algebra modulo p, this implies that the determinant of the matrix
satisfies
32 Exercises for Chapter 1
det
c1m11
c2m21
c3m31
0 (mod p).
Thus three plaintext/ciphertext pairs allows Eve to compute a number,
namely
D= det
c1m11
c2m21
c3m31
that is divisible by the secret prime p. If Eve can factor D, then at worst she
has a few possible values of pto check. So three pairs may be enough to break
the cipher.
More generally, if Eve has ndifferent pairs, she can compute determinant
values D1, . . . , Dn2by using different pairs in the last row of the matrix
(keeping the first two rows the same). This gives her a bunch of numbers that
are divisible by p, and within a short time she will almost certain find that
gcd(D1, . . . , Dn2) is equal to p.
1.42. Consider the Hill cipher defined by (1.11),
ek(m)k1·m+k2(mod p) and dk(c)k1
1·(ck2) (mod p),
where m,c, and k2are column vectors of dimension n, and k1is an n-by-n
matrix.
(a) We use the vector Hill cipher with p= 7 and the key k1= ( 1 3
2 2 )
and k2= ( 5
4).
(i) Encrypt the message m= ( 2
1).
(ii) What is the matrix k1
1used for decryption?
(iii) Decrypt the message c= ( 3
5).
(b) Explain why the Hill cipher is vulnerable to a chosen plaintext attack.
(c) The following plaintext/ciphertext pairs were generated using a Hill ci-
pher with the prime p= 11. Find the keys k1and k2.
m1= ( 5
4), c1= ( 1
8), m2= ( 8
10 ), c2= ( 8
5), m3= ( 7
1), c3= ( 8
7).
(d) Explain how any simple substitution cipher that involves a permutation
of the alphabet can be thought of as a special case of a Hill cipher.
Solution to Exercise 1.42.
(a-i) ek(m) = 5 3 .
(a ii)k1
1=3 6
4 5 .
(a iii)dk(c) = 0 4 .
(b) Each known plaintext/ciphertext pair gives a congruence of the form
ck1·m+k2(mod p). Writing this out gives nlinear equations for the n2+n
unknown entries of k1and k2. Hence n+1 plaintext/ciphertext pairs probably
gives enough equations to solve for the keys k1and k2.
Exercises for Chapter 1 33
(c) We let k1= ( x y
z w ) and k2= ( u
v). Then the congruence c1=k1m1+
k2(mod 11) becomes the matrix equation
µ1
8=µx y
z wµ5
4+µu
v=µ5x+ 4y+u
5z+ 4w+v(mod 11).
So this gives the two congruences
5x+ 4y+u1 (mod 11) and 5z+ 4w+v8 (mod 11).
Similarly, the congruence c2=k1m2+k2(mod 11) gives
8x+ 10y+u8 (mod 11) and 8z+ 10w+v5 (mod 11).
and c3=k1m3+k2(mod 11) gives
7x+y+u8 (mod 11) and 7z+w+v7 (mod 11).
This gives us 6 equations for the 6 unknowns x, y, z, w, u, v. Further, three of
the equations only involve x, y, u and the other three only involve z, w, v, so
it’s really two sets of 3-by-3 equations to solve:
5x+ 4y+u= 1 5z+ 4w+v= 8
8x+ 10y+u= 8 8z+ 10w+v= 5
7x+y+u= 8 7z+w+v= 7.
(All equations are modulo 11.) These are easily solved using basic linear al-
gebra methods, and we find that
(x, y, u) = (3,7,2) and (z, w, v) = (4,3,9).
Hence
k1=µ3 7
4 3and k2=µ2
9.
(d) We work with vectors of dimension 26. Let e1, . . . , e26 be the usual basis
vectors for R26, i.e., eihas a 1 in the ith place and 0’s elsewhere. For the
plaintext, we use e1to represent (a), we use e2to represent (b), and so
on. We view the the simple substitution cipher as a function that takes each
plaintext letter and assigns it to a ciphertext letter. Equivalently, it takes
each eiand assigns it to some eπ(i), where πis a one-to-one function
π:{1,2,...,26} −→ {1,2, . . . , 26}.
In the Hill cipher, we now take k1to be the matrix whose ijth entry is 1 if
e(i) = j, and otherwise it is 0. We also take k2= 0. Then k1·ei=eπ(i), so
the encryption of the plaintext eiis equal to eπ(i), as desired.
34 Exercises for Chapter 1
1.43. Let Nbe a large integer and let K=M=C=Z/NZ. For each of the
functions
e:K × M C
listed in (a), (b), and (c), answer the following questions:
Is ean encryption function?
If eis an encryption function, what is its associated decryption function d?
If eis not an encryption function, can you make it into an encryption
function by using some smaller, yet reasonably large, set of keys?
(a) ek(m)km(mod N).
(b) ek(m)k·m(mod N).
(c) ek(m)(k+m)2(mod N).
Solution to Exercise 1.43.
(a) Yes, eis an encryption function. The decryption function dk(c) = kc
is the same as e!
(b) No, eis not an encryption function, it is not one-to-one. However, if we
restrict the keys to K= (Z/NZ)(i.e., gcd(k, N ) = 1), then eis an encryption
function, with decryption function dk(c)k1c(mod N).
(c) No, eis not an encryption function, it is not one-to-one, and no sub-
set of keys will make it one-to-one. However, one might define a decryption
“function” by dk(c)ck(mod N). Assuming that one knows how to
compute square roots modulo N, this gives two possibly decryptions, since
it’s really ±c. In practice, one might be able to use some property of valid
messages to figure out which one is correct.
1.44. (a) Convert the 12 bit binary number 110101100101 into a decimal
integer between 0 and 212 1.
(b) Convert the decimal integer m= 37853 into a binary number.
(c) Convert the decimal integer m= 9487428 into a binary number.
(d) Use exclusive or (XOR) to “add” the bit strings 11001010 10011010.
(e) Convert the decimal numbers 8734 and 5177 into binary numbers, com-
bine them using XOR, and convert the result back into a decimal number.
Solution to Exercise 1.44.
(a) 211 + 210 + 28+ 26+ 25+ 22+ 20= 3429
(b) 37853 = 215 + 212 + 29+ 28+ 27+ 26+ 24+ 23+ 22+ 20, so the binary
form of 37853 is 1001001111011101 .
(c) 9487428 = 223 + 220 + 215 + 214 + 210 + 26+ 22, so the binary form
of 9487428 is 100100001100010001000100 .
(d) 11001010 10011010 = 01010000 .
(e)
Exercises for Chapter 1 35
8734 = ‘10001000011110’,
5177 = ‘01010000111001’,
8734 5177 = 10001000011110 01010000111001 = 11011000100111,
‘11011000100111’ = 13863 .
1.45. Alice and Bob choose a key space Kcontaining 256 keys. Eve builds a
special-purpose computer that can check 10,000,000,000 keys per second.
(a) How many days does it take Eve to check half of the keys in K?
(b) Alice and Bob replace their key space with a larger set containing 2Bdif-
ferent keys. How large should Alice and Bob choose Bin order to force
Eve’s computer to spend 100 years checking half the keys? (Use the ap-
proximation that there are 365.25 days in a year.)
For many years the United States government recommended a symmetric
cipher called DES that used 56 bit keys. During the 1990s, people built special
purpose computers demonstrating that 56 bits provided insufficient security.
A new symmetric cipher called AES, with 128 bit keys, was developed to
replace DES. See Section 8.10 for further information about DES and AES.
Solution to Exercise 1.45.
(a)
(256 keys) ·µ1 second
10,000,000,000 keys·µ1 minute
60 seconds
·µ1 hour
60 minutes·µ1 day
24 hours83.4 days.
It thus takes about 83.4 days to check all the keys, so about 41.7 days to
check half the keys.
(b)
µ10,000,000,000 keys
1 second ·µ60 seconds
1 minute ·µ60 minutes
1 hour
·µ24 hours
1 day ·µ365.25 days
1 year ·(100 years)
= 31557600000000000000 keys 264.775 keys.
Thus it takes Eve’s computer 100 years to check 264.775 keys. The problem says
that this should be half the keys, so Alice and Bob should have at least 265.775
different keys. In practice, it is easiest to choose an integral power of 2, so Alice
and Bob’s key space should contain (at least) 266 keys.
Comparing (a) and (b), notice that by increasing the keylength from 56 bits
to 66 bits, Alice and Bob’s security goes from 42 days to 100 years. Thus even a
36 Exercises for Chapter 1
small increase in the keylength results in an enormous increase in the breaking
time by exhaustive search. This reflects the fact that exponential functions
grow extremely rapidly.
1.46. Explain why the cipher
ek(m) = kmand dk(c) = kc
defined by XOR of bit strings is not secure against a chosen plaintext attack.
Demonstrate your attack by finding the private key used to encrypt the 16-bit
ciphertext c= 1001010001010111 if you know that the corresponding plaintext
is m= 0010010000101100.
Solution to Exercise 1.46.
If you know mand c, since they are related by c=km, it follows that
cm=kmm=k. For the example,
k=cm= 1001010001010111 0010010000101100 = 1011000001111011 .
1.47. Alice and Bob create a symmetric cipher as follows. Their private key k
is a large integer and their messages (plaintexts) are d-digit integers
M={mZ: 0 m < 10d}.
To encrypt a message, Alice computes kto ddecimal places, throws away
the part to the left of the decimal point, and keeps the remaining ddigits.
Let αbe this d-digit number. (For example, if k= 23 and d= 6, then
87 = 9.32737905 . . . and α= 327379.)
Alice encrypts a message mas
cm+α(mod 10d).
Since Bob knows k, he can also find α, and then he decrypts cby comput-
ing mcα(mod 10d).
(a) Alice and Bob choose the secret key k= 11 and use it to encrypt 6-digit
integers (i.e., d= 6). Bob wants to send Alice the message m= 328973.
What is the ciphertext that he sends?
(b) Alice and Bob use the secret key k= 23 and use it to encrypt 8-digit
integers. Alice receives the ciphertext c= 78183903. What is the plain-
text m?
(c) Show that the number αused for encryption and decryption is given by
the formula
α=j10d³k− bkc´k,
where btcdenotes the greatest integer that is less than or equal to t.
Exercises for Chapter 1 37
(d) (Challenge Problem) If Eve steals a plaintext/ciphertext pair (m, c), then
it is clear that she can recover the number α, since αcm(mod 10d).
If 10dis large compared to k, can she also recover the number k? This
might be useful, for example, if Alice and Bob use some of the other digits
of kto encrypt subsequent messages.
Solution to Exercise 1.47.
(a) 11 = 3.3166247903 ..., so α= 316624 and the ciphertext is c=
328973 + 316624 = 645597 .
(b) 23 = 4.7958315233127195 . . . , so α= 79583152 and the plaintext is
c= 78183903 79583152 = 1399249 98600751 (mod 108).
(c) The quantity x− bxcgives the fractional part of x, i.e., the part to the
right of the decimal point. The remaining part of the formula simply shifts
the digits dplaces to the left and then discards everything after the decimal
point.
(d) The answer is yes, Eve should be able to recover k, but probably not
using the tools that we’ve developed so far. Let β=α/10d. Then
k=L+βfor some LZ.
There are two unknowns here, kand L, and all that Eve knows is that they
are both integers. Squaring both sides gives
k=L2+ 2+β2.
Thus there are integers Aand Bsatisfying
β2++B= 0,
namely A= 2Land B=L2k. Of course, Eve doesn’t know Aor B, either.
However, there are algorithms based on lattice reduction that are very good at
finding the smallest (quadratic) polynomial with integer coefficients satisfied
by a given decimal number. Using these algorithms, Eve should be able to
find Aand B, from which it is easy to recover kas k=1
4A2B.
1.48. Bob and Alice use a cryptosystem in which their private key is a (large)
prime kand their plaintexts and ciphertexts are integers. Bob encrypts a
message mby computing the product c=km. Eve intercepts the following
two ciphertexts:
c1= 12849217045006222, c2= 6485880443666222.
Use the gcd method described in Section 1.7.4 to find Bob and Alice’s private
key.
Solution to Exercise 1.48.
We compute
gcd(c1, c2) = 174385766.
This factors as 174385766 = 2 ·87192883 and 87192883 is prime, so it is Bob
and Alice’s key.
Chapter 2
Discrete Logarithms and
Diffie–Hellman
Exercises for Chapter 2
Section. Diffie–Hellman and RSA
2.1. Write a one page essay giving arguments, both pro and con, for the
following assertion:
If the government is able to convince a court that there is a valid
reason for their request, then they should have access to an in-
dividual’s private keys (even without the individual’s knowledge),
in the same way that the government is allowed to conduct court
authorized secret wiretaps in cases of suspected criminal activity
or threats to national security.
Based on your arguments, would you support or oppose the government be-
ing given this power? How about without court oversight? The idea that all
private keys should be stored at a secure central location and be accessible to
government agencies (with or without suitably stringent legal conditions) is
called key escrow.
Solution to Exercise 2.1.
A solution for this exercise will not be provided.
2.2. Research and write a one to two page essay on the classification of cryp-
tographic algorithms as munitions under ITAR (International Traffic in Arms
Regulations). How does that act define “export”? What are the potential
fines and jail terms for those convicted of violating the Arms Export Control
Act? Would teaching non-classified cryptographic algorithms to a college class
that includes non-US citizens be considered a form of export? How has US
government policy changed from the early 1990s to the present?
39
40 Exercises for Chapter 2
Solution to Exercise 2.2.
Some historical material:
Press Release
Law Professor Sues Federal Government Over Computer Privacy Issues
Federal Civil Rights Action Seeks Injunction Against State Department
And National Security Agency
Cleveland Scholar Attacks Prohibition On Discussing Cryptographic Soft-
ware With Foreign Students And Colleagues
For Immediate Release
Cleveland, Wednesday, August 7, 1996
A Case Western Reserve University law professor filed suit today in federal
court, challenging government regulations which restrict his ability to teach
a course in computer law. Peter Junger, a twenty-five year veteran of the
law school faculty, will file a federal civil rights action this afternoon in the
United States District Court in Cleveland. The suit names the Department
of State and the secretive National Security Agency, which administer federal
regulations limiting Professor Junger’s ability to teach.
The case involves the International Traffic in Arms Regulations, or ITAR,
federal regulations which restrict the export of military technology. Under the
ITAR, cryptographic computer software, which encodes text to preserve the
privacy of messages on the Internet, is considered a “munition” and subject to
strict export control. The regulations raise significant First Amendment ques-
tions by defining “export” to include discussing technical information about
non-classified software with foreign nationals, such as students registered for
Professor Junger’s course.
In recent months, the State Department has sent a series of letters threat-
ening possible criminal action to a Florida man who posted a simple crypto-
graphic algorithm to the ”sci.crypt” Usenet Newsgroup, an Internet site pop-
ular with cryptography enthusiasts. These and similar incidents have caused
Professor Junger to limit his discussions of cryptographic material with foreign
colleagues, for fear of violating the ITAR. Penalties for unlicensed disclosure
of cryptographic information are severe: federal law provides ten year prison
terms and One Million Dollar fines for those convicted of violating the Arms
Export Control Act, the legislation under which the ITAR was promulgated.
————————————
Statement by Ambassador David Aaron
US Envoy for Cryptography
RSA Data Security Conference, January 28, 1997
International Views of Key Recovery
These concerns are being heard in Washington. The Administration has
taken the following steps - many based on the direct recommendations of
industry representatives:
First, at the end of last year, jurisdiction for licenses of encryption exports
was transferred from the Department of State to the Department of Com-
merce. Commercial encryption is no longer treated as a munition and thereby
Exercises for Chapter 2 41
subject to various foreign policy embargoes. We hope this will both speed up
and simplify the tasks of obtaining licenses.
Second, and very important, the Administration will license the export of
encryption products, of any algorithm and any key length, if they incorporate
key recovery.
Third, the Administration will also permit the export, over the next two
years, of 56-bit DES and equivalent encryption products without key recovery
provided exporters make commitments to develop key recovery products. I
am pleased to report that already at least 4 vendors have formally filed key
recovery commitments and several more companies are in the initial stages of
dialogue with the Department of Commerce.
And last, a point which is often lost in the debate, domestic use of key
recovery will be voluntary as announced by the Vice President last October.
All Americans will remain free to use any encryption system in the United
States.
———————————
In 1992, the Software Publishers Association and the State Department
reached an agreement which allows the export of programs containing RSA
Data Security’s RC2 and RC4 algorithms, but only when the key size is set
to 40 bits or less. 40 bits is not very secure, and application of a distributed
attack using standard workstations in a good-size lab can break these in at
most a few days. This theory was demonstrated quite visibly in mid-1995
when two independent groups broke 40-bit keys used in the export version of
the Netscape browser.
Section. The discrete logarithm problem
2.3. Let gbe a primitive root for Fp.
(a) Suppose that x=aand x=bare both integer solutions to the congruence
gxh(mod p). Prove that ab(mod p1). Explain why this implies
that the map (2.1) on page 63 is well-defined.
(b) Prove that logg(h1h2) = logg(h1) + logg(h2) for all h1, h2F
p.
(c) Prove that logg(hn) = nlogg(h) for all hF
pand nZ.
Solution to Exercise 2.3.
(a) We are given that gagb(mod p), since they are both congruent
to h. Hence gab1 (mod p). But gis a primitive root, so its order is p1,
which implies that p1 divides ab. Hence ab(mod p1). This means
the logg(h) is well-defined up to adding or subtracting multiples of p1, so
the map (2.1) on page 63 is well-defined.
(b) We have
glogg(h1)+logg(h2)=glogg(h1)·glogg(h2)
h1·h2(mod p)
glogg(h1h2)(mod p).
42 Exercises for Chapter 2
Hence logg(h1) + logg(h2) = logg(h1h2), or more precisely, the are congruent
modulo p1.
(c) We have
gnlogg(h)=³glogg(h)´nhnglogg(hn)(mod p).
Hence nlogg(h) = logg(hn).
2.4. Compute the following discrete logarithms.
(a) log2(13) for the prime 23, i.e., p= 23, g= 2, and you must solve the
congruence 2x13 (mod 23).
(b) log10(22) for the prime p= 47.
(c) log627(608) for the prime p= 941. (Hint. Look in the second column of
Table 2.1 on page 64.)
Solution to Exercise 2.4.
(a) log2(13) = 7 in F23, since 213 = 128 13 (mod 23).
(b) log10(22) = 11 in F47.
(c) The table shows that 62718 608 (mod 941), so log627(608) = 18
in F941.
2.5. Let pbe an odd prime and let gbe a primitive root modulo p. Prove
that ahas a square root modulo pif and only if its discrete logarithm logg(a)
modulo pis even.
Solution to Exercise 2.5.
This solution is taken from the proof of Proposition 3.60.
Let m= logg(a), so a=gm. If m= 2kis even, then gm=g2k= (gk)2is
a square.
On the other hand, let mbe odd, say m= 2k+ 1, and suppose that gm
is a square modulo p, say gmc2(mod p). Fermat’s little theorem (Theo-
rem 1.25) tells us that
cp11 (mod p).
However, cp1(mod p) is also equal to
cp1(c2)p1
2(gm)p1
2(g2k+1)p1
2gk(p1) ·gp1
2(mod p).
Another application of Fermat’s little theorem tells us that
gk(p1) (gp1)k1k1 (mod p),
so we find that
gp1
21 (mod p).
This contradicts the fact that gis a primitive root, which proves that every
odd power of gis not a square modulo p.
Section. Diffie–Hellman key exchange
Exercises for Chapter 2 43
2.6. Alice and Bob agree to use the prime p= 1373 and the base g= 2 for
a Diffie–Hellman key exchange. Alice sends Bob the value A= 974. Bob asks
your assistance, so you tell him to use the secret exponent b= 871. What
value Bshould Bob send to Alice, and what is their secret shared value? Can
you figure out Alice’s secret exponent?
Solution to Exercise 2.6.
Bob sends B=gb= 2871 805 (mod 1373) to Alice. Their shared value
is Ab= 974871 397 (mod 1373). There is no really easy way to determine
Alice’s secret exponent, but with a computer or even a progammable calcu-
lator, it does not take long to compute all of the powers of 2 modulo 1373.
(Using the babystep–giantstep method is even faster, you only need to make
two lists of length approximately 1373 = 37.04 . . . . If you do this, you will
find that 2587 974 (mod 1373), so Alice’s secret exponent is 587.
2.7. Let pbe a prime and let gbe an integer. The Diffie–Hellman Decision
Problem is as follows. Supoose that you are given three numbers A,B, and C,
and suppose that Aand Bare equal to
Aga(mod p) and Bgb(mod p),
but that you do not necessarily know the values of the exponents aand b.
Determine whether Cis equal to gab (mod p). Notice that this is different
from the Diffie–Hellman problem described on page 67. The Diffie–Hellman
problem asks you to actually compute the value of gab.
(a) Prove that an algorithm that solves the Diffie–Hellman problem can be
used to solve the Diffie–Hellman decision problem.
(b) Do you think that the Diffie–Hellman decision problem is hard or easy?
Why?
See Exercise 5.35 for a related example in which the decision problem is easy,
but it is believed that the associated computational problem is hard.
Solution to Exercise 2.7.
(a) This is obvious. If you can compute gab from g,ga, and gb, then you
can simply compare the value of gab with the value of Cand check if they are
equal.
(b) No one currently knows how to solve the Diffie–Hellman decision problem
without solving the Diffie–Hellman computational problem.
Section. The ElGamal public key cryptosystem
2.8. Alice and Bob agree to use the prime p= 1373 and the base g= 2 for
communications using the ElGamal public key cryptosystem.
(a) Alice chooses a= 947 as her private key. What is the value of her public
key A?
(b) Bob chooses b= 716 as his private key, so his public key is
B2716 469 (mod 1373).
44 Exercises for Chapter 2
Alice encrypts the message m= 583 using the ephemeral key k= 877.
What is the ciphertext (c1, c2) that Alice sends to Bob?
(c) Alice decides to choose a new private key a= 299 with associated public
key A2299 34 (mod 1373). Bob encrypts a message using Alice’s
public key and sends her the ciphertext (c1, c2) = (661,1325). Decrypt
the message.
(d) Now Bob chooses a new private key and publishes the associated public
key B= 893. Alice encrypts a message using this public key and sends the
ciphertext (c1, c2) = (693,793) to Bob. Eve intercepts the transmission.
Help Eve by solving the discrete logarithm problem 2b893 (mod 1373)
and using the value of bto decrypt the message.
Solution to Exercise 2.8.
(a) A2947 177 (mod 1373), so Alice’s public key is A= 177 .
(b) c12877 719 (mod 1373) and c2583 ·469877 623 (mod 1373).
Alice sends the ciphertext (c1, c2) = (719,623) to Bob.
(c) (ca
1)1·c2(661299)1·1325 6451·1325 794 ·1325 332
(mod 1373). Thus the plaintext is m=332 . It turns out that the ephemeral
key is k= 566, but Alice does not know this value.
(d) The solution to 2b893 (mod 1373) is b= 219 , which is Bob’s private
key. It is now easy to decrypt,
(ca
1)1·c2(693219)1·793 4311·793 532 ·793 365 (mod 1373).
Thus Alice’s message to Bob is m= 365 . (The ephemeral key was k= 932.)
2.9. Suppose that an oracle offers to solve the Diffie–Hellman problem for
you. (See page 67 for a description of the Diffie–Hellman problem.) Explain
how you can use the oracle to decrypt messages that have been encrypted
using the ElGamal public key cryptosystem.
Solution to Exercise 2.9.
In the ElGamal PKC, you know Alice’s public key Aga(mod p) and
you know the ciphertext consisting of the two quantities c1gk(mod p) and
c2m·Ak(mod p), where kis Bob’s secret ephemeral key. You thus know
the values of gaand gk, so the Diffie–Hellman problem oracle will take those
values and tell you the value of gak (mod p). But gak Ak(mod p), so you
can recover Bob’s plaintext message by computing (gak)1·c2m(mod p).
2.10. The exercise describes a public key cryptosystem that requires Bob and
Alice to exchange several messages. We illustrate the system with an example.
Bob and Alice fix a publicly known prime p= 32611, and all of the other
numbers used are private. Alice takes her message m= 11111, chooses a ran-
dom exponent a= 3589, and sends the number u=ma(mod p) = 15950 to
Bob. Bob chooses a random exponent b= 4037 and sends v=ub(mod p) = 15422
back to Alice. Alice then computes w=v15619 27257 (mod 32611) and
Exercises for Chapter 2 45
sends w= 27257 to Bob. Finally, Bob computes w31883 (mod 32611) and
recovers the value 11111 of Alice’s message.
(a) Explain why this algorithm works. In particular, Alice uses the numbers
a= 3589 and 15619 as exponents. How are they related? Similarly, how
are Bob’s exponents b= 4037 and 31883 related?
(b) Formulate a general version of this cryptosystem, i.e., using variables, and
show that it works in general.
(c) What is the disadvantage of this cryptosystem over ElGamal? (Hint. How
many times must Alice and Bob exchange data?)
(d) Are there any advantages of this cryptosystem over ElGamal? In partic-
ular, can Eve break it if she can solve the discrete logarithm problem?
Can Eve break it if she can solve the Diffie–Hellman problem?
Solution to Exercise 2.10.
(a) Alice’s and Bob’s exponents satisfy
3589 ·15619 1 (mod 32610) and 4037 ·31883 1 (mod 32610)
The reason why the algorithm works is discussed in the answer to (b).
(b) In the general formulation, a public prime pis fixed. Alice choose a plain-
text mmod pand a random exponent asatisfying gcd(a, p 1) = 1. She send
uma(mod p)
to Bob. Bob chooses a random exponent bsatisfying gcd(b, p 1) = 1, com-
putes
vub(mod p),
and send vto Alice. Alice now computes the inverse of amodulo p1, i.e.,
she solves ax 1 (mod p1) for x. Let a0=a1mod p1. Alice computes
wva0(mod p)
and sends it to Bob. Finally, Bob computes the inverse b0=b1(mod p1)
and then wb0mod pis equal to m.
To see that this last assertion is true, we compute
wb0va0b0uba0b0maba0b0(mod p).
We know that
aa01 (mod 1) (mod p1) and bb01 (mod 1) (mod p1),
so the exponent aba0b0is congruent to 1 modulo p1. Then Fermat’s little
theorem tells us that maba0b0m(mod p).
(c) ElGamal only require Alice to send Bob a single message. This new cryp-
tosystem requires Alice to send Bob two messages and for Bob to send a
46 Exercises for Chapter 2
message back to Alice. So this new system is much more interactive and re-
quires a lot more communication than does ElGamal.
(d) The advantage of this new system is that Alice and Bob reveal somewhat
less information than in ElGamal. Of course, if Eve can solve the DLP, then
since she knows u,vand w, she can solve
wvx(mod p)
to recover x=a0, and then she can recover m, because
ua0maa0m(mod p).
However, there does not appear to be an easy way for Eve to break the
system if she knows how to solve the Diffie–Hellman Problem. Thus this new
cryptosystem is potentially more secure than ElGamal, if it turns out that
the DHP is easier to solve than the DLP.
Section. An overview of the theory of groups
2.11. The group S3consists of the following six distinct elements
e, σ, σ2, τ, στ, σ2τ,
where eis the identity element and multiplication is performed using the rules
σ3=e, τ2= 1, τσ =σ2τ.
Compute the following values in the group S3:
(a) τσ2(b) τ(στ ) (c) (στ)(στ ) (d) (στ)(σ2τ).
Is S3a commutative group?
Solution to Exercise 2.11.
(a) τσ2= (τσ)σ= (σ2τ)σ=σ2(τσ) = σ2(σ2τ) = σ4τ= (σ3)στ =στ.
(b) τ(στ) = (τσ)τ= (σ2τ)τ=σ2τ2=σ2.
(c) (στ)(στ ) = σ(τσ)τ=σ(σ2τ)τ=σ3τ2=e.
(d) (στ)(σ2τ) = σ(τσ)στ =σ(σ2τ)στ =σ3(τσ)τ=e(σ2τ)τ=σ2τ2=σ2.
No, S3is not a commutative group. For example τσ =σ2τ, which is different
from στ.
2.12. Let Gbe a group, let d1 be an integer, and define a subset of Gby
G[d] = {gG:gd=e}.
(a) Prove that if gis in G[d], then g1is in G[d].
(b) Suppose that Gis commutative. Prove that if g1and g2are in G[d], then
their product g1 g2is in G[d].
(c) Deduce that if Gis commutative, then G[d] is a group.
(d) Show by an example that if Gis not a commutative group, then G[d]
need not be a group. (Hint. Use Exercise 2.11.)
Exercises for Chapter 2 47
Solution to Exercise 2.12.
(a) For any element hof Gand any positive integer n, we have
(h1)n hn= (h1 h1···  h1)(hh···  h) = e,
since there are ncopies of h1to cancel the ncopies of h. Thus (h1)nis the
inverse of hn, which we can write succintly as (h1)n= (hn)1. We apply this
with h=gand n=dand use the assumption that gd=eto conclude that
(g1)d= (gd)1=e1=e.
Hence g1is in G[d].
(b) We are given that gd
1=eand gd
2=e. We use the commutativity to
compute
(g1g2)d=g1g2g1g2···g1g2=gd
1gd
2=ee =e.
Therefore g1g2G[d].
(c) From (a) and (b), if we start with two elements in G[d], their product
and their inverses are in G[d]. Also clearly eis in G[d]. This gives the first
two axioms, and the third (associativity) is automatic, since it’s true for all
elements in G.
(d) Using the group S3in Exercise 2.11, we have τ2=eand (στ )2=e. (The
first is true from the description of the group, and the second is true form
part (c) of the exercise.) However, (στ)τ=στ 2=σdoes not satisfy σ2=e.
To see why, note that σ3=e, so if also σ2=e, then we would have e=σ3=
(σ2)σ==σ, which is not true.
An alternative solution is to use the group of 2-by-2 matrices with integer
coefficients. The matrix A= ( 0 1
1 0 ) satisfies A2=Iand the matrix B=¡11
01¢
satisfies B2=I, but AB =¡11
01¢actually has order 3, i.e., (AB)3=I.
2.13. Let Gand Hbe groups. A function φ:GHis called a (group)
homomorphism if it satisfies
φ(g1 g2) = φ(g1) φ(g2) for all g1, g2G.
(Note that the product g1 g2uses the group law in the group G, while the
product φ(g1) φ(g2) uses the group law in the group H.)
(a) Let eGbe the identity element of G, let eHbe the identity element of H,
and let gG. Prove that
φ(eG) = eHand φ(g1) = φ(g)1.
(b) Let Gbe a commutative group. Prove that the map φ:GGdefined
by φ(g) = g2is a homomorphism. Give an example of a noncommutative
group for which this map is not a homomorphism.
(c) Same question as (b) for the map φ(g) = g1.
Solution to Exercise 2.13.
A solution for this exercise is not currently available.
48 Exercises for Chapter 2
2.14. Prove that each of the following maps is a group homomorphism.
(a) The map φ:ZZ/NZthat sends aZto amod Nin Z/NZ.
(b) The map φ:RGL2(R) defined by φ(a) = ¡a0
0a1¢.
(c) The discrete logarithm map logg:F
pZ/(p1)Z, where gis a primitive
root modulo p.
Solution to Exercise 2.14.
A solution for this exercise is not currently available.
2.15. (a) Prove that GL2(Fp) is a group.
(b) Show that GL2(Fp) is a noncommutative group for every prime p.
(c) Describe GL2(F2) completely. That is, list its elements and describe the
multiplication table.
(d) How many elements are there in the group GL2(Fp)?
(e) How many elements are there in the group GLn(Fp)?
Solution to Exercise 2.15.
(a) The identity element is the usual matrix ( 1 0
0 1 ). The definition of GL2(Fp)
ensures that every element has an inverse. Finally, the associative law is true
because it’s true in general for matrix multiplication. (But feel free to write
it out explicitly for the product of three 2-by-2 matrices.)
(b) Here’s an example of noncommuting matrices:
µ1 1
0 1µ1 0
1 1=µ2 1
1 1and µ1 0
1 1µ1 1
0 1=µ1 1
1 2.
(If p= 2, then 2 = 0, but they are still different matrices.)
(c) The group GL2(F2) has 6 elements:
e=µ1 0
0 1α=µ1 1
1 0β=µ0 1
1 1
γ=µ0 1
1 0δ=µ1 1
0 1=µ1 0
1 1
They satisfy many relations, for example β=α2and =α2γ. In fact, we can
get all 6 elements as
e, α, α2, γ, αγ, α2γ,
and the group operation is determined by the rules
α3=e, γ2=e, γα =α2γ.
Comparing with Exercise 2.11 we see that GL2(F2) is the same as the group S3
described in that exercise, we’ve just named the generating elements αand γ
instead of σand τ.
(d) Let αbe a matrix in GL2(Fp). The first row can be any vector except for
the 0 vector, so there are p21 possibilities for the first row. The second row
Exercises for Chapter 2 49
can be any vector that is not a scalar multiple of the first row. There are p
possible scalar multiples of the first row, so there are p2ppossibilities for
the second row. Hence
# GL2(Fp)=(p11)(p2p) = (p1)2p(p+ 1).
(e) Using the same reasoning as in (d), there are pn1 allowable first rows,
then pnpallowable second rows, then pnp2allowable third rows (since
we have to disallow all linear combinations of the first two rows), etc. Hence
# GLn(Fp) =
n1
Y
i=0
(pnpi).
Section. How hard is the discrete logarithm problem?
2.16. Verify the following assertions from Example 2.17.
(a) x2+x=O¡x2¢. (d) (ln k)375 =O¡k0.001¢.
(b) 5 + 6x237x5=O¡x5¢. (e) k22k=O¡e2k¢.
(c) k300 =O¡2k¢. (f) N102N=O¡eN¢.
Solution to Exercise 2.16.
A solution for this exercise is not currently available.
Section. A Collision Algorithm for the DLP
2.17. Use Shanks’s babystep–giantstep method to solve the following discrete
logarithm problems. (For (b) and (c), you may want to write a computer
program implementing Shanks’s algorithm.)
(a) 11x= 21 in F71.
(b) 156x= 116 in F593.
(c) 650x= 2213 in F3571.
Solution to Exercise 2.17.
(a) The number 11 has order 70 in F71. Set N=d70 e= 9 and H=
hN= 119= 7. From Table ?? we see that
111= 21 ·74= 11 in F71.
Hence
21 = 111·74= 111·(119)4= 1137 in F71,
so the solution is x=37 .
(b) The number 156 has order 148 in F593. Set N=d148 e= 13 and
H=hN= 15613 = 297. From Table ?? we see that
1567= 116 ·2974= 452 in F593.
50 Exercises for Chapter 2
k hka·Hk
1 11 5
2 50 35
3 53 32
4 15 11
Table 2.1: Solve 11x21 (mod 71) with babystep–giantstep
k hka·Hk
1 156 58
2 23 29
3 30 311
4 529 452
5 97 226
6 307 113
7 452 353
Table 2.2: Solve 156x116 (mod 593) via babystep–giantstep
Hence
116 = 1567·2974= 1567·(15613)4= 15659 in F593,
so the solution is x=59 .
(c) The number h= 650 has order 510 in F3571. Set N=d510 e= 23 and
H=hN= 65023 = 1925. Table ?? lists the values of hkand a·Hkfor
k= 1,2, . . .. From the table we see that
65020 = 2213 ·192513 = 3011 in F3571.
Using the fact that 1925 = 65023, we compute
2213 = 65020 ·192513 = 65020 ·(65023)13 = 650319 in F3571,
so the solution is x=319 .
Section. The Chinese remainder theorem
2.18. Solve each of the following simultaneous systems of congruences (or
explain why no solution exists).
k hka·Hk
1 650 3393
2 1122 166
3 816 1731
4 1892 432
5 1376 3128
k hka·Hk
6 1650 694
7 1200 396
8 1522 1677
9 133 41
10 746 363
k hka·Hk
11 2815 2430
12 1398 3311
13 1666 3011
14 887 442
15 1619 952
k hka·Hk
16 2476 677
17 2450 3381
18 3405 2063
19 2801 323
20 3011 421
Table 2.3: Solve 650x2213 (mod 3571) using babystep–giantstep
Exercises for Chapter 2 51
(a) x3 (mod 7) and x4 (mod 9).
(b) x137 (mod 423) and x87 (mod 191).
(c) x133 (mod 451) and x237 (mod 697).
(d) x5 (mod 9), x 6 (mod 10),and x7 (mod 11).
(e) x37 (mod 43), x 22 (mod 49),and x18 (mod 71).
Solution to Exercise 2.18.
(a) x31 (mod 63).
(b) x27209 (mod 80793).
(c) No solution, since gcd(451,697) = 41 and 133 and 237 are not congru-
ent to one another modulo 41.
(d) x986 (mod 990).
(e) x11733 (mod 149597).
2.19. Solve the 1700-year-old Chinese remainder problem from the Sun Tzu
Suan Ching stated on page 82.
Solution to Exercise 2.19.
In the modern notation, the solution in the Sun Tzu Suan Ching uses the
fact that:
70 1 (mod 3) 0 (mod 5) 0 (mod 7),
21 0 (mod 3) 1 (mod 5) 0 (mod 7),
15 0 (mod 3) 0 (mod 5) 1 (mod 7).
Hence (2 70) + (3 21) + (2 15) = 233 satisfies the desired congruences.
Since any multiple of 105 is divisible by 3, 5 and 7, we can subtract 2 105
from 233 to get 23 as the smallest positive solution.
Problem 26 is the only problem in the Sun Tzu Suan Ching that illus-
trates the Chinese remainder theorem. Thus it is not known if the author had
developed a general method to solve such problems.
2.20. Let a, b, m, n be integers with gcd(m, n) = 1. Let
c(ba)·m1(mod n).
Prove that x=a+cn is a solution to
xa(mod m) and xb(mod n),(2.1)
and that every solution to (2.24) has the form x=a+cn+ymn for some yZ.
Solution to Exercise 2.20.
A solution for this exercise is not currently available.
2.21. Let x=cand x=c0be two solutions of the system of simultaneous
congruences (2.7) in the Chinese remainder theorem (Theorem 2.25). Prove
that
cc0(mod m1m2···mk).
52 Exercises for Chapter 2
Solution to Exercise 2.21.
A solution for this exercise is not currently available.
2.22. For those who have studied ring theory, this exercise sketches a short, al-
beit nonconstructive, proof of the Chinese remainder theorem. Let m1, . . . , mk
be integers and let m=m1m2···mkbe their product.
(a) Prove that the map
Z
mZZ
m1Z×Z
m2Z×Z
mkZ
amod m(amod m1, a mod m2, . . . , a mod mk)
(2.2)
is a well-defined homomorphism of rings. (Hint. First define a homomor-
phism from Zto the right-hand side of (2.25), and then show that mZis
in the kernel.)
(b) Assume that m1, . . . , mkare pairwise relatively prime. Prove that the
map given by (2.25) is one-to-one. (Hint. What is the kernel?)
(c) Continuing with the assumption that the numbers m1, . . . , mkare pair-
wise relatively prime, prove that the map (2.25) is onto. (Hint. Use (b)
and count the size of both sides.)
(d) Explain why the Chinese remainder theorem (Theorem 2.25) is equivalent
to the assertion that (b) and (c) are true.
Solution to Exercise 2.22.
A solution for this exercise is not currently available.
2.23. Use the method described in Section 2.8.1 to find square roots modulo
the following composite moduli.
(a) Find a square root of 340 modulo 437. (Note that 437 = 19 ·23.)
(b) Find a square root of 253 modulo 3143.
(c) Find four square roots of 2833 modulo 4189. (The modulus factors as
4189 = 59 ·71. Note that your four square roots should be distinct mod-
ulo 4189.)
(d) Find eight square roots of 813 modulo 868.
Solution to Exercise 2.23.
(a) The square roots of 340 modulo 437 are 146, 215, 222, and 291.
(b) The square roots of 253 modulo 3143 are 489, 1387, 1756, 2654. (Note
3143 = 7 ·449 and 449 is prime.)
(c) The square roots of 2833 modulo 4189 are 1002, 1712, 2477, and 3187.
(d) We factor 868 = 4 ·7·31. The eight square roots of 813 modulo 868 are
41, 83, 351, 393, 475, 517, 785, and 827.
2.24. Let pbe an odd prime and let bbe a square root of amodulo p. This
exercise investigates the square root of amodulo powers of p.
(a) Prove that for some choice of k, the number b+kp is a square root of a
modulo p2, i.e., (b+kp)2a(mod p2).
Exercises for Chapter 2 53
(b) The number b= 537 is a square root of a= 476 modulo the prime
p= 1291. Use the idea in (a) to compute a square root of 476 modulo p2.
(c) Suppose that bis a square root of amodulo pn. Prove that for some choice
of j, the number b+jpnis a square root of amodulo pn+1.
(d) Explain why (c) implies the following statement: If pis an odd prime and
if ahas a square root modulo p, then ahas a square root modulo pnfor
every power of p. Is this true if p= 2?
(e) Use the method in (c) to compute the square root of 3 modulo 133, given
that 923 (mod 13).
Solution to Exercise 2.24.
(a),(c),(d) A solution for this exercise is not currently available.
(b) (b+k·p)2a(mod p2) gives 1074k+ 223 0 (mod p), and hence
k239 (mod p). This gives 309086 as the square root of amodulo p2.
(e) 9863 is the square root of 3 modulo 133.
2.25. Suppose n=pq with pand qboth primes.
(a) Suppose that gcd(a, pq) = 1. Prove that if the equation x2a(mod n)
has any solutions, then it has four solutions.
(b) Suppose you had a machine that could find all four solutions for some
given a. How could you use this machine to factor n?
Solution to Exercise 2.25.
A solution for this exercise is not currently available.
Section. The Pohlig–Hellman algorithm
2.26. Let Fpbe a finite field and let N|p1. Prove that F
phas an element
of order N. This is true in particular for any prime power that divides p1.
(Hint. Use the fact that F
phas a primitive root.)
Solution to Exercise 2.26.
Let gbe a primitive root. Then ghas order p1, so h=g(p1)/N has
order N.
2.27. Write out your own proof that the Pohlig–Hellman algorithm works in
the particular case that p1 = q1·q2is a product of two distinct primes.
This provides a good opportunity for you to understand how the proof works
and to get a feel for how it was discovered.
Solution to Exercise 2.27.
A solution for this exercise will not be provided.
2.28. Use the Pohlig–Hellman algorithm (Theorem 2.32) to solve the discrete
logarithm problem
gx=ain Fp
in each of the following cases.
(a) p= 433, g= 7, a= 166.
54 Exercises for Chapter 2
(b) p= 746497, g= 10, a= 243278.
(c) p= 41022299, g= 2, a= 39183497. (Hint.p= 2 ·295+ 1.)
(d) p= 1291799, g= 17, a= 192988. (Hint.p1 has a factor of 709.)
Solution to Exercise 2.28.
(a) Step 1 is to solve
q e h =g(p1)/qeb=a(p1)/qeywith hy=b
2 4 265 250 15
3 3 374 335 20
Step 2 is to solve
x15 (mod 24), x 20 (mod 33).
The solution is x=47 .
(b) Step 1 is to solve
q e h =g(p1)/qeb=a(p1)/qeywith hy=b
2 10 4168 38277 523
3 6 674719 322735 681
Step 2 is to solve
x523 (mod 210), x 681 (mod 36).
The solution is x=223755 .
(c) Step 1 is to solve
q e h =g(p1)/qeb=a(p1)/qeywith hy=b
2 1 41022298 1 0
29 5 4 11844727 13192165
In order to solve the discrete logarithm problem modulo 295, it is best to solve
it step by step. Note that 4294= 18794375 is an element of order 29 in F
p. To
avoid notational confusion, we use the letter ufor the exponents.
First solve 18794375u0=¡11844727¢294
= 987085. The solution is u0= 7.
The value of uso far is u= 7.
Solve 18794375u1=¡11844727·47¢293
= 8303208. The solution is u1= 8.
The value of uso far is u= 239 = 7 + 8 ·29.
Solve 18794375u2=¡11844727 ·4239¢292
= 30789520. The solution is
u2= 26. The value of uso far is u= 22105 = 7 + 8 ·29 + 26 ·292.
Solve 18794375u3=¡11844727 ·422105¢291
= 585477. The solution is
u3= 18. The value of uso far is u= 461107 = 7 + 8 ·29 + 26 ·292+ 18 ·293.
Solve 18794375u4=¡11844727 ·4461107¢290
= 585477. The solution is
u4= 18. The final value of uis u= 13192165 = 7 + 8 ·29 + 26 ·292+ 18 ·293+
18 ·294, which is the number you see in the last column of the table.
Exercises for Chapter 2 55
Step 2 is to solve
x0 (mod 2), x 13192165 (mod 295).
The solution is x=33703314 .
(d) Step 1 is to solve
q e h =g(p1)/qeb=a(p1)/qeywith hy=b
2 1 1291798 1 0
709 1 679773 566657 322
911 1 329472 898549 534
There is no magical way to solve the DLP’s modulo 709 or 911, although
they are easily solved by an exhaustive search on a computer, and a collision
algorithm is even faster. Step 2 is to solve
x0 (mod 2), x 322 (mod 709), x 534 (mod 911).
The solution is x=984414 .
Section. Rings, quotient rings, polynomial rings, and finite fields
2.29. Let Rbe a ring with the property that the only way that a product a·b
can be 0 is if a= 0 or b= 0. (In the terminology of Example 2.56, the ring R
has no zero divisors.) Suppose further that Rhas only finitely many elements.
Prove that Ris a field. (Hint. Let aRwith a6= 0. What can you say about
the map RRdefined by b7→ a·b?)
Solution to Exercise 2.29.
A solution for this exercise is not currently available.
2.30. Let Rbe a ring. Prove the following properties of Rdirectly from the
ring axioms described in Section 2.10.1.
(a) Prove that the additive identity element 0 Ris unique, i.e., prove that
there is only one element in Rsatisfying 0+a=a+0 = 0 for every aR.
(b) Prove that the multiplicative identity element 1 Ris unique.
(c) Prove that every element of Rhas a unique additive inverse.
(d) Prove that 0  a =a  0 = 0 for all aR.
(e) We denote the additive inverse of aby a. Prove that (a) = a.
(f) Let 1 be the additive inverse of the multiplicative identity element 1
R. Prove that (1) (1) = 1.
(g) Prove that b|0 for every nonzero bR.
(h) Prove that an element of Rhas at most one multiplicative inverse.
Solution to Exercise 2.30.
(a) If 0 and 00are both additive identities, then
00= 00+ 0 = 0.
56 Exercises for Chapter 2
(b) If 1 and 10are both multiplicative identities, then
10= 101 = 1.
(c) If band care both additive inverses of a, then
b=b+ 0 = b+ (c+b0) = (b+c) + b0= 0 + b0=b0.
(d)
0 a = (0 + 0)  a = (0  a) + (0  a).
Subtracting 0  a from both sides give 0  a = 0. (Note “subtraction” really
means to add the additive inverse.)
(e) Let b=(a). Then by definition, b+ (a) = 0. But we also know by
definition that a+ (a) = 0. Since additive inverses are unique from (c), it
follows that b=a.
(f) To ease notation, we let i= 1 and u=1. Then
0 = 0  u = (i+u) u = (iu)+(uu) = u+ (uu).
Thus uu is the additive inverse of u. Using (e) gives (1)(1) = (1) = 1.
(g) We have b  0 = 0 from (d), so b|0 by definition of divisibility.
(h) Let aRand suppose that ab = 1 and ac = 1, so band care both
multiplicative inverses of a. Then
b=b·1 = b·(a·c) = (a·b)·c= 1 ·c=c.
Thus b=c, so ahas at most one multiplicative inverse.
2.31. Prove Proposition 2.42.
Solution to Exercise 2.31.
A solution for this exercise is not currently available.
2.32. Prove Proposition 2.44. (Hint. First use Exercise 2.31 to prove that the
congruence classes a+band abdepend only on the congruence classes of a
and b.)
Solution to Exercise 2.32.
A solution for this exercise is not currently available.
2.33. Let Fbe a field and let aand bbe nonzero polynomials in F[x].
(a) Prove that deg(a·b) = deg(a) + deg(b).
(b) Prove that ahas a multiplicative inverse in F[x] if and only if ais in F,
i.e., if and only if ais a constant polynomial.
(c) Prove that every nonzero element of F[x] can be factored into a product of
irreducible polynomials. (Hint. Use (a), (b), and induction on the degree
of the polynomial.)
Exercises for Chapter 2 57
(d) Let Rbe the ring Z/6Z. Give an example to show that (a) is false for
some polynomials aand bin R[x].
Solution to Exercise 2.33.
(a) A solution for this exercise is not currently available.
(b) If a·b= 1, then taking degrees and using (a) gives
0 = deg(1) = deg(a·b) = deg(a) + deg(b).
The degree of a nonzero polynomial is a nonnegative integer, so we conclude
that deg(a) = deg(b) = 0. Hence aand bare constant polynomials.
(c) Polynomials of degree 0 and 1 are already irreducible. Suppose we know
that every polynomial of degree smaller than ncan be factored into a product
of irreducible polynomials, and let aF[x] have degree n. If ais itself irre-
ducible, we’re done. Otherwise it factors as a=b·c, where neither bnor c
is a unit. It follows from (b) that band cboth have degree at least 1, so
using (a) we find that band chave degrees that are strictly smaller than the
degree of a. Hence by induction, both band ccan be factored as a product
of irreducible polynomials. But then their product, which equals a, is also a
product of irreducible polynomials.
(d) Let a= 2x+ 1 and bfb = 3x+ 1, then a·b= 6x2+ 5x+ 1 = 5x+ 1,
since 6 = 0 in Z/6Z. Hence
deg(a) = deg(b) = deg(a·b) = 1,
so the degree formula in (a) is false.
2.34. Let aand bbe the polynomials
a=x5+ 3x45x33x2+ 2x+ 2,
b=x5+x42x3+ 4x2+x+ 5.
Use the Euclidean algorithm to compute gcd(a,b) in each of the following
rings.
(a) F2[x] (b) F3[x] (c) F5[x] (d) F7[x].
Solution to Exercise 2.34.
(a) gcdF2[x](a,b) = x3+x2+x+ 1.
(b) gcdF3[x](a,b) = x2+x+ 2.
(c) gcdF5[x](a,b) = x+ 4.
(d) gcdF7[x](a,b) = 1.
(Note for instructor: The resultant of aand bis 23·32·5·59 ·107, so
gcd(a,b) = 1 in Fp[x] unless p∈ {2,3,5,59,107}.)
2.35. Continuing with the same polynomials aand bas in Exercise 2.34,
for each of the polynomial rings (a), (b), (c), and (d) in Exercise 2.34, find
polynomials uand vsatisfying
a·u+b·v= gcd(a,b).
58 Exercises for Chapter 2
Solution to Exercise 2.35.
(a) u= 1 and v= 1.
(b) u=x+ 1 and v= 2x.
(c) u= 3x3+ 4x2+x+ 2 and v= 2x3+x.
(d) u= 3x4+ 3x3+x2+ 5x+ 4 and v= 4x4+ 5x3+x2+ 2x.
2.36. Prove that the polynomial x3+x+ 1 is irreducible in F2[x]. (Hint.
Think about what a factorization would have to look like.)
Solution to Exercise 2.36.
If x3+x+ 1 factors, then it can be written as the product of a linear
polynomial and a quadratic polynomial. Since the only possible coefficients
are 0 and 1, this means we would have
x3+x+ 1 = (x+a)(x2+bx +c) in F2[x].
Putting x= 0 yields 1 = ac, so we must have a=c= 1. (Remember that a
and care in F2, so they are either 0 or 1.) Now we have
x3+x+ 1 = (x+ 1)(x2+bx + 1),
and putting x= 1 yields 1 = 2 ·(2 + b) = 0. This contradiction shows
that x3+x+ 1 does not factor in F2[x].
2.37. The multiplication table for the field F2[x]/(x3+x+ 1) is given in
Table 2.5, but we have omitted fourteen entries. Fill in the missing entries.
(This is the field described in Example 2.58. You can download and print
a copy of Table 2.5 at www.math.brown.edu/~jhs/MathCrypto/Table2.5.
pdf.)
Solution to Exercise 2.37.
Note that it’s not necessary to compute both a·band b·a. Half missing
entries in the table are
1·x2=x2
x·(x2+x) = x2+x+ 1
x2·x=x+ 1
(x+ 1) ·1 = x+ 1
(x2+ 1) ·(x+ 1) = x2
(x2+x)·(x2+x+ 1) = x2
(x2+x+ 1) ·(x2+ 1) = x2+x.
The other half are the same products in the opposite order.
Exercises for Chapter 2 59
0 1 x x21 + x1 + x2x+x21 + x+x2
0 0 0 0 0 0 0 0 0
1 0 1 x1 + x2x+x21 + x+x2
x0x x2x+x21 1 + x2
x20x+x21 + x+x2x1 + x21
1 + x0x+x21 + x+x21 + x21x
1 + x20 1 + x21x1 + x+x21 + x
x+x20x+x21 + x21 1 + x x
1 + x+x20 1 + x+x21 + x21x1 + x
Table 2.4: Multiplication table for the field F2[x]/(x3+x+ 1)
2.38. The field F7[x]/(x2+ 1) is a field with 49 elements, which for the mo-
ment we denote by F49. (See Example 2.59 for a convenient way to work
with F49.)
(a) Is 2 + 5xa primitive root in F49?
(b) Is 2 + xa primitive root in F49?
(c) Is 1 + xa primitive root in F49?
(Hint. Lagrange’s theorem says that the order of uF49 must divide 48. So
if uk6= 1 for all proper divisors kof 48, then uis a primitive root.)
Solution to Exercise 2.38.
(a) No, (2 + x)8= 1.
(b) Yes. It suffices to check that (2 + x)16 = 4 and (2+x)24 = 6 are not equal
to 1.
(c) No, (1 + x)24 = 1.
2.39. Let pbe a prime number and let e2. The quotient ring Z/peZand
the finite field Fpeare both rings and both have the same number of elements.
Describe some ways in which they are intrinsically different.
Solution to Exercise 2.39.
Every nonzero element in the field Fpehas a multiplicative inverse,
while Z/(pe) has lots of elements that do not have inverses, for example all el-
ements of the form kp with 1 k < pe1. In the field Fpe, if a product ab = 0,
then either a= 0 or b= 0. (To see this, note that if a6= 0, then a1exists, so
multiplying ab = 0 by a1shows that b= 0.) On the other hand, Z/(pe) does
not have this property. For example, p·pe1= 0, but neither pnor pe1is 0
in Z/(pe). A subtler property is that every element αof Fpesatisfies αpe=α,
but this is not true in Z/(pe). For example, if we take α=p, the αpe= 0.
2.40. Let Fbe a finite field.
(a) Prove that there is an integer m1 such that if we add 1 to itself m
times,
1+1+··· + 1
| {z }
mones
,
60 Exercises for Chapter 2
then we get 0. Note that here 1 and 0 are the multiplicative and additive
identity elements of the field F. If the notation is confusing, you can let u
and zbe the multiplicative and additive identity elements of F, and then
you need to prove that u+u+···+u=z. (Hint. Since Fis finite, the
numbers 1, 1 + 1, 1 + 1 + 1,. . . cannot all be different.)
(b) Let mbe the smallest positive integer with the property described in (a).
Prove that mis prime. (Hint. If mfactors, show that there are nonzero
elements in Fwhose product is zero, so Fcannot be a field.) This prime
is called the characteristic of the field F.
(c) Let pbe the characteristic of F. Prove that Fis a finite-dimensional vector
space over the field Fpof pelements.
(d) Use (c) to deduce that Fhas pdelements for some d1.
Solution to Exercise 2.40.
(a) The fact that Fis finite means that when we look at
1,1 + 1,1 + 1 + 1,1+1+1+1, . . .
eventually we get a repeated value. Subtracting the smaller number of terms
from the larger, it follows that some sum of 1’s is equal to 0 in F.
(b) Suppose that mfactors as m=qr. Then we have
1+1+··· + 1
| {z }
qones ·1 + 1 + ··· + 1
| {z }
rones
= 1 + 1 + ··· + 1
| {z }
mones
= 0.
Since Fis a field, the only way for a product to be 0 is for one of the factors
to be 0, so we have either
1+1+··· + 1
| {z }
qones
= 0 or 1 + 1 + ··· + 1
| {z }
rones
= 0 in F.
But we defined mto be the smallest number of 1’s that sums to 0, so either q
mor rm. Since we also have m=qr, it follows that either q=m(and
r= 1) or r=m(and q= 1). This proves that mis prime.
(c) It follows that we have a copy of Fpinside Fby sending 1 to 1 and
1 + 1 to 1 + 1, etc. The axioms for a field show that this makes Finto a
vector space using Fpas scalars. By standard linear algebra, Fhas a basis as
a vector space over Fp, and the basis is finite since Fitself is finite. Hence F
is a finite-dimensional vector space over Fp.
(d) Let v1,...,vdbe a basis for Fas a vector space over Fp. Then every
element of Fcan be written uniquely as
a1v1+a2v2+··· +advdwith a1, . . . , adFp.
There are pchoices of a1, and pchoices of a2, and pchoices of a3, etc. So
there are pddistinct elements in F.
Chapter 3
Integer Factorization and
RSA
Exercises for Chapter 3
Section. Euler’s theorem and roots modulo pq
3.1. Solve the following congruences.
(a) x19 36 (mod 97).
(b) x137 428 (mod 541).
(c) x73 614 (mod 1159).
(d) x751 677 (mod 8023).
(e) x38993 328047 (mod 401227). (Hint. 401227 = 607 ·661.)
Solution to Exercise 3.1.
(a) 97 is prime. The congruence 19d1 (mod 96) has solution d91
(mod 96). Then x3691 36 (mod 97).
(b) 541 is prime. The congruence 137d1 (mod 540) has solution d473
(mod 540). Then x428473 213 (mod 541).
(c) 1159 = 19 ·61 and 18 ·60 = 1080. The congruence 73d1 (mod 1080)
has solution d577 (mod 1080). Then x614577 158 (mod 1159).
More efficiently, g= gcd(18,60) = 6 and (18)(60)/6 = 180. The congruence
73d1 (mod 180) has solution d37 (mod 180). Then x61437 158
(mod 1159).
(d) 8023 = 71 ·113 and 71 ·112 = 7840. The congruence 751d1
(mod 7840) has solution d7151 (mod 7840). Then x6777151 1355
(mod 8023). More efficiently, g= gcd(70,112) = 14 and (70)(112)/14 = 560.
The congruence 751d1 (mod 560) has solution d431 (mod 560). Then
x677431 1355 (mod 8023).
(e) 401227 = 607 ·661 and 608 ·660 = 399960. The congruence 38993d
1 (mod 399960) has the solution d265457 (mod 399960). Then x
61
62 Exercises for Chapter 3
328047265457 36219 (mod 401227). More efficiently, g= gcd(606,660) = 6
and (606)(660)/6 = 66660. The congruence 38993d1 (mod 66660) has
the solution d65477 (mod 66660). Then x32804765477 36219
(mod 401227).
3.2. Let pand qbe distinct primes and let eand dbe integers satisfying
de 1 (mod (p1)(q1)).
Suppose further that cis an integer with gcd(c, pq)>1. Prove that
xcd(mod pq) is a solution to the congruence xec(mod pq),
thereby completing the proof of Proposition 3.4.
Solution to Exercise 3.2.
If pq |c, then the solution is x= 0. So the interesting case is when cis
divisible by exactly one of pand q, say p|cand q-c. Then xcd0 (mod p)
is a solution to xec0 (mod p), so we only need to check that it is true
modulo q. We compute
(cd)ec1+k(p1)(q1) c·(cq1)k(p1) c(mod q),
since cq11 (mod q) from Fermat’s little theorem.
3.3. Recall from Section 1.3 that Euler’s phi function φ(N) is the function
defined by
φ(N) = #{0k < N : gcd(k, N) = 1}.
In other words, φ(N) is the number of integers between 0 and N1 that are
relatively prime to N, or equivalently, the number of elements in Z/N Zthat
have inverses modulo N.
(a) Compute the values of φ(6), φ(9), φ(15), and φ(17).
(b) If pis prime, what is the value of φ(p)?
(c) Prove Euler’s formula
aφ(N)1 (mod N) for all integers asatisfying gcd(a, N) = 1.
(Hint. Mimic the proof of Fermat’s little theorem (Theorem 1.25), but
instead of looking at all of the multiples of aas was done in (1.8), just
take the multiples ka of afor values of ksatisfying gcd(k, N) = 1.)
Solution to Exercise 3.3.
A solution for this exercise is not currently available.
3.4. Euler’s phi function has many beautiful properties.
(a) If pand qare distinct primes, how is φ(pq) related to φ(p) and φ(q)?
Exercises for Chapter 3 63
(b) If pis prime, what is the value of φ(p2)? How about φ(pj)? Prove that
your formula for φ(pj) is correct. (Hint. Among the numbers between 0
and pj1, remove the ones that have a factor of p. The ones that are
left are relatively prime to p.)
(c) Let Mand Nbe integers satisfying gcd(M, N) = 1. Prove the multipli-
cation formula
φ(MN) = φ(M)φ(N).
(d) Let p1, p2, . . . , prbe the distinct primes that divide N. Use your results
from (b) and (c) to prove the following formula:
φ(N) = N
r
Y
i=1 µ11
pi.
(e) Use the formula in (d) to compute the following values of φ(N).
(i) φ(1728). (ii) φ(1575). (iii) φ(889056) (Hint. 889056 = 25·34·73).
Solution to Exercise 3.4.
(a)–(d) A solution for this exercise is not currently available.
(e) (i) φ(1728) = 576, (ii) φ(1575) = 720, (iii) φ(889056) = 254016.
3.5. Let N,c, and ebe positive integers satisfying the conditions gcd(N, c) = 1
and gcd¡e, φ(N)¢= 1.
(a) Explain how to solve the congruence
xec(mod N),
assuming that you know the value of φ(N). (Hint. Use the formula in
Exercise 3.3(c).)
(b) Solve the following congruences. (The formula in Exercise 3.4(d) may be
helpful for computing the value of φ(N).)
(i) x577 60 (mod 1463).
(ii) x959 1583 (mod 1625).
(iii) x133957 224689 (mod 2134440).
Solution to Exercise 3.5.
(a) A solution for this exercise is not currently available.
(b) (i) N= 7 ·11 ·19, so
φ(1463) = 1463 µ11
7µ11
11µ11
19= 1080.
We compute d577173 (mod 1080), so
x6073 1390 (mod 1463).
64 Exercises for Chapter 3
Check: 1390577 60 (mod 1463). X
(ii) N= 53·13, so
φ(1625) = 1625 µ11
5µ11
13= 1200.
We compute d9591239 (mod 1200), so
x1583239 147 (mod 1625).
Check: 147959 1583 (mod 1625). X
(iii) N= 23·32·5·72·112, so
φ(2134440) = 2134440 µ11
2µ11
3µ11
5µ11
7µ11
11
= 443520.
We compute d1339571326413 (mod 443520), so
x224689326413 1892929 (mod 2134440).
Check: 1892929133957 224689 (mod 2134440). X
Section. The RSA public key cryptosystem
3.6. Alice publishes her RSA public key: modulus N= 2038667 and exponent
e= 103.
(a) Bob wants to send Alice the message m= 892383. What ciphertext does
Bob send to Alice?
(b) Alice knows that her modulus factors into a product of two primes, one
of which is p= 1301. Find a decryption exponent dfor Alice.
(c) Alice receives the ciphertext c= 317730 from Bob. Decrypt the message.
Solution to Exercise 3.6.
(a) Bob sends c=me= 892383103 45293 (mod 2038667).
(b) The modulus is N= 2038667 = 1301 ·1567, so φ(N) = 1300 ·1568 =
2035800. A decryption exponent is given by a solution to
103d1 (mod 2035800).
The solution is d810367 (mod 2035800).
(c) Alice needs to solve
m103 317730 (mod 2038667).
Raising both sides to the dth power, where d= 810367 is her decryption
exponent, yields
m317730810367 514407 (mod 2038667).
Exercises for Chapter 3 65
3.7. Bob’s RSA public key has modulus N= 12191 and exponent e= 37.
Alice sends Bob the ciphertext c= 587. Unfortunately, Bob has chosen too
small a modulus. Help Eve by factoring Nand decrypting Alice’s message.
(Hint.Nhas a factor smaller than 100.)
Solution to Exercise 3.7.
The modulus factors as N= 12191 = 73 ·167, so φ(N) = 72 ·168 = 11952.
The congruence
37d1 (mod 11952)
has solution d11629 (mod 11952). Then
m58711629 4894 (mod 12191)
is a solution to m37 587 (mod 12191).
It is possible to be a bit more efficient, using the fact that g= gcd(72,166) =
2 and (72)(166)/2 = 5976. Thus a solution to the congruence
37d1 (mod 5976)
is a decryption exponent, giving the smaller decryption exponent d5653
(mod 5976). Of course, this gives the same plaintext
m5875653 4894 (mod 12191).
3.8. For each of the given values of N=pq and (p1)(q1), use the method
described in Remark 3.10 to determine pand q.
(a) N=pq = 352717 and (p1)(q1) = 351520.
(b) N=pq = 77083921 and (p1)(q1) = 77066212.
(c) N=pq = 109404161 and (p1)(q1) = 109380612.
(d) N=pq = 172205490419 and (p1)(q1) = 172204660344.
Solution to Exercise 3.8.
(a) Suppose that N=pq = 352717 and (p1)(q1) = 351520. Then
p+q=N+ 1 (p1)(q1) = 1198, so
X2(p+q)X+N=X21198X+ 352717 = (X677)(X521).
Hence N= 352717 = 677 ·521.
(b) Suppose that N=pq = 77083921 and (p1)(q1) = 77066212. Then
p+q=N+ 1 (p1)(q1) = 17710, so
X2(p+q)X+N=X217710X+ 77083921 = (X10007)(X7703).
Hence N= 77083921 = 10007 ·7703.
(c) Suppose that N=pq = 109404161 and (p1)(q1) = 109380612. Then
p+q=N+ 1 (p1)(q1) = 23550, so
66 Exercises for Chapter 3
X2(p+q)X+N=X223550X+ 109404161 = (X6367)(X17183).
Hence N= 109404161 = 6367 ·17183.
(d) Suppose that N=pq = 172205490419 and (p1)(q1) = 172204660344.
Then p+q=N+ 1 (p1)(q1) = 830076, so
X2(p+q)X+N=X2830076X+172205490419 = (X407893)(X422183).
Hence N= 172205490419 = 407893 ·422183.
3.9. Adecryption exponent for an RSA public key (N, e) is an integer dwith
the property that ade a(mod N) for all integers athat are relatively prime
to N.
(a) Suppose that Eve has a magic box that creates decryption exponents
for (N, e) for a fixed modulus Nand for a large number of different
encryption exponents e. Explain how Eve can use her magic box to try
to factor N.
(b) Let N= 38749709. Eve’s magic box tells her that the encryption ex-
ponent e= 10988423 has decryption exponent d= 16784693 and
that the encryption exponent e= 25910155 has decryption exponent
d= 11514115. Use this information to factor N.
(c) Let N= 225022969. Eve’s magic box tells her the following three encryp-
tion/decryption pairs for N:
(70583995,4911157),(173111957,7346999),(180311381,29597249).
Use this information to factor N.
(d) Let N= 1291233941. Eve’s magic box tells her the following three en-
cryption/decryption pairs for N:
(1103927639,76923209),(1022313977,106791263),(387632407,7764043).
Use this information to factor N.
Solution to Exercise 3.9.
Let e1, e2, . . . , enbe a bunch of random encryption exponents, and suppose
that Eve uses her magic box to create decryption exponents d1, d2, . . . , dn.
The numbers Kwith the property that aKa(mod N) for all asatisfying
gcd(a, N) = 1 are numbers satisfying
K1µmod (p1)(q1)
gcd(p1, q 1).
Thus diei1 is a multiple of (p1)(q1)/gcd(p1, q 1) for all 1 in.
Assuming that the ei’s are reasonably random, Eve will find that
T= gcd(d1e11, d2e21, d3e31, . . . , dnen1) (3.1)
Exercises for Chapter 3 67
is equal to a small multiple of
(p1)(q1)
gcd(p1, q 1).
Next Eve uses the fact that gcd(p1, q 1) is even and tends to be fairly
small. So she first assumes that T= (p1)(q1)/2 and uses this to compute
R=N+ 1 (p1)(q1) = N+ 1 2T. If she is right about the value of T,
then Rwill equal p+q, and she can recover pand qby factoring x2T x+N. If
this doesn’t work, she repeats the process with R=N+13T,R=N+14T,
etc. Continuing in this fashion, she should recover pand qfairly quickly.
Eve can save a bit of time in finding the right multiple of T. The idea is
that N+ 1 kT should equal p+q, and in practice pand qwill have more or
less the same order of magnitude. So Eve wants N+ 1 kT 2N, which
means that she should take k(N+ 1 2N)/T .
(b)
gcd(16784693 ·10988423 1,11514115 ·25910155 1)
= gcd(184437306609138,298332504337824)
= 19368558
First Eve tries N+ 1 1·gcd = 19381152, but x219381152x+ 38749709
is irreducible. Next she tries N+ 1 2·gcd = 12594, and this time she finds
that x212594x+ 38749709 = (x7247)(x5347). Hence N= 38749709 =
7247 ·5347.
(c)
gcd(4911157 ·70583995 1,7346999 ·173111957 1,
29597249 ·180311381 1)
= gcd(346649081132214,1271853374967042,5336720840990868)
= 37498566
Eve computes (225022969 1)2/37498566 6.00004193, which suggests
that she should try N+ 1 6·gcd = 31574. This given
x231574x+ 225022969 = (x20707)(x10867).
Hence N= 225022969 = 20707 ·10867.
(d)
gcd(76923209 ·1103927639 1,106791263 ·1022313977 1,
7764043 ·387632407 1)
= gcd(84917656495673550,109174200786382950,3009594676141500)
= 129112350
68 Exercises for Chapter 3
Eve computes (1291233941 1)2/129112350 10.0002987, which suggests
that she should use N+ 1 10 ·gcd = 110442. This yields
x2110442x+ 1291233941 = (x97151)(x13291).
Hence N= 1291233941 = 97151 ·13291.
3.10. Here is an example of a public key system that was proposed at a
cryptography conference. It is supposed to be faster and more efficient than
RSA.
Alice chooses two large primes pand qand she publishes N=pq. It is as-
sumed that Nis hard to factor. Alice also chooses three random numbers g,r1,
and r2modulo Nand computes
g1gr1(p1) (mod N) and g2gr2(q1) (mod N).
Her public key is the triple (N, g1, g2) and her private key is the pair of
primes (p, q).
Now Bob wants to send the message mto Alice, where mis a number
modulo N. He chooses two random integers s1and s2modulo Nand computes
c1=mgs1
1(mod N) and c2mgs2
2(mod N).
Bob sends the ciphertext (c1, c2) to Alice.
Decryption is extremely fast and easy. Alice use the Chinese remainder
theorem to solve the pair of congruences
xc1(mod p) and xc2(mod q).
(a) Prove that Alice’s solution xis equal to Bob’s plaintext m.
(b) Explain why this cryptosystem is not secure.
Solution to Exercise 3.10.
(a) Notice that
c1mgs1
1mgs1r1(p1) m(mod p)
by Fermat’s little theorem, and similarly c2m(mod q). Hence Alice’s
solutions satisfies xm(mod pq).
(b) As in (a), we observe that g11 (mod p) from Fermat’s little theorem.
On the other hand, most likely g16≡ 1 (mod q). So Eve can recover pfrom
the trivial gcd computation
gcd(g11, N) = p.
(If, by some rare coincidence, g11 (mod q), then c1m(mod N), so
although Eve cannot factor N, she can read Bob’s message.)
Section. Implementation and security issues
Exercises for Chapter 3 69
3.11. Formulate a man-in-the-middle attack, similar to the attack described
in Example 3.12 on page 122, for the following public key cryptosystems.
(a) The ElGamal public key cryptosystem (Table 2.3 on page 70).
(b) The RSA public key cryptosystem (Table 3.1 on page 119).
Solution to Exercise 3.11.
A solution for this exercise is not currently available.
3.12. Alice decides to use RSA with the public key N= 1889570071. In
order to guard against transmission errors, Alice has Bob encrypt his message
twice, once using the encryption exponent e1= 1021763679 and once using
the encryption exponent e2= 519424709. Eve intercepts the two encrypted
messages
c1= 1244183534 and c2= 732959706.
Assuming that Eve also knows Nand the two encryption exponents e1and e2,
use the method described in Example 3.14 to help Eve recover Bob’s plaintext
without finding a factorization of N.
Solution to Exercise 3.12.
With notation as in Example 3.14, we find that
u·c1+v·c2= 1
with
u= 252426389 and v=496549570.
Then the plaintext is
mcu
1·cv
21054592380 (mod N).
Section. Primality testing
3.13. We stated that the number 561 is a Carmichael number, but we never
checked that a561 a(mod 561) for every value of a.
(a) The number 561 factors as 3 ·11 ·17. First use Fermat’s little theorem to
prove that
a561 a(mod 3), a561 a(mod 11),and a561 a(mod 17)
for every value of a. Then explain why these three congruences imply that
a561 a(mod 561) for every value of a.
(b) Mimic the idea used in (a) to prove that each of the following numbers is
a Carmichael number. (To assist you, we have factored each number into
primes.)
(i) 1729 = 7 ·13 ·19
(ii) 10585 = 5 ·29 ·73
70 Exercises for Chapter 3
(iii) 75361 = 11 ·13 ·17 ·31
(iv) 1024651 = 19 ·199 ·271
(c) Prove that a Carmichael number must be odd.
(d) Prove that a Carmichael number must be a product of distinct primes.
(e) Look up Korselt’s criterion in a book or online, write a brief description of
how it works, and use it to show that 29341 = 13·37·61 and 172947529 =
307 ·613 ·919 are Carmichael numbers.
Solution to Exercise 3.13.
A solution for this exercise is not currently available.
Here is a list of all Carmichael up to 100000, plus a few others.
561 = 3 ·11 ·17
1105 = 5 ·13 ·17
1729 = 7 ·13 ·19
2465 = 5 ·17 ·29
2821 = 7 ·13 ·31
6601 = 7 ·23 ·41
8911 = 7 ·19 ·67
10585 = 5 ·29 ·73
15841 = 7 ·31 ·73
29341 = 13 ·37 ·61
41041 = 7 ·11 ·13 ·41
46657 = 13 ·37 ·97
52633 = 7 ·73 ·103
62745 = 3 ·5·47 ·89
63973 = 7 ·13 ·19 ·37
75361 = 11 ·13 ·17 ·31
294409 = 37 ·73 ·109
56052361 = 211 ·421 ·631
118901521 = 271 ·541 ·811
172947529 = 307 ·613 ·919
Exercises for Chapter 3 71
1024651 = 19 ·199 ·271
3.14. Use the Miller–Rabin test on each of the following numbers. In each
case, either provide a Miller–Rabin witness for the compositeness of n, or
conclude that nis probably prime by providing 10 numbers that are not
Miller–Rabin witnesses for n.
(a) n= 1105. (Yes, 5 divides n, but this is just a warm-up exercise!)
(b) n= 294409 (c) n= 294409
(d) n= 118901509 (e) n= 118901521
(f) n= 118901527 (g) n= 118915387
Solution to Exercise 3.14.
(a) n1 = 1104 = 24·69.
269 ≡ −138 (mod 1105)
22·69 259 (mod 1105)
24·69 ≡ −324 (mod 1105)
28·69 1 (mod 1105)
Thus 1105 is composite. It factors as n= 5 ·13 ·17.
(b) n1 = 294408 = 23·36801.
236801 512 (mod 294409)
22·36801 ≡ −32265 (mod 294409)
24·36801 1 (mod 294409)
Thus 294409 is composite. It factors as n= 37 ·73 ·109.
(c) n1 = 294438 = 21·147219.
2147219 1 (mod 294439)
3147219 ≡ −1 (mod 294439)
5147219 1 (mod 294439)
Thus 2, 3, 5 are not Miller–Rabin witnesses for 294439. It turns out that
294439 is prime.
(d) n1 = 118901508 = 22·29725377.
72 Exercises for Chapter 3
229725377 7906806 (mod 118901509)
22·29725377 ≡ −1 (mod 118901509)
329725377 ≡ −1 (mod 118901509)
32·29725377 1 (mod 118901509)
529725377 ≡ −1 (mod 118901509)
52·29725377 1 (mod 118901509)
729725377 7906806 (mod 118901509)
72·29725377 ≡ −1 (mod 118901509)
1129725377 ≡ −1 (mod 118901509)
112·29725377 1 (mod 118901509)
Thus 2, 3, 5, 7, and 11 are not Miller–Rabin witnesses for 118901509. It turns
out that 118901509 is prime.
(e) n1 = 118901520 = 24·7431345
27431345 45274074 (mod 118901521)
22·7431345 1758249 (mod 118901521)
24·7431345 1 (mod 118901521)
28·7431345 1 (mod 118901521)
Thus 118901521 is composite. It factors as 118901521 = 271 ·541 ·811.
(f) n1 = 118901526 = 21·59450763.
259450763 1 (mod 118901527)
359450763 ≡ −1 (mod 118901527)
559450763 ≡ −1 (mod 118901527)
759450763 1 (mod 118901527)
1159450763 1 (mod 118901527)
Thus 2, 3, 5, 7, and 11 are not Miller–Rabin witnesses for 118901527. It turns
out that 118901527 is prime.
(g) n1 = 118915386 = 21·59457693.
259457693 ≡ −5081012 (mod 118915387)
Thus 118915387 is composite. It factors as n= 6571 ·18097.
3.15. Looking back at Exercise 3.9, let’s suppose that for a given N, the magic
box can produce only one decryption exponent. Equivalently, suppose that an
RSA key pair has been compromised and that the private decryption exponent
corresponding to the public encryption exponent has been discovered. Show
how the basic idea in the Miller–Rabin primality test can be applied to use
this information to factor N.
Exercises for Chapter 3 73
Solution to Exercise 3.15.
We are given an encryption/decryption pair (e, d), which means that
ade a(mod N) for all 1 a < N.
So for most values of awe have ade11 (mod N). (This is true un-
less gcd(a, N)>1, in which case gcd(a, N ) is a nontrivial factor of N.) Using
the idea of the Miller–Rabin test, we factor
de = 2krwith rodd.
Then for random choices of a, we look at
ar, a2r, a4r, . . . , a2krmod N.
We know that the last entry in the list is 1.
Now suppose that Nfactors as pq, where we do not know pand q. We
choose a value for a. The Miller–Rabin test applied to ptells us that either
ar1 (mod p),or else a2ir≡ −1 (mod p) for some 0 i < k.
(If the latter is true, we take ito be the smallest such value.) Note that we
do not know the value of i, because we do not know the value of p, but that’s
okay. Next we do the same thing with q. Thus the Miller–Rabin test tells us
that either
ar1 (mod q),or else a2jr≡ −1 (mod p) for some 0 j < k,
where again we choose the smallest such j.
We now consider several cases. If ar1 (mod p) and αr6≡ 1 (mod q),
then we recover pby computing
gcd(N, ar1) = p.
Similarly, if ar6≡ 1 (mod p) and αr1 (mod q), then gcd(N, ar1) = q, so
again we win. On the other hand, if ar1 (mod N), then we get no useful
information, so we need to go try a different value for a.
In the remaining cases we have ar6≡ 1 (mod p) and αr6≡ 1 (mod q).
Suppose that iand jare different, say i < j. Then
a2ir≡ −1 (mod p) and a2ir6≡ −1 (mod q),
So computing gcd(N, a2ir+1) = precovers p. A similar method works if j < i.
And finally, if i=j, then we get no useful information and need to try a
different value for a.
We can summarize the above solution as the following algorithm:
1. Choose a random value 1 < a < N .
74 Exercises for Chapter 3
2. Compute gcd(a, N). If it is not equal to 1, then it is a nontrivial factor
of N.
3. Let (e, d) be the encryption/decryption pair. Factor de 1 = 2krwith r
odd.
4. Compute gcd(N, ar1). If it is a nontrivial factor of N, you’re are done.
5. For each 0 i < k, compute gcd(N, a2ir+ 1). If it is a nontrivial factor
of N, you’re done.
6. If you haven’t found a factor of N, go back to Step 1 and choose a new
value of a.
3.16. The function π(X) counts the number of primes between 2 and X.
(a) Compute the values of π(20), π(30), and π(100).
(b) Write a program to compute π(X) and use it to compute π(X) and
the ratio π(X)/(X/ ln(X)) for X= 100, X= 1000, X= 10000, and
X= 100000. Does your list of ratios make the prime number theorem
plausible?
Solution to Exercise 3.16.
X π(X)π(X)/(X/ ln(X)
10 4 0.921
20 8 1.198
30 10 1.134
100 25 1.151
1000 168 1.161
10000 1229 1.132
100000 9592 1.104
1000000 78498 1.084
3.17. Let
π1(X) = (# of primes pbetween 2 and Xsatisfying p1 (mod 4)),
π3(X) = (# of primes pbetween 2 and Xsatisfying p3 (mod 4)).
Thus every prime other than 2 gets counted by either π1(X) or by π3(X).
(a) Compute the values of π1(X) and π3(X) for each of the following values
of X. (i) X= 10. (ii) X= 25. (iii) X= 100.
(b) Write a program to compute π1(X) and π3(X) and use it to compute their
values and the ratio π3(X)1(X) for X= 100, X= 1000, X= 10000,
and X= 100000.
(c) Based on your data from (b), make a conjecture about the relative sizes
of π1(X) and π3(X). Which one do you think is larger? What do you
think is the limit of the ratio π3(X)1(X) as X→ ∞?
Solution to Exercise 3.17.
Exercises for Chapter 3 75
X π1(X)π3(X)π3(X)1(X)
10 1 2 2.0000
25 3 5 1.6667
100 11 13 1.1818
1000 80 87 1.0875
10000 609 619 1.0164
100000 4783 4808 1.0052
1000000 39175 39322 1.0038
(c) From the data, it appears that π3(X)> π1(X) for all X. This is
actually false, but the first Xfor which the inequality is reversed is ex-
tremely large. In any case, the ratio satisfies limX→∞ π3(X)1(X) = 1.
This is a special case of Dirichlet’s theorem on primes in arithmetic pro-
gressions, which says the following. Let gcd(a, N) = 1 and let πa,N (X) be
the number of primes pbetween 2 and Xsatisfying pa(mod N). Then
limX→∞ πa,N (X)(X) = 1(N).
3.18. We noted in Section 3.4 that it really makes no sense to say that the
number nhas probability 1/ln(n) of being prime. Any particular number that
you choose either will be prime or will not be prime; there are no numbers
that are 35% prime and 65% composite! In this exercise you will prove a
result that gives a more sensible meaning to the statement that a number has
a certain probability of being prime. You may use the prime number theorem
(Theorem 3.20) for this problem.
(a) Fix a (large) number Nand suppose that Bob chooses a random number n
in the interval 1
2Nn3
2N. If he repeats this process many times, prove
that approximately 1/ln(N) of his numbers will be prime. More precisely,
define
P(N) = number of primes between 1
2Nand 3
2N
number of integers between 1
2Nand 3
2N
="Probability that an integer nin the
interval 1
2Nn3
2Nis a prime num-
ber #,
and prove that
lim
N→∞
P(N)
1/ln(N)= 1.
This shows that if Nis large, then P(N) is approximately 1/ln(N).
(b) More generally, fix two numbers c1and c2satisfying c1< c2. Bob chooses
random numbers nin the interval c1Nnc2N. Keeping c1and c2
fixed, let
P(c1, c2;N) = "Probability that an integer nin the in-
terval c1Nnc2Nis a prime num-
ber #.
76 Exercises for Chapter 3
In the following formula, fill in the box with a simple function of Nso
that the statement is true:
lim
N→∞
P(c1, c2;N)= 1.
Solution to Exercise 3.18.
We will just write P(N), instead of P(c1, c2;N).
P(N) = # of primes between c1Nand c2N
N
=π(c2N)π(c2N)
N
=c2
ln(c2N)c1
ln(c1N)+oµ1
ln(N)from the prime number theorem
=(c2c1) ln(N) + O(1)
ln(c1N) ln(c2N)+oµ1
ln(N)
=c2c1
ln(N)+oµ1
ln(N)
Hence P(N) divided by (c2c1)/ln(N) goes to 1 as N→ ∞, or equivalently,
lim
N→∞
P(N)
ln(N)=c2c1.
For part (a), we have c1=1
2and c2=3
2, so the limit is 1.
3.19. Continuing with the previous exercise, explain how to make mathemat-
ical sense of the following statements.
(a) A randomly chosen odd number Nhas probability 2/ln(N) of being
prime. (What is the probability that a randomly chosen even number is
prime?)
(b) A randomly chosen number Nsatisfying N1 (mod 3) has probability
3/(2 ln(N)) of being prime.
(c) A randomly chosen number Nsatisfying N1 (mod 6) has probability
3/ln(N) of being prime.
(d) Let m=p1p2···prbe a product of distinct primes and let kbe a number
satisfying gcd(k, m) = 1. What number should go into the box to make
statement (3.35) correct? Why?
A randomly chosen number Nsatisfying
Nk(mod m) has probabil-
ity /ln(N) of being prime.
(3.2)
(e) Same question, but for arbitrary m, not just for mthat are products of
distinct primes.
Exercises for Chapter 3 77
Solution to Exercise 3.19.
(a,b,c) A solution for this exercise is not currently available.
(d) If m=p1···pr, then the probability that Nk(mod m) is prime is
approximately r
Y
i=1 µpi
pi1·1
ln(N).
(e) More generally, for arbitrary mand ksatisfying gcd(m, k) = 1, the prob-
ability that Nk(mod m) is prime is approximately
Y
p|mµp
p1·1
ln(N).
This is often written as
Y
p|mµ11
p1
·1
ln(N),
which is also equal to N/(φ(N) ln(N)), where φ(N) is Euler’s phi function.
3.20. The logarithmic integral function Li(X) is defined to be
Li(X) = ZX
2
dt
ln t.
(a) Prove that
Li(X) = X
ln X+ZX
2
dt
(ln t)2+O(1).
(Hint. Integration by parts.)
(b) Compute the limit
lim
X→∞
Li(X)
X/ ln X.
(Hint. Break the integral in (a) into two pieces, 2 tXand X
tX, and estimate each piece separately.)
(c) Use (b) to show that formula (3.12) on page 131 implies the prime number
theorem (Theorem 3.20).
Solution to Exercise 3.20.
A solution for this exercise is not currently available.
Section. Pollard’s p1factorization algorithm
3.21. Use Pollard’s p1 method to factor each of the following numbers.
(a) n= 1739 (b) n= 220459 (c) n= 48356747
78 Exercises for Chapter 3
Be sure to show your work and to indicate which prime factor pof nhas the
property that p1 is a product of small primes.
Solution to Exercise 3.21.
(a)
23! 163 (mod 1739) gcd(23! 1,1739) = 1
24! 11082 (mod 1739) gcd(24! 1,1739) = 1
25! 11394 (mod 1739) gcd(25! 1,1739) = 1
26! 11443 (mod 1739) gcd(26! 1,1739) = 37
This give 1739 = 37 ·47. Note that p1 = 36 = 22·32and q1 = 46 = 2 ·23.
(b)
23! 163 (mod 220459) gcd(23! 1,220459) = 1
24! 122331 (mod 220459) gcd(24! 1,220459) = 1
25! 185053 (mod 220459) gcd(25! 1,220459) = 1
26! 14045 (mod 220459) gcd(26! 1,220459) = 1
27! 143102 (mod 220459) gcd(27! 1,220459) = 1
28! 1179600 (mod 220459) gcd(28! 1,220459) = 449
This gives 220459 = 449 ·491. Note that p1 = 448 = 26·7 and q1 =
490 = 2 ·5·72.
(c)
215! 146983890 (mod 48356747) gcd(215! 1,48356747) = 1
216! 18398520 (mod 48356747) gcd(216! 1,48356747) = 1
217! 19367159 (mod 48356747) gcd(217! 1,48356747) = 1
218! 117907955 (mod 48356747) gcd(218! 1,48356747) = 1
219! 113944672 (mod 48356747) gcd(219! 1,48356747) = 6917
This gives 48356747 = 6917 ·6991. Note that p1 = 6916 = 22·7·13 ·19 and
q1 = 6990 = 2 ·3·5·233.
3.22. A prime of the form 2n1 is called a Mersenne prime.
(a) Factor each of the numbers 2n1 for n= 2,3, . . . , 10. Which ones are
Mersenne primes?
(b) Find the first seven Mersenne primes. (You may need a computer.)
(c) If nis even and n > 2, prove that 2n1 is not prime.
(d) If 3 |nand n > 3, prove that 2n1 is not prime.
(e) More generally, prove that if nis a composite number, then 2n1 is not
prime. Thus all Mersenne primes have the form 2p1 with pa prime
number.
Exercises for Chapter 3 79
(f) What is the largest known Mersenne prime? Are there any larger primes
known? (You can find out at the “Great Internet Mersenne Prime Search”
web site www.mersenne.org/prime.htm.)
(g) Write a one page essay on Mersenne primes, starting with the discoveries
of Father Mersenne and ending with GIMPS.
Solution to Exercise 3.22.
The factorization of 2n1 for 2 n20 is
221=3=3
231=7=7
241 = 15 = 3 ·5
251 = 31 = 31
261 = 63 = 32·7
271 = 127 = 127
281 = 255 = 3 ·5·17
291 = 511 = 7 ·73
210 1 = 1023 = 3 ·11 ·31
211 1 = 2047 = 23 ·89
212 1 = 4095 = 32·5·7·13
213 1 = 8191 = 8191
214 1 = 16383 = 3 ·43 ·127
215 1 = 32767 = 7 ·31 ·151
216 1 = 65535 = 3 ·5·17 ·257
217 1 = 131071 = 131071
218 1 = 262143 = 33·7·19 ·73
219 1 = 524287 = 524287
220 1 = 1048575 = 3 ·52·11 ·31 ·41
Thus the first few Mersenne primes are
221=3,231 = 7,251 = 31,271 = 127,
213 1 = 8191,217 1 = 131071,219 1 = 524287.
Notice that 2p1 is prime for all primes p < 20 except for p= 11. However,
this is somewhat misleading. For the primes 20 < p < 40, only 231 1 yields
a Mersenne prime.
223 1 = 8388607 = 47 ·178481
229 1 = 536870911 = 233 ·1103 ·2089
231 1 = 2147483647 = 2147483647
237 1 = 137438953471 = 223 ·616318177
241 1 = 2199023255551 = 13367 ·164511353
243 1 = 8796093022207 = 431 ·9719 ·2099863
247 1 = 140737488355327 = 2351 ·4513 ·13264529
(c) If nis even, say n= 2m, then 2n1 = 22m1 = (2m1)(2m+ 1), so
2n1 is composite unless 2m1 = 1, i.e. unless m= 1 and n= 2.
80 Exercises for Chapter 3
(d) Similarly, 23m1 = (2m1)(22m+ 2m+ 1), so it is composite unless
m= 1.
(e) More generally,
2km 1 = (2m1)(2(k1)m+ 2(k2)m+··· + 22m+ 2m+ 1),
so 2km 1 is composite unless m= 1 or k= 1. Notice that what we are really
doing is using the standard identity
xk1 = (x1)(x(k1) +x(k2) +··· +x2+x+ 1)
with x= 2m.
(f) As of January 2008, the largest known Mersenne prime is 232582657 1,
which was discovered in September 2006 as part of the GIMPS project.
Exercises for Chapter 3 81
Section. Factorization via difference of squares
3.23. For each of the following numbers N, compute the values of
N+ 12, N + 22, N + 32, N + 42, . . .
as we did in Example 3.33 until you find a value N+b2that is a perfect
square a2. Then use the values of aand bto factor N.
(a) N= 53357 (b) N= 34571 (c) N= 25777 (d) N= 64213
Solution to Exercise 3.23.
(a)
53357 + 12= 53358 not a square,
53357 + 22= 53361 = 2312** square **.
Thus
53357 = 231222= (231 + 2)(231 2) = 233 ·229.
(b)
34571 + 12= 34572 not a square,
34571 + 22= 34575 not a square,
34571 + 32= 34580 not a square,
34571 + 42= 34587 not a square,
34571 + 52= 34596 = 1862** square **.
Thus
34571 = 186252= (186 + 5)(186 5) = 191 ·181.
(c)
25777 + 12= 25778 not a square
25777 + 22= 25781 not a square
25777 + 32= 25786 not a square
25777 + 42= 25793 not a square
25777 + 52= 25802 not a square
25777 + 62= 25813 not a square
25777 + 72= 25826 not a square
25777 + 82= 25841 not a square
25777 + 92= 25858 not a square
25777 + 102= 25877 not a square
25777 + 112= 25898 not a square
25777 + 122= 25921 = 1612** square **
82 Exercises for Chapter 3
Thus
25777 = 1612122= (161 + 12)(161 12) = 173 ·149.
(d) Most people will give up before finishing this one unless they write a
computer program! It is included to make people aware that this method
doesn’t always work.
64213 + 12= 64214 not a square
64213 + 22= 64217 not a square
64213 + 32= 64222 not a square
64213 + 42= 64229 not a square
.
.
..
.
.
64213 + 1212= 78854 not a square
64213 + 1222= 79097 not a square
64213 + 1232= 79342 not a square
64213 + 1242= 79589 not a square
64213 + 1252= 79838 not a square
64213 + 1262= 80089 = 2832** square **
Thus
64213 = 28321262= (283 + 126)(283 126) = 409 ·157.
3.24. For each of the listed values of N,k, and binit, factor Nby making
a list of values of k·N+b2, starting at b=binit and incrementing buntil
k·N+b2is a perfect square. Then take greatest common divisors as we did
in Example 3.34.
(a) N= 143041 k= 247 binit = 1
(b) N= 1226987 k= 3 binit = 36
(c) N= 2510839 k= 21 binit = 90
Solution to Exercise 3.24.
(a)
247 ·143041 + 12= 35331128 not a square
247 ·143041 + 22= 35331131 not a square
247 ·143041 + 32= 35331136 = 59442** square **
Thus
247 ·143041 = 5944232= (5944 + 3)(5944 3) = 5947 ·5941.
Exercises for Chapter 3 83
gcd(143041,5947) = 313,gcd(143041,5941) = 457
(b)
3·1226987 + 362= 3682257 not a square
3·1226987 + 372= 3682330 not a square
3·1226987 + 382= 3682405 not a square
3·1226987 + 392= 3682482 not a square
3·1226987 + 402= 3682561 = 19192** square **
Thus
3·1226987 = 19192402= (1919 + 40)(1919 40) = 1959 ·1879.
gcd(1226987,1959) = 653,gcd(1226987,1879) = 1879
(c)
21 ·2510839 + 902= 52735719 not a square
21 ·2510839 + 912= 52735900 not a square
21 ·2510839 + 922= 52736083 not a square
21 ·2510839 + 932= 52736268 not a square
21 ·2510839 + 942= 52736455 not a square
21 ·2510839 + 952= 52736644 = 72622** square **
Thus
21 ·2510839 = 72622952= (7262 + 95)(7262 95) = 7357 ·7167.
gcd(2510839,7357) = 1051,gcd(2510839,7167) = 2389
3.25. For each part, use the data provided to find values of aand bsatisfying
a2b2(mod N), and then compute gcd(N, a b) in order to find a nontrivial
factor of N, as we did in Examples 3.36 and 3.37.
(a) N= 61063
18822270 (mod 61063) and 270 = 2 ·33·5
1898260750 (mod 61063) and 60750 = 2 ·35·53
(b) N= 52907
3992480 (mod 52907) and 480 = 25·3·5
7632192 (mod 52907) and 192 = 26·3
773215552 (mod 52907) and 15552 = 26·35
9762250 (mod 52907) and 250 = 2 ·53
84 Exercises for Chapter 3
(c) N= 198103
1189227000 (mod 198103) and 27000 = 23·33·53
16052686 (mod 198103) and 686 = 2 ·73
23782108000 (mod 198103) and 108000 = 25·33·53
28152105 (mod 198103) and 105 = 3 ·5·7
(d) N= 2525891
159125390 (mod 2525891) and 5390 = 2 ·5·72·11
3182221560 (mod 2525891) and 21560 = 23·5·72·11
4773248510 (mod 2525891) and 48510 = 2 ·32·5·72·11
5275240824 (mod 2525891) and 40824 = 23·36·7
540121386000 (mod 2525891) and 1386000 = 24·32·53·7·11
Solution to Exercise 3.25.
(a)
18822·18982(2 ·33·5)(2 ·35·53) (mod 61063)
= (2 ·34·52)2
= 40502
gcd(61063,1882 ·1898 4050) = 227 Eureka!
(b) The most natural combination to try first is
7632·7732(26·3)(26·35) (mod 52907)
= (26·33)2
= 17282
gcd(52907,763 ·773 1728) = 277 Eureka!
So this works. However, if instead we use
3992·7632·9762(25·3·5)(26·3)(2 ·53) (mod 52907)
= (26·3·52)2
= 48002,
then we do not win, since
gcd(52907,399 ·763 ·976 4800) = 52907 No help
(c) First we try
Exercises for Chapter 3 85
11892·23782(23·33·53)(25·33·53) (mod 198103)
= (24·33·53)2
= 540002
gcd(198103,1189 ·2378 54000) = 198103 No help
This didn’t work, so next we try
11892·16052·28152(23·33·53)(2 ·73)(3 ·5·7) (mod 198103)
= (22·32·52·72)2
= 441002
gcd(198103,1189 ·1605 ·2815 44100) = 499 Eureka!
(d) First we try
15912·31822(2 ·5·72·11)(23·5·72·11) (mod 2525891)
= (22·5·72·11)2
= 107802
gcd(2525891,1591 ·3182 10780) = 2525891 No help
Next we try
15912·47732(2 ·5·72·11)(2 ·32·5·72·11) (mod 2525891)
= (2 ·3·5·72·11)2
= 161702
gcd(2525891,1591 ·4773 16170) = 2525891 No help
Finally we win when we try
15912·52752·54012
(2 ·5·72·11)(23·36·7)(24·32·53·7·11) (mod 2525891)
= (24·34·52·72·11)2
= 174636002
gcd(2525891,1591 ·5275 ·5401 17463600) = 1637 Eureka!
Section. Smooth numbers, sieves, and building relations for factorization
3.26. Compute the following values of ψ(X, B), the number of B-smooth
numbers between 2 and X(see page 146).
(a) ψ(25,3) (b) ψ(35,5) (c) ψ(50,7) (d) ψ(100,5)
(e) ψ(100,7)
86 Exercises for Chapter 3
Solution to Exercise 3.26.
(a) ψ(25,3) = 10
(b) ψ(35,5) = 18
(c) ψ(50,7) = 30
(d) ψ(100,5) = 33
(e) ψ(100,7) = 45
3.27. An integer Mis called B-power-smooth if every prime power pedi-
viding Msatisfies peB. For example, 180 = 22·32·5 is 10-power-smooth,
since the largest prime power dividing 180 is 9, which is smaller than 10.
(a) Suppose that Mis B-power-smooth. Prove that Mis also B-smooth.
(b) Suppose that Mis B-smooth. Is it always true that Mis also B-power-
smooth? Either prove that it is true or give an example for which it is
not true.
(c) The following is a list of 20 randomly chosen numbers between 1 and 1000,
sorted from smallest to largest. Which of these numbers are 10-power-
smooth? Which of them are 10-smooth?
{84,141,171,208,224,318,325,366,378,390,420,440,
504,530,707,726,758,765,792,817}
(d) Prove that Mis B-power-smooth if and only if Mdivides the least com-
mon multiple of [1,2, . . . , B]. (The least common multiple of a list of
numbers k1, . . . , kris the smallest number Kthat is divisible by every
number in the list.)
Solution to Exercise 3.27.
(a,b,d) A solution for this exercise is not currently available.
(c) The numbers 84 = 22·3·7, 420 = 22·3·5·7, 504 = 23·32·7, and are
10-power-smooth. They are also 10-smooth, of course, as are the additional
numbers 224 = 25·7 and 378 = 2 ·33·7.
3.28. Let L(N) = e(ln N)(ln ln N)as usual. Suppose that a computer does
one billion operations per second.
(a) How many seconds does it take to perform L(2100) operations?
(b) How many hours does it take to perform L(2250) operations?
(c) How many days does it take to perform L(2350) operations?
(d) How many years does it take to perform L(2500) operations?
(e) How many years does it take to perform L(2750) operations?
(f) How many years does it take to perform L(21000) operations?
(g) How many years does it take to perform L(22000) operations?
(For simplicity, you may assume that there are 365.25 days in a year.)
Solution to Exercise 3.28.
(a) N= 2100 :L(N) = 224.73 steps takes 0.03 seconds.
(b) N= 2250 :L(N) = 243.12 steps takes 2.65 hours.
Exercises for Chapter 3 87
(c) N= 2350 :L(N) = 252.66 steps takes 82.24 days.
(d) N= 2500 :L(N) = 264.95 steps takes 1129.30 years.
(e) N= 2750 :L(N) = 282.26 steps takes 108.26 years.
(f) N= 21000 :L(N) = 297.14 steps takes 1012.74 years.
(g) N= 22000 :L(N) = 2144.48 steps takes 1026.99 years.
3.29. Prove that the function L(X) = e(ln X)(ln ln X)is subexponential. That
is, prove the following two statements.
(a) For every positive constant α, no matter how large, L(X) = Ω¡(ln X)α¢.
(b) For every positive constant β, no matter how small, L(X) = O¡Xβ).
Solution to Exercise 3.29.
A solution for this exercise is not currently available.
3.30. For any fixed positive constants aand b, define the function
Fa,b(X) = e(ln X)1/a (ln ln X)1/b .
Prove the following properties of Fa,b(X).
(a) If a > 1, prove that Fa,b(X) is subexponential.
(b) If a= 1, prove that Fa,b(X) is exponential.
(c) What happens if a < 1?
Solution to Exercise 3.30.
A solution for this exercise is not currently available.
3.31. This exercise asks you to verify an assertion in the proof of Corol-
lary 3.44. Let L(X) be the usual function L(X) = e(ln X)(ln ln X).
(a) Prove that there is a value of  > 0 such that
(ln X)²<ln L(X)<(ln X)1²for all X > 10.
(b) Let c > 0, let Y=L(X)c, and let u= (ln X)/(ln Y). Prove that
uu=L(X)1
2c(1+o(1)).
Solution to Exercise 3.31.
(a) is clear, any  < 1
2will work.
(b) We first compute
u=ln X
ln L(X)c=ln X
cp(ln X)(ln ln X)=1
crln X
ln ln X.
Then
88 Exercises for Chapter 3
uln u=1
crln X
ln ln Xln Ã1
crln X
ln ln X!
=1
crln X
ln ln X·1
2ln ln X1
2ln ln ln Xln c¸
=1
2cln Xln ln X¡1 + o(1)¢
=1
2c¡ln L(X)¢¡1 + o(1)¢.
Hence
uu=L(X)1
2c(1+o(1)).
3.32. Proposition 3.47 assumes that we choose random numbers amodulo N,
compute a2(mod N), and check whether the result is B-smooth. We can
achieve better results if we take values for aof the form
a=¥N¦+kfor 1 kK.
(For simplicity, you may treat Kas a fixed integer, independent of N. More
rigorously, it is necessary to take Kequal to a power of L(N), which has a
small effect on the final answer.)
(a) Prove that a2N2KN+K2, so in particular, a2(mod N) is smaller
than a multiple of N.
(b) Prove that L(N)L(N)1/2by showing that
lim
N→∞
log L(N)
log L(N)1/2= 1.
More generally, prove that in the same sense, L(N1/r )L(N)1/rfor
any fixed r > 0.
(c) Re-prove Proposition 3.47 using this better choice of values for a. Set
B=L(N)cand find the optimal value of c. Approximately how many
relations are needed to factor N?
Solution to Exercise 3.32.
(a) We have a=N++kfor some 0  < 1. Hence a2N=
2(+k)N+ (+k)22KN+K2.
(b) A rough computation shows that
L(N) = e(ln N)(ln ln N)
=e(1
2ln N)(ln 1
2ln N)
e(1
2ln N)(ln ln N)=L(N)1/2.
Exercises for Chapter 3 89
More precisely, we first simplify
log L(N1/r)
log L(N)1/r=ln N1/r ln ln N1/r
(1/r)ln Nln ln N
=s(1/r)(ln N)(ln(1/r