# Solutions Manual

User Manual: Pdf

Open the PDF directly: View PDF .

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

An Introduction to Mathematical

Cryptography

Solution Manual

Jeﬀrey Hoﬀstein, Jill Pipher, Joseph H. Silverman

c

°2008 by J. Hoﬀstein, 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 ﬁrst 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 Jeﬀerson, 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 ﬁnds.

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 ﬁve 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 ﬂowers—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 triﬂing 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 ﬁxed if the encryption of the letter

is the letter itself. How many simple substitution ciphers are there that

leave:

(i) no letters ﬁxed?

(ii) at least one letter ﬁxed?

(iii) exactly one letter ﬁxed?

(iv) at least two letters ﬁxed?

(Part (b) is quite challenging! You might try doing the problem ﬁrst with an

alphabet of four or ﬁve 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 diﬀerent simple

substitution ciphers.

(b) Let S(n, k) denote the number of permutations of nelements that ﬁx at

least kelements. You might guess that since there are ¡n

k¢ways to choose k

elements to ﬁx and (n−k)! permutations of the remaining n−kelements,

S(n, k) = µn

k¶(n−k)! ←− Incorrect Formula.(1.1)

6 Exercises for Chapter 1

But this overcounts because any permutation ﬁxing more than n−kele-

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 ﬁx exactly kelements, and !(n−k)

(the subfactorial of (n−k)) denote the number of permutations of n−kele-

ments that ﬁx no elements (such permutations are called derangements), then

the following equation holds:

R(n, k) = µn

k¶!(n−k).(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 ﬁx at least 1 element}.(1.3)

Now if we notice that

#{permutations that ﬁx at least 1 element}=

#{permutations that ﬁx element 1}

∪{permutations that ﬁx element 2}

∪··· ∪ {permutations that ﬁx element n}(1.4)

and use an analogue of the following formula in probability (often called the

inclusion–exclusion principle):

P(E1∪E2∪ ··· ∪ En) =

n

X

i=1

P(Ei) + X

i1<i2

P(Ei1∩Ei2) + . . .

+(−1)r+1 X

i1<i2<···<ir

P(Ei1∩Ei2∩Eir) + . . .

+(−1)n+1P(E1∩E2∩ ··· ∩ En) (1.5)

we see that

!n=

n

X

i=1

#{permutations that ﬁx element i}

−

n

X

i1<i2

#{permutations that ﬁx elements i1and i2}+. . .

+(−1)r+1 X

i1<i2<···<ir

#{permutations that ﬁx elements i1,i2, . . . ir}+. . .

+(−1)n+1#{permutations that ﬁx everything}.(1.6)

Exercises for Chapter 1 7

Given kelements, the number of permutations ﬁxing them is (n−k)!

regardless of which kelements you ﬁx, and there are ¡n

k¢ways to choose k

elements to ﬁx. So the above equation becomes

!n=µn

1¶(n−1)! −µn

2¶(n−2)! + . . .

+(−1)k+1µn

k¶(n−k)! + ··· + (−1)n+1(n−n)!.(1.7)

Now noticing that

µn

k¶(n−k)! = n!

(n−k)!k!(n−k)! = 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 e−1. Thus

n

X

k=0

(−1)k

k!=e−1−∞

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!−e−1¯¯¯<1

(n+ 1)!.

Multiplying by n! and using (??) yields

¯¯¯!n−n!

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¶!(n−k) = µn

k¶¹(n−k)!

e¼,

and then we can compute S(n, k) using

S(n, k) =

n

X

j=k

R(n, j) = n!−

k−1

X

j=0

R(n, j).(1.10)

8 Exercises for Chapter 1

(b-i) No letters ﬁxed 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 ﬁxed is n! minus no letters ﬁxed, 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 ﬁxed is

R(n, 1) = n·!(n−1) = n¹(n−1)!

e¼,

so

R(26,1) = 26 ¹25!

e¼= 148362637348470135821287824.

(b-iv) At least two letters ﬁxed is n! minus zero or one letters ﬁxed, so

S(n, 1) = n!−R(n, 0) −R(1,0) = n!−!n−n·!(n−1)

=n!− bn!/ee − nb(n−1)!/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 deﬁnition 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|(b−c).

Solution to Exercise 1.6.

(a) By deﬁnition 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 deﬁnition 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 deﬁnition we have b=au and c=av for some integers uand v. Then

b±c=au ±av =a(u±v),

so both b+cand b−care 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=a−b·q= 193.

(b) a= 238792, b= 7843, a/b = 30.44651281, q= 30, r=a−b·q= 3502.

(c) a= 9829387493, b= 873485, a/b = 11253.06959249, q= 11253, r=

a−b·q= 60788.

(d) a= 1498387487, b= 76348, a/b = 19625.75950909, q= 19625, r=

a−b·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.

r≈127 ·0.03937008 ≈4.99999889,so r= 5.

(b) a= 2837647, b= 4387, a/b = 646.83086392.

r≈4387 ·0.83086392 ≈3644.99997317,so r= 3645.

(c) a= 8739287463, b= 18754, a/b = 465995.91889730.

r≈18754 ·0.91889730 ≈17232.99996420,so r= 17233.

(d) a= 4536782793, b= 9784537, a/b = 463.66862254.

r≈9784537 ·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 ﬁnd 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 speciﬁc 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 v2−v1and that bdivides u2−u1.

(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=v0−ka/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 speciﬁc 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 ﬁnd a solution to g=ax +by, so we get

au +bv =c=gq +r= (ax +by)q+r.

Rearranging this yields

a(u−xq) + b(v−yq) = 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(u−u0) = −b(v−v0).

Dividing both sides by ggives

a

g(u−u0) = −b

g(v−v0).

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 v−v0. Hence

v−v0=a

gxfor some integer x.

The same reasoning tells us that

u−u0=b

gyfor some integer y.

Hence

u=u0+b

gyand v=v0+a

gx.

Substituting into the equation a

g(u−u0) = −b

g(v−v0) 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=v0−a

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 ineﬃcient. 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= (g−au)/b and return the values (g, u, v)

3. Divide gby ywith remainder, g=qy +t, with 0≤t < y

4. Set s=u−qx

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

modiﬁed 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 ﬁnd 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 k≥3, and we want to prove it for kintegers. By the induction

hypothesis, we can ﬁnd a solution to

a1u1+a2u2+··· +ak−1uk−1= gcd(a1, . . . , ak−1).

To ease notation, we let b= gcd(a1, . . . , ak−1). 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+··· +ak−1uk−1v= gcd(a1, . . . , ak−1)v

=bv by deﬁnition of b,

=−akw+ gcd(b, ak).

Hence

a1u1v+a2u2v+··· +ak−1uk−1v+akw= gcd(b, ak).

This completes the proof, since from the deﬁnition of gcd as the largest integer

dividing all of the listed integers, it’s clear that

gcd(b, ak) = gcd¡gcd(a1, . . . , ak−1), ak¢= gcd(a1, . . . , ak−1, ak).

Section. Modular arithmetic

14 Exercises for Chapter 1

1.14. Let m≥1 be an integer and suppose that

a1≡a2(mod m) and b1≡b2(mod m).

Prove that

a1±b1≡a2±b2(mod m) and a1·b1≡a2·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, ﬁll in the box

with an integer between 0 and m−1, 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) 1372≡130 (mod 327).

(g) 3736≡463 (mod 581).

(h) 233·195·114≡93 (mod 97).

1.17. Find all values of xbetween 0 and m−1 that are solutions of the

following congruences. (Hint. If you can’t ﬁgure out a clever way to ﬁnd the

solution(s), you can just substitute each value x= 1, x= 2,. . . , x=m−1

and see which ones work.)

(a) x+ 17 ≡23 (mod 37).

(b) x+ 42 ≡19 (mod 51).

(c) x2≡3 (mod 11).

(d) x2≡2 (mod 13).

(e) x2≡1 (mod 8).

16 Exercises for Chapter 1

(f) x3−x2+ 2x−2≡0 (mod 11).

(g) x≡1 (mod 5) and also x≡2 (mod 7). (Find all solutions modulo 35,

that is, ﬁnd the solutions satisfying 0 ≤x≤34.)

Solution to Exercise 1.17.

(a) x≡23 −17 ≡6 (mod 37).

(b) x≡19 −42 ≡ −23 ≡28 (mod 51).

(c) The squares modulo 11 are 02≡0, 12≡1, 22≡4, 32≡9, 42≡16 ≡5,

etc. The full list is {0,1,4,9,5,3,3,5,9,4,1}. Thus 52≡2 (mod 11) and

62≡2 (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 x2≡1 (mod 8) are x= 1, x= 3, x= 5 and x= 7 .

(f) Plugging x= 0,1,2, . . . , 10 into x3−x2+ 2x−2 and reducing modulo 11,

we ﬁnd 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 x≡1 (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,

1≡1,6≡6,11 ≡4,16 ≡2,21 ≡0,26 ≡5,31 ≡3.

Thus the solution is x= 16 .

1.18. Suppose that ga≡1 (mod m) and that gb≡1 (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)v≡1u·1v≡1 (mod p).

1.19. Prove that if a1and a2are units modulo m, then a1a2is a unit modulo

m.

Solution to Exercise 1.19.

By deﬁnition of unit, there are numbers b1and b2so that

a1b1≡1 (mod m) and a2b2≡1 (mod m).

Then

(a1a2)(b1b2)≡(a1b1)(a2b2)≡1·1≡1 (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) = m−1, where φis Euler’s

phi function.

Solution to Exercise 1.20.

Suppose ﬁrst that mis prime. Let kbe any number between 1 and m−1

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 m−1

satisﬁes gcd(k, m) = 1. Hence

φ(m) = #©1≤k < m : gcd(k, m) = 1ª= #{1,2,3, . . . , m −1}=m−1.

Next suppose that φ(m) = m−1. This means that every number kbe-

tween 1 and m−1 satisﬁes gcd(k, m) = 1. Suppose that ddivides mand

that d6=m. Then 1 ≤d≤m−1, 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 m∈Z.

(a) Suppose that mis odd. What integer between 1 and m−1 equals 2−1mod m?

(b) More generally, suppose that m≡1 (mod b). What integer between 1

and m−1 is equal to b−1mod 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 m≡1 (mod b) means that m−1

bis an integer, so

we have

b·m−1

b=m−1≡ −1 (mod m).

This is almost what we want, so multiply by −1 to get

b·1−m

b= 1 −m≡1 (mod m).

Unfortunately, 1−m

bis negative, but we can add on multiples of mwithout

changing its value modulo m. Thus 1−m

b+m=1+(b−1)m

bis an integer and

b·1+(b−1)m

b= 1 + (b−1)m≡1 (mod m).

Hence b−1mod mis equal to 1+(b−1)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+a2≡2 + 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

x≡3 (mod 7) and x≡4 (mod 9).

(Hint. Note that every solution of the ﬁrst 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

x≡13 (mod 71) and x≡41 (mod 97).

(c) Find a single value xthat simultaneously solves the three congruences

x≡4 (mod 7), x ≡5 (mod 8),and x≡11 (mod 15).

(d) Prove that if gcd(m, n) = 1, then the pair of congruences

x≡a(mod m) and x≡b(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 ﬁrst 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 ﬁnd a value of zsuch that

a+my −b=nz.

In other words, we need integers yand zsatisfying

my −nz =b−a.

We are given that gcd(m, n) = 1, so we can ﬁnd integers uand vsatisfying

mu +nv = 1. Multiplying this by b−agives

mu(b−a) + nv(b−a) = b−a,

Exercises for Chapter 1 19

so we can take y=u(b−a) and z=v(b−a). Then we have x=a+my =

a+mu(b−a).

To summarize, we ﬁrst solve mu +nv = 1 and then we take

x=a+mu(b−a) = a+ (1 −nv)(b−a) = b+nv(b−a).

The two expressions for xshow that x≡a(mod m) and x≡v(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 A≡1 (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.

*** ﬁll in solution

1.25. Use the square-and-multiply algorithm described in Section 1.3.2, or the

more eﬃcient 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 ﬁnite ﬁelds

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 inﬁnitely many prime numbers. (This proof of

the inﬁnitude 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 N≥2, we know that it must

be divisible by some prime.) Suppose that qwere equal to some pi. Then we

would have

1 = N−p1p2···pr≡0 (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 ﬁnitely many primes. That means we

can list them, say p1, p2, . . . , pr. But from the ﬁrst part of the exercise, we can

create a new prime that’s not in our list. This contradicts the assumption that

there are ﬁnitely many primes, and hence proves that there must be inﬁnitely

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 ﬁnd 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 deﬁnition 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 deﬁnition,

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 deﬁnition 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 ﬁrst 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 ﬁnite ﬁelds

1.30. For each of the following primes pand numbers a, compute a−1mod 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 11−1≡ −17 ≡30 (mod 47). (ii) Fermat’s

little theorem gives

11−1≡1145 ≡30 (mod 47).

(b) (i) We use the extended Euclidean algorithm to solve

345u+ 587v= 1.

The solution is (u, v) = (114,−67), so 345−1≡114 (mod 587). (ii) Fermat’s

little theorem gives

345−1≡345585 ≡114 (mod 587).

(c) (i) We use the extended Euclidean algorithm to solve

78467u+ 104801v= 1.

The solution is (u, v) = (1763,−1320), so 78467−1≡1763 (mod 104801). (ii)

Fermat’s little theorem gives

78467−1≡78467104799 ≡1763 (mod 104801).

1.31. Let pbe a prime and let qbe a prime that divides p−1.

(a) Let a∈F∗

pand let b=a(p−1)/q. Prove that either b= 1 or else bhas

order q. (Recall that the order of bis the smallest k≥1 such that bk= 1

in F∗

p.Hint. Use Proposition 1.30.)

(b) Suppose that we want to ﬁnd an element of F∗

pof order q. Using (a), we

can randomly choose a value of a∈F∗

pand check whether b=a(p−1)/q

satisﬁes b6= 1. How likely are we to succeed? In other words, compute

the value of the ratio

#{a∈F∗

p:a(p−1)/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=ap−1= 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 g∈F∗

pbe a primitive root. Then every a∈F∗

phas the form gifor

some 0 ≤i < p −1. We’ll count the number of awith a(p−1)/q = 1. Thus

Exercises for Chapter 1 23

#{a∈F∗

p:a(p−1)/q = 1}= #{0≤i < p −1 : (gi)(p−1)/q = 1}

= #{0≤i < p −1 : gi(p−1)/q = 1}.

Since ghas order p−1, we have gk= 1 if and only if p−1|k. Hence

gi(p−1)/q = 1 ⇐⇒ p−1|i(p−1)/q ⇐⇒ q|i.

Hence

#{a∈F∗

p:a(p−1)/q = 1}= #{0≤i < p −1 : q|i}=p−1

q.

It follows that

#{a∈F∗

p:a(p−1)/q 6= 1}=p−1−#{a∈F∗

p:a(p−1)/q = 1}

=p−1−p−1

q= (p−1) µ1−1

q¶.

Hence #{a∈F∗

p:a(p−1)/q 6= 1}

#F∗

p

= 1 −1

q,

so if qis large, we have a very good chance of succeeding on our ﬁrst 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 ﬁnd

all primitive roots modulo 229. Verify that there are exactly φ(229) of

them.

(f) Use your program from (e) to ﬁnd all primes less than 100 for which 2 is

a primitive root.

(g) Repeat the previous exercise to ﬁnd all primes less than 100 for which 3

is a primitive root. Ditto to ﬁnd 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 inﬁnitely 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(p−1) 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 p−1 from Proposition 1.30. Since p−1 = 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=p−1, 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

X2≡b(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, ﬁnd 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 a≡gk(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

1−band pdivides a2

2−b, so pdivides their diﬀerence

(a2

1−b)−(a2

2−b) = a2

1−a2

2= (a1−a2)(a1+a2).

It follows that pdivides either a1−a2or a1+a2. If the former, then a1≡a2

(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 p≥3, then p−ais a second

solution diﬀerent from a, so if there are any solutions, then there are exactly

two solutions. On the other hand, if p= 2, then X2≡b(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 X2≡29 (mod 35), so 29 has four

square roots modulo 35. This does not contradict (a), since the modulus 35

is not prime.

(d) Suppose ﬁrst that kis even, say k= 2j. Then

a≡gk≡g2j≡(gj)2(mod p),

so ais a square modulo p.

Next suppose ais a square, say a≡b2(mod p). Since gis a primitive root,

we can write b≡gi(mod p) for some exponent i. Then

gk≡a≡b2≡(gi)2≡g2i(mod p).

Thus gk−2i≡1 (mod p), and the fact that gis a primitive root implies

that p−1 divides k−2i. But p−1 is even, hence 2 divides k−2i, so 2

divides k.

1.35. Let p≥3 be a prime and suppose that the congruence

X2≡b(mod p)

has a solution.

26 Exercises for Chapter 1

(a) Prove that for every exponent e≥1 the congruence

X2≡b(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 X2≡b(mod p). Prove that in (a), we can ﬁnd

a solution X=βto X2≡b(mod pe) that also satisﬁes β≡α(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 X2≡b(mod p). We are going to prove by induction that for

every e≥1 there is a unique value βmod pesatisfying both

β2≡b(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 X2≡b(mod pe+1).

We also want to use the fact that βis a solution to X2≡b(mod pe). This

means that

β2=b+peBfor some integer B.

Now we substitute γ=β+ypeinto the congruence X2≡b(mod pe+1) and

try to solve for y. Thus

(β+ype)2≡b(mod pe+1)

β2+ 2ype+y2p2e≡b(mod pe+1)

β2+ 2ype≡b(mod pe+1) since 2e≥e+ 1,

b+peB+ 2ype≡b(mod pe+1) since β2=b+peB,

pe(B+ 2y)≡0 (mod pe+1).

Thus we need to solve

B+ 2y≡0 (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,

y≡p−1

2B(mod p).

This completes the proof that for every e≥1 there exists a unique value of β

(mod pe) satisfying

β2≡b(mod pe) and β≡α(mod p),

which gives all of the statements in (a), (b), and (b).

(d) From the earlier exercise we know that X2≡b(mod p) has either 0

or 2 solutions. If it has no solutions, there there certainly aren’t any solutions

to X2≡b(mod pe) for e≥2, since any such solution could always be

reduced modulo p. On the other hand, if X2≡b(mod p) has two solutions,

then (a), (b), and (c) together imply that there are also two solutions to

X2≡b(mod pe) for each e≥1, since the solutions to X2≡b(mod p) are

matched up one-to-one with the solutions to X2≡b(mod pe).

This exercise is a very special case of Hensel’s lemma.

1.36. Compute the value of

2(p−1)/2(mod p)

for every prime 3 ≤p < 20. Make a conjecture as to the possible values of

2(p−1)/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(p−1)/2is congruent to either 1 or p−1 modulo p.

Proof : Let a= 2(p−1)/2. Then a2≡2p−1≡1 (mod p) by Fermat’s little

theorem. Therefore a≡ ±1 (mod p). To see this last fact, note that p|(a2−1),

so p|(a−1)(a+ 1), so since pis prime, it divides one of a−1 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 ﬁrst 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 ﬁrst 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 oﬀ 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 ﬁrst 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 aﬃne 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 aﬃne 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 aﬃne cipher. The

value of pis public knowledge, and Eve intercepts the ciphertexts c1=

324 and c2= 381 and also manages to ﬁnd 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 aﬃne 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 c≡34·204+71 ≡7007 ≡515 (mod 541).

The inverse of k1is 34−1≡366 (mod 541). The decryption of c= 431 is

m≡366(431 −71) ≡297 (mod 541).

(b) Given two plaintext/ciphertext pairs, one can solve the two linear con-

gruences

c1≡k1·m1+k2(mod p) and c2≡k1·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 ﬁrst equation from the second to get

57 ≡k1·104 (mod 601).

She computes 104−1≡549 (mod 601), and hence

k1≡57 ·104−1≡41 (mod 601).

Then she uses either of the above congruences to recover k2,

k2≡324 −k1·387 ≡83 (mod 601).

Eve now knows Alice and Bob’s private key, so she can encrypt a message,

c3≡k1·m3+k2≡41 ·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

c1≡k1m1+k2(mod p)

c2≡k1m2+k2(mod p)

c3≡k1m3+k2(mod p)

We can write this in suggestive matrix and vector notation at

c1m11

c2m21

c3m31

¡1−k1−k2¢≡¡0 0 0¢(mod p).

Using linear algebra modulo p, this implies that the determinant of the matrix

satisﬁes

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 ndiﬀerent pairs, she can compute determinant

values D1, . . . , Dn−2by using diﬀerent pairs in the last row of the matrix

(keeping the ﬁrst 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 ﬁnd that

gcd(D1, . . . , Dn−2) is equal to p.

1.42. Consider the Hill cipher deﬁned by (1.11),

ek(m)≡k1·m+k2(mod p) and dk(c)≡k−1

1·(c−k2) (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 k−1

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)k−1

1=3 6

4 5 .

(a −iii)dk(c) = 0 4 .

(b) Each known plaintext/ciphertext pair gives a congruence of the form

c≡k1·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+u≡1 (mod 11) and 5z+ 4w+v≡8 (mod 11).

Similarly, the congruence c2=k1m2+k2(mod 11) gives

8x+ 10y+u≡8 (mod 11) and 8z+ 10w+v≡5 (mod 11).

and c3=k1m3+k2(mod 11) gives

7x+y+u≡8 (mod 11) and 7z+w+v≡7 (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 ﬁnd that

(x, y, u) = (3,7,2) and (z, w, v) = (4,3,9).

Hence

k1=µ3 7

4 3¶and 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)≡k−m(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) = k−c

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)≡k−1c(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 deﬁne a decryption

“function” by dk(c)≡√c−k(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 ﬁgure 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 insuﬃcient 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 hours¶≈83.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

diﬀerent 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 reﬂects the fact that exponential functions

grow extremely rapidly.

1.46. Explain why the cipher

ek(m) = k⊕mand dk(c) = k⊕c

deﬁned by XOR of bit strings is not secure against a chosen plaintext attack.

Demonstrate your attack by ﬁnding 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=k⊕m, it follows that

c⊕m=k⊕m⊕m=k. For the example,

k=c⊕m= 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={m∈Z: 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

c≡m+α(mod 10d).

Since Bob knows k, he can also ﬁnd α, and then he decrypts cby comput-

ing m≡c−α(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− b√kc´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 α≡c−m(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 L∈Z.

There are two unknowns here, kand L, and all that Eve knows is that they

are both integers. Squaring both sides gives

k=L2+ 2Lβ +β2.

Thus there are integers Aand Bsatisfying

β2+Aβ +B= 0,

namely A= 2Land B=L2−k. Of course, Eve doesn’t know Aor B, either.

However, there are algorithms based on lattice reduction that are very good at

ﬁnding the smallest (quadratic) polynomial with integer coeﬃcients satisﬁed

by a given decimal number. Using these algorithms, Eve should be able to

ﬁnd Aand B, from which it is easy to recover kas k=1

4A2−B.

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 ﬁnd 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

Diﬃe–Hellman

Exercises for Chapter 2

Section. Diﬃe–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 classiﬁcation of cryp-

tographic algorithms as munitions under ITAR (International Traﬃc in Arms

Regulations). How does that act deﬁne “export”? What are the potential

ﬁnes and jail terms for those convicted of violating the Arms Export Control

Act? Would teaching non-classiﬁed 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 ﬁled suit today in federal

court, challenging government regulations which restrict his ability to teach

a course in computer law. Peter Junger, a twenty-ﬁve year veteran of the

law school faculty, will ﬁle 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 Traﬃc 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 signiﬁcant First Amendment ques-

tions by deﬁning “export” to include discussing technical information about

non-classiﬁed 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 ﬁnes 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 ﬁled 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

gx≡h(mod p). Prove that a≡b(mod p−1). Explain why this implies

that the map (2.1) on page 63 is well-deﬁned.

(b) Prove that logg(h1h2) = logg(h1) + logg(h2) for all h1, h2∈F∗

p.

(c) Prove that logg(hn) = nlogg(h) for all h∈F∗

pand n∈Z.

Solution to Exercise 2.3.

(a) We are given that ga≡gb(mod p), since they are both congruent

to h. Hence ga−b≡1 (mod p). But gis a primitive root, so its order is p−1,

which implies that p−1 divides a−b. Hence a≡b(mod p−1). This means

the logg(h) is well-deﬁned up to adding or subtracting multiples of p−1, so

the map (2.1) on page 63 is well-deﬁned.

(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 p−1.

(c) We have

gnlogg(h)=³glogg(h)´n≡hn≡glogg(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 2x≡13 (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 gm≡c2(mod p). Fermat’s little theorem (Theo-

rem 1.25) tells us that

cp−1≡1 (mod p).

However, cp−1(mod p) is also equal to

cp−1≡(c2)p−1

2≡(gm)p−1

2≡(g2k+1)p−1

2≡gk(p−1) ·gp−1

2(mod p).

Another application of Fermat’s little theorem tells us that

gk(p−1) ≡(gp−1)k≡1k≡1 (mod p),

so we ﬁnd that

gp−1

2≡1 (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. Diﬃe–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 Diﬃe–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 ﬁgure 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

ﬁnd that 2587 ≡974 (mod 1373), so Alice’s secret exponent is 587.

2.7. Let pbe a prime and let gbe an integer. The Diﬃe–Hellman Decision

Problem is as follows. Supoose that you are given three numbers A,B, and C,

and suppose that Aand Bare equal to

A≡ga(mod p) and B≡gb(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 diﬀerent

from the Diﬃe–Hellman problem described on page 67. The Diﬃe–Hellman

problem asks you to actually compute the value of gab.

(a) Prove that an algorithm that solves the Diﬃe–Hellman problem can be

used to solve the Diﬃe–Hellman decision problem.

(b) Do you think that the Diﬃe–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 Diﬃe–Hellman decision problem

without solving the Diﬃe–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

B≡2716 ≡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 A≡2299 ≡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 2b≡893 (mod 1373)

and using the value of bto decrypt the message.

Solution to Exercise 2.8.

(a) A≡2947 ≡177 (mod 1373), so Alice’s public key is A= 177 .

(b) c1≡2877 ≡719 (mod 1373) and c2≡583 ·469877 ≡623 (mod 1373).

Alice sends the ciphertext (c1, c2) = (719,623) to Bob.

(c) (ca

1)−1·c2≡(661299)−1·1325 ≡645−1·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 2b≡893 (mod 1373) is b= 219 , which is Bob’s private

key. It is now easy to decrypt,

(ca

1)−1·c2≡(693219)−1·793 ≡431−1·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 oﬀers to solve the Diﬃe–Hellman problem for

you. (See page 67 for a description of the Diﬃe–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 A≡ga(mod p) and

you know the ciphertext consisting of the two quantities c1≡gk(mod p) and

c2≡m·Ak(mod p), where kis Bob’s secret ephemeral key. You thus know

the values of gaand gk, so the Diﬃe–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·c2≡m(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 ﬁx 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 Diﬃe–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 ﬁxed. Alice choose a plain-

text mmod pand a random exponent asatisfying gcd(a, p −1) = 1. She send

u≡ma(mod p)

to Bob. Bob chooses a random exponent bsatisfying gcd(b, p −1) = 1, com-

putes

v≡ub(mod p),

and send vto Alice. Alice now computes the inverse of amodulo p−1, i.e.,

she solves ax ≡1 (mod p−1) for x. Let a0=a−1mod p−1. Alice computes

w≡va0(mod p)

and sends it to Bob. Finally, Bob computes the inverse b0=b−1(mod p−1)

and then wb0mod pis equal to m.

To see that this last assertion is true, we compute

wb0≡va0b0≡uba0b0≡maba0b0(mod p).

We know that

aa0≡1 (mod 1) (mod p−1) and bb0≡1 (mod 1) (mod p−1),

so the exponent aba0b0is congruent to 1 modulo p−1. Then Fermat’s little

theorem tells us that maba0b0≡m(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

w≡vx(mod p)

to recover x=a0, and then she can recover m, because

ua0≡maa0≡m(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 Diﬃe–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 diﬀerent

from στ.

2.12. Let Gbe a group, let d≥1 be an integer, and deﬁne a subset of Gby

G[d] = {g∈G:gd=e}.

(a) Prove that if gis in G[d], then g−1is 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

(h−1)n hn= (h−1 h−1··· h−1)(hh··· h) = e,

since there are ncopies of h−1to cancel the ncopies of h. Thus (h−1)nis the

inverse of hn, which we can write succintly as (h−1)n= (hn)−1. We apply this

with h=gand n=dand use the assumption that gd=eto conclude that

(g−1)d= (gd)−1=e−1=e.

Hence g−1is 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 g1g2∈G[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 ﬁrst

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

ﬁrst 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)σ=eσ =σ, which is not true.

An alternative solution is to use the group of 2-by-2 matrices with integer

coeﬃcients. The matrix A= ( 0 1

1 0 ) satisﬁes A2=Iand the matrix B=¡1−1

0−1¢

satisﬁes B2=I, but AB =¡1−1

0−1¢actually has order 3, i.e., (AB)3=I.

2.13. Let Gand Hbe groups. A function φ:G→His called a (group)

homomorphism if it satisﬁes

φ(g1 g2) = φ(g1) φ(g2) for all g1, g2∈G.

(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 g∈G. Prove that

φ(eG) = eHand φ(g−1) = φ(g)−1.

(b) Let Gbe a commutative group. Prove that the map φ:G→Gdeﬁned

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) = g−1.

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 φ:Z→Z/NZthat sends a∈Zto amod Nin Z/NZ.

(b) The map φ:R∗→GL2(R) deﬁned by φ(a) = ¡a0

0a−1¢.

(c) The discrete logarithm map logg:F∗

p→Z/(p−1)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 deﬁnition 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 1¶and µ1 0

1 1¶µ1 1

0 1¶=µ1 1

1 2¶.

(If p= 2, then 2 = 0, but they are still diﬀerent 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 ﬁrst row can be any vector except for

the 0 vector, so there are p2−1 possibilities for the ﬁrst row. The second row

Exercises for Chapter 2 49

can be any vector that is not a scalar multiple of the ﬁrst row. There are p

possible scalar multiples of the ﬁrst row, so there are p2−ppossibilities for

the second row. Hence

# GL2(Fp)=(p1−1)(p2−p) = (p−1)2p(p+ 1).

(e) Using the same reasoning as in (d), there are pn−1 allowable ﬁrst rows,

then pn−pallowable second rows, then pn−p2allowable third rows (since

we have to disallow all linear combinations of the ﬁrst two rows), etc. Hence

# GLn(Fp) =

n−1

Y

i=0

(pn−pi).

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 + 6x2−37x5=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=d√70 e= 9 and H=

h−N= 11−9= 7. From Table ?? we see that

111= 21 ·74= 11 in F71.

Hence

21 = 111·7−4= 111·(119)4= 1137 in F71,

so the solution is x=37 .

(b) The number 156 has order 148 in F593. Set N=d√148 e= 13 and

H=h−N= 156−13 = 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 11x≡21 (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 156x≡116 (mod 593) via babystep–giantstep

Hence

116 = 1567·297−4= 1567·(15613)4= 15659 in F593,

so the solution is x=59 .

(c) The number h= 650 has order 510 in F3571. Set N=d√510 e= 23 and

H=h−N= 650−23 = 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 = 650−23, we compute

2213 = 65020 ·1925−13 = 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 650x≡2213 (mod 3571) using babystep–giantstep

Exercises for Chapter 2 51

(a) x≡3 (mod 7) and x≡4 (mod 9).

(b) x≡137 (mod 423) and x≡87 (mod 191).

(c) x≡133 (mod 451) and x≡237 (mod 697).

(d) x≡5 (mod 9), x ≡6 (mod 10),and x≡7 (mod 11).

(e) x≡37 (mod 43), x ≡22 (mod 49),and x≡18 (mod 71).

Solution to Exercise 2.18.

(a) x≡31 (mod 63).

(b) x≡27209 (mod 80793).

(c) No solution, since gcd(451,697) = 41 and 133 and 237 are not congru-

ent to one another modulo 41.

(d) x≡986 (mod 990).

(e) x≡11733 (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 satisﬁes 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≡(b−a)·m−1(mod n).

Prove that x=a+cn is a solution to

x≡a(mod m) and x≡b(mod n),(2.1)

and that every solution to (2.24) has the form x=a+cn+ymn for some y∈Z.

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

c≡c0(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

mZ−−−−→ Z

m1Z×Z

m2Z×Z

mkZ

amod m−−−−→ (amod m1, a mod m2, . . . , a mod mk)

(2.2)

is a well-deﬁned homomorphism of rings. (Hint. First deﬁne 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 ﬁnd 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)2≡a(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 92≡3 (mod 13).

Solution to Exercise 2.24.

(a),(c),(d) A solution for this exercise is not currently available.

(b) (b+k·p)2≡a(mod p2) gives 1074k+ 223 ≡0 (mod p), and hence

k≡239 (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 x2≡a(mod n)

has any solutions, then it has four solutions.

(b) Suppose you had a machine that could ﬁnd 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 ﬁnite ﬁeld and let N|p−1. Prove that F∗

phas an element

of order N. This is true in particular for any prime power that divides p−1.

(Hint. Use the fact that F∗

phas a primitive root.)

Solution to Exercise 2.26.

Let gbe a primitive root. Then ghas order p−1, so h=g(p−1)/N has

order N.

2.27. Write out your own proof that the Pohlig–Hellman algorithm works in

the particular case that p−1 = 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.p−1 has a factor of 709.)

Solution to Exercise 2.28.

(a) Step 1 is to solve

q e h =g(p−1)/qeb=a(p−1)/qeywith hy=b

2 4 265 250 15

3 3 374 335 20

Step 2 is to solve

x≡15 (mod 24), x ≡20 (mod 33).

The solution is x=47 .

(b) Step 1 is to solve

q e h =g(p−1)/qeb=a(p−1)/qeywith hy=b

2 10 4168 38277 523

3 6 674719 322735 681

Step 2 is to solve

x≡523 (mod 210), x ≡681 (mod 36).

The solution is x=223755 .

(c) Step 1 is to solve

q e h =g(p−1)/qeb=a(p−1)/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·4−7¢293

= 8303208. The solution is u1= 8.

The value of uso far is u= 239 = 7 + 8 ·29.

Solve 18794375u2=¡11844727 ·4−239¢292

= 30789520. The solution is

u2= 26. The value of uso far is u= 22105 = 7 + 8 ·29 + 26 ·292.

Solve 18794375u3=¡11844727 ·4−22105¢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 ·4−461107¢290

= 585477. The solution is

u4= 18. The ﬁnal 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

x≡0 (mod 2), x ≡13192165 (mod 295).

The solution is x=33703314 .

(d) Step 1 is to solve

q e h =g(p−1)/qeb=a(p−1)/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

x≡0 (mod 2), x ≡322 (mod 709), x ≡534 (mod 911).

The solution is x=984414 .

Section. Rings, quotient rings, polynomial rings, and ﬁnite ﬁelds

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 ﬁnitely many elements.

Prove that Ris a ﬁeld. (Hint. Let a∈Rwith a6= 0. What can you say about

the map R→Rdeﬁned 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 a∈R.

(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 a∈R.

(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 b∈R.

(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 deﬁnition, b+ (−a) = 0. But we also know by

deﬁnition 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 = (iu)+(uu) = u+ (uu).

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 deﬁnition of divisibility.

(h) Let a∈Rand 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 abdepend 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 ﬁeld 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 a∈F[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 ﬁnd 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+ 3x4−5x3−3x2+ 2x+ 2,

b=x5+x4−2x3+ 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, ﬁnd

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 coeﬃcients

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 ﬁeld 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 ﬁeld 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 ﬁeld F2[x]/(x3+x+ 1)

2.38. The ﬁeld F7[x]/(x2+ 1) is a ﬁeld 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 u∈F49 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 suﬃces 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 e≥2. The quotient ring Z/peZand

the ﬁnite ﬁeld Fpeare both rings and both have the same number of elements.

Describe some ways in which they are intrinsically diﬀerent.

Solution to Exercise 2.39.

Every nonzero element in the ﬁeld 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 < pe−1. In the ﬁeld Fpe, if a product ab = 0,

then either a= 0 or b= 0. (To see this, note that if a6= 0, then a−1exists, so

multiplying ab = 0 by a−1shows that b= 0.) On the other hand, Z/(pe) does

not have this property. For example, p·pe−1= 0, but neither pnor pe−1is 0

in Z/(pe). A subtler property is that every element αof Fpesatisﬁes αpe=α,

but this is not true in Z/(pe). For example, if we take α=p, the αpe= 0.

2.40. Let Fbe a ﬁnite ﬁeld.

(a) Prove that there is an integer m≥1 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 ﬁeld 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 ﬁnite, the

numbers 1, 1 + 1, 1 + 1 + 1,. . . cannot all be diﬀerent.)

(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 ﬁeld.) This prime

is called the characteristic of the ﬁeld F.

(c) Let pbe the characteristic of F. Prove that Fis a ﬁnite-dimensional vector

space over the ﬁeld Fpof pelements.

(d) Use (c) to deduce that Fhas pdelements for some d≥1.

Solution to Exercise 2.40.

(a) The fact that Fis ﬁnite 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 ﬁeld, 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 deﬁned mto be the smallest number of 1’s that sums to 0, so either q≥

mor r≥m. 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 ﬁeld 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 ﬁnite since Fitself is ﬁnite. Hence F

is a ﬁnite-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, . . . , ad∈Fp.

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 19d≡1 (mod 96) has solution d≡91

(mod 96). Then x≡3691 ≡36 (mod 97).

(b) 541 is prime. The congruence 137d≡1 (mod 540) has solution d≡473

(mod 540). Then x≡428473 ≡213 (mod 541).

(c) 1159 = 19 ·61 and 18 ·60 = 1080. The congruence 73d≡1 (mod 1080)

has solution d≡577 (mod 1080). Then x≡614577 ≡158 (mod 1159).

More eﬃciently, g= gcd(18,60) = 6 and (18)(60)/6 = 180. The congruence

73d≡1 (mod 180) has solution d≡37 (mod 180). Then x≡61437 ≡158

(mod 1159).

(d) 8023 = 71 ·113 and 71 ·112 = 7840. The congruence 751d≡1

(mod 7840) has solution d≡7151 (mod 7840). Then x≡6777151 ≡1355

(mod 8023). More eﬃciently, g= gcd(70,112) = 14 and (70)(112)/14 = 560.

The congruence 751d≡1 (mod 560) has solution d≡431 (mod 560). Then

x≡677431 ≡1355 (mod 8023).

(e) 401227 = 607 ·661 and 608 ·660 = 399960. The congruence 38993d≡

1 (mod 399960) has the solution d≡265457 (mod 399960). Then x≡

61

62 Exercises for Chapter 3

328047265457 ≡36219 (mod 401227). More eﬃciently, g= gcd(606,660) = 6

and (606)(660)/6 = 66660. The congruence 38993d≡1 (mod 66660) has

the solution d≡65477 (mod 66660). Then x≡32804765477 ≡36219

(mod 401227).

3.2. Let pand qbe distinct primes and let eand dbe integers satisfying

de ≡1 (mod (p−1)(q−1)).

Suppose further that cis an integer with gcd(c, pq)>1. Prove that

x≡cd(mod pq) is a solution to the congruence xe≡c(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 x≡cd≡0 (mod p)

is a solution to xe≡c≡0 (mod p), so we only need to check that it is true

modulo q. We compute

(cd)e≡c1+k(p−1)(q−1) ≡c·(cq−1)k(p−1) ≡c(mod q),

since cq−1≡1 (mod q) from Fermat’s little theorem.

3.3. Recall from Section 1.3 that Euler’s phi function φ(N) is the function

deﬁned by

φ(N) = #{0≤k < N : gcd(k, N) = 1}.

In other words, φ(N) is the number of integers between 0 and N−1 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 pj−1, 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 µ1−1

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

xe≡c(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 µ1−1

7¶µ1−1

11¶µ1−1

19¶= 1080.

We compute d≡577−1≡73 (mod 1080), so

x≡6073 ≡1390 (mod 1463).

64 Exercises for Chapter 3

Check: 1390577 ≡60 (mod 1463). X

(ii) N= 53·13, so

φ(1625) = 1625 µ1−1

5¶µ1−1

13¶= 1200.

We compute d≡959−1≡239 (mod 1200), so

x≡1583239 ≡147 (mod 1625).

Check: 147959 ≡1583 (mod 1625). X

(iii) N= 23·32·5·72·112, so

φ(2134440) = 2134440 µ1−1

2¶µ1−1

3¶µ1−1

5¶µ1−1

7¶µ1−1

11¶

= 443520.

We compute d≡133957−1≡326413 (mod 443520), so

x≡224689326413 ≡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

103d≡1 (mod 2035800).

The solution is d≡810367 (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

m≡317730810367 ≡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

37d≡1 (mod 11952)

has solution d≡11629 (mod 11952). Then

m≡58711629 ≡4894 (mod 12191)

is a solution to m37 ≡587 (mod 12191).

It is possible to be a bit more eﬃcient, using the fact that g= gcd(72,166) =

2 and (72)(166)/2 = 5976. Thus a solution to the congruence

37d≡1 (mod 5976)

is a decryption exponent, giving the smaller decryption exponent d≡5653

(mod 5976). Of course, this gives the same plaintext

m≡5875653 ≡4894 (mod 12191).

3.8. For each of the given values of N=pq and (p−1)(q−1), use the method

described in Remark 3.10 to determine pand q.

(a) N=pq = 352717 and (p−1)(q−1) = 351520.

(b) N=pq = 77083921 and (p−1)(q−1) = 77066212.

(c) N=pq = 109404161 and (p−1)(q−1) = 109380612.

(d) N=pq = 172205490419 and (p−1)(q−1) = 172204660344.

Solution to Exercise 3.8.

(a) Suppose that N=pq = 352717 and (p−1)(q−1) = 351520. Then

p+q=N+ 1 −(p−1)(q−1) = 1198, so

X2−(p+q)X+N=X2−1198X+ 352717 = (X−677)(X−521).

Hence N= 352717 = 677 ·521.

(b) Suppose that N=pq = 77083921 and (p−1)(q−1) = 77066212. Then

p+q=N+ 1 −(p−1)(q−1) = 17710, so

X2−(p+q)X+N=X2−17710X+ 77083921 = (X−10007)(X−7703).

Hence N= 77083921 = 10007 ·7703.

(c) Suppose that N=pq = 109404161 and (p−1)(q−1) = 109380612. Then

p+q=N+ 1 −(p−1)(q−1) = 23550, so

66 Exercises for Chapter 3

X2−(p+q)X+N=X2−23550X+ 109404161 = (X−6367)(X−17183).

Hence N= 109404161 = 6367 ·17183.

(d) Suppose that N=pq = 172205490419 and (p−1)(q−1) = 172204660344.

Then p+q=N+ 1 −(p−1)(q−1) = 830076, so

X2−(p+q)X+N=X2−830076X+172205490419 = (X−407893)(X−422183).

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 ﬁxed modulus Nand for a large number of diﬀerent

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 aK≡a(mod N) for all asatisfying

gcd(a, N) = 1 are numbers satisfying

K≡1µmod (p−1)(q−1)

gcd(p−1, q −1)¶.

Thus diei−1 is a multiple of (p−1)(q−1)/gcd(p−1, q −1) for all 1 ≤i≤n.

Assuming that the ei’s are reasonably random, Eve will ﬁnd that

T= gcd(d1e1−1, d2e2−1, d3e3−1, . . . , dnen−1) (3.1)

Exercises for Chapter 3 67

is equal to a small multiple of

(p−1)(q−1)

gcd(p−1, q −1).

Next Eve uses the fact that gcd(p−1, q −1) is even and tends to be fairly

small. So she ﬁrst assumes that T= (p−1)(q−1)/2 and uses this to compute

R=N+ 1 −(p−1)(q−1) = N+ 1 −2T. If she is right about the value of T,

then Rwill equal p+q, and she can recover pand qby factoring x2−T x+N. If

this doesn’t work, she repeats the process with R=N+1−3T,R=N+1−4T,

etc. Continuing in this fashion, she should recover pand qfairly quickly.

Eve can save a bit of time in ﬁnding 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 ≈2√N, which

means that she should take k≈(N+ 1 −2√N)/T .

(b)

gcd(16784693 ·10988423 −1,11514115 ·25910155 −1)

= gcd(184437306609138,298332504337824)

= 19368558

First Eve tries N+ 1 −1·gcd = 19381152, but x2−19381152x+ 38749709

is irreducible. Next she tries N+ 1 −2·gcd = 12594, and this time she ﬁnds

that x2−12594x+ 38749709 = (x−7247)(x−5347). 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

x2−31574x+ 225022969 = (x−20707)(x−10867).

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

x2−110442x+ 1291233941 = (x−97151)(x−13291).

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 eﬃcient 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

g1≡gr1(p−1) (mod N) and g2≡gr2(q−1) (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 c2≡mgs2

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

x≡c1(mod p) and x≡c2(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

c1≡mgs1

1≡mgs1r1(p−1) ≡m(mod p)

by Fermat’s little theorem, and similarly c2≡m(mod q). Hence Alice’s

solutions satisﬁes x≡m(mod pq).

(b) As in (a), we observe that g1≡1 (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(g1−1, N) = p.

(If, by some rare coincidence, g1≡1 (mod q), then c1≡m(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 ﬁnding a factorization of N.

Solution to Exercise 3.12.

With notation as in Example 3.14, we ﬁnd that

u·c1+v·c2= 1

with

u= 252426389 and v=−496549570.

Then the plaintext is

m≡cu

1·cv

2≡1054592380 (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) n−1 = 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) n−1 = 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) n−1 = 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) n−1 = 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) n−1 = 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) n−1 = 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) n−1 = 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 ade−1≡1 (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

ar≡1 (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

ar≡1 (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 ar≡1 (mod p) and αr6≡ 1 (mod q),

then we recover pby computing

gcd(N, ar−1) = p.

Similarly, if ar6≡ 1 (mod p) and αr≡1 (mod q), then gcd(N, ar−1) = q, so

again we win. On the other hand, if ar≡1 (mod N), then we get no useful

information, so we need to go try a diﬀerent value for a.

In the remaining cases we have ar6≡ 1 (mod p) and αr6≡ 1 (mod q).

Suppose that iand jare diﬀerent, 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 ﬁnally, if i=j, then we get no useful information and need to try a

diﬀerent 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, ar−1). 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 p≡1 (mod 4)),

π3(X) = (# of primes pbetween 2 and Xsatisfying p≡3 (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 ﬁrst Xfor which the inequality is reversed is ex-

tremely large. In any case, the ratio satisﬁes 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 p≡a(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

2N≤n≤3

2N. If he repeats this process many times, prove

that approximately 1/ln(N) of his numbers will be prime. More precisely,

deﬁne

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

2N≤n≤3

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, ﬁx two numbers c1and c2satisfying c1< c2. Bob chooses

random numbers nin the interval c1N≤n≤c2N. Keeping c1and c2

ﬁxed, let

P(c1, c2;N) = "Probability that an integer nin the in-

terval c1N≤n≤c2Nis a prime num-

ber #.

76 Exercises for Chapter 3

In the following formula, ﬁll 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

=(c2−c1) ln(N) + O(1)

ln(c1N) ln(c2N)+oµ1

ln(N)¶

=c2−c1

ln(N)+oµ1

ln(N)¶

Hence P(N) divided by (c2−c1)/ln(N) goes to 1 as N→ ∞, or equivalently,

lim

N→∞

P(N)

ln(N)=c2−c1.

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 N≡1 (mod 3) has probability

3/(2 ln(N)) of being prime.

(c) A randomly chosen number Nsatisfying N≡1 (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

N≡k(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 N≡k(mod m) is prime is

approximately r

Y

i=1 µpi

pi−1¶·1

ln(N).

(e) More generally, for arbitrary mand ksatisfying gcd(m, k) = 1, the prob-

ability that N≡k(mod m) is prime is approximately

Y

p|mµp

p−1¶·1

ln(N).

This is often written as

Y

p|mµ1−1

p¶−1

·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 deﬁned 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 ≤t≤√Xand √X≤

t≤X, 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 p−1factorization algorithm

3.21. Use Pollard’s p−1 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 p−1 is a product of small primes.

Solution to Exercise 3.21.

(a)

23! −1≡63 (mod 1739) gcd(23! −1,1739) = 1

24! −1≡1082 (mod 1739) gcd(24! −1,1739) = 1

25! −1≡1394 (mod 1739) gcd(25! −1,1739) = 1

26! −1≡1443 (mod 1739) gcd(26! −1,1739) = 37

This give 1739 = 37 ·47. Note that p−1 = 36 = 22·32and q−1 = 46 = 2 ·23.

(b)

23! −1≡63 (mod 220459) gcd(23! −1,220459) = 1

24! −1≡22331 (mod 220459) gcd(24! −1,220459) = 1

25! −1≡85053 (mod 220459) gcd(25! −1,220459) = 1

26! −1≡4045 (mod 220459) gcd(26! −1,220459) = 1

27! −1≡43102 (mod 220459) gcd(27! −1,220459) = 1

28! −1≡179600 (mod 220459) gcd(28! −1,220459) = 449

This gives 220459 = 449 ·491. Note that p−1 = 448 = 26·7 and q−1 =

490 = 2 ·5·72.

(c)

215! −1≡46983890 (mod 48356747) gcd(215! −1,48356747) = 1

216! −1≡8398520 (mod 48356747) gcd(216! −1,48356747) = 1

217! −1≡9367159 (mod 48356747) gcd(217! −1,48356747) = 1

218! −1≡17907955 (mod 48356747) gcd(218! −1,48356747) = 1

219! −1≡13944672 (mod 48356747) gcd(219! −1,48356747) = 6917

This gives 48356747 = 6917 ·6991. Note that p−1 = 6916 = 22·7·13 ·19 and

q−1 = 6990 = 2 ·3·5·233.

3.22. A prime of the form 2n−1 is called a Mersenne prime.

(a) Factor each of the numbers 2n−1 for n= 2,3, . . . , 10. Which ones are

Mersenne primes?

(b) Find the ﬁrst seven Mersenne primes. (You may need a computer.)

(c) If nis even and n > 2, prove that 2n−1 is not prime.

(d) If 3 |nand n > 3, prove that 2n−1 is not prime.

(e) More generally, prove that if nis a composite number, then 2n−1 is not

prime. Thus all Mersenne primes have the form 2p−1 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 ﬁnd 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 2n−1 for 2 ≤n≤20 is

22−1=3=3

23−1=7=7

24−1 = 15 = 3 ·5

25−1 = 31 = 31

26−1 = 63 = 32·7

27−1 = 127 = 127

28−1 = 255 = 3 ·5·17

29−1 = 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 ﬁrst few Mersenne primes are

22−1=3,23−1 = 7,25−1 = 31,27−1 = 127,

213 −1 = 8191,217 −1 = 131071,219 −1 = 524287.

Notice that 2p−1 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 2n−1 = 22m−1 = (2m−1)(2m+ 1), so

2n−1 is composite unless 2m−1 = 1, i.e. unless m= 1 and n= 2.

80 Exercises for Chapter 3

(d) Similarly, 23m−1 = (2m−1)(22m+ 2m+ 1), so it is composite unless

m= 1.

(e) More generally,

2km −1 = (2m−1)(2(k−1)m+ 2(k−2)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

xk−1 = (x−1)(x(k−1) +x(k−2) +··· +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 diﬀerence 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 ﬁnd 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 = 2312−22= (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 = 1862−52= (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 = 1612−122= (161 + 12)(161 −12) = 173 ·149.

(d) Most people will give up before ﬁnishing 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 = 2832−1262= (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 = 59442−32= (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 = 19192−402= (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 = 72622−952= (7262 + 95)(7262 −95) = 7357 ·7167.

gcd(2510839,7357) = 1051,gcd(2510839,7167) = 2389

3.25. For each part, use the data provided to ﬁnd values of aand bsatisfying

a2≡b2(mod N), and then compute gcd(N, a −b) in order to ﬁnd a nontrivial

factor of N, as we did in Examples 3.36 and 3.37.

(a) N= 61063

18822≡270 (mod 61063) and 270 = 2 ·33·5

18982≡60750 (mod 61063) and 60750 = 2 ·35·53

(b) N= 52907

3992≡480 (mod 52907) and 480 = 25·3·5

7632≡192 (mod 52907) and 192 = 26·3

7732≡15552 (mod 52907) and 15552 = 26·35

9762≡250 (mod 52907) and 250 = 2 ·53

84 Exercises for Chapter 3

(c) N= 198103

11892≡27000 (mod 198103) and 27000 = 23·33·53

16052≡686 (mod 198103) and 686 = 2 ·73

23782≡108000 (mod 198103) and 108000 = 25·33·53

28152≡105 (mod 198103) and 105 = 3 ·5·7

(d) N= 2525891

15912≡5390 (mod 2525891) and 5390 = 2 ·5·72·11

31822≡21560 (mod 2525891) and 21560 = 23·5·72·11

47732≡48510 (mod 2525891) and 48510 = 2 ·32·5·72·11

52752≡40824 (mod 2525891) and 40824 = 23·36·7

54012≡1386000 (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 ﬁrst 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 Msatisﬁes pe≤B. 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 ﬁxed positive constants aand b, deﬁne 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

u−u=L(X)−1

2c(1+o(1)).

Solution to Exercise 3.31.

(a) is clear, any < 1

2will work.

(b) We ﬁrst 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 X−1

2ln ln ln X−ln c¸

=1

2c√ln 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 ≤k≤K.

(For simplicity, you may treat Kas a ﬁxed integer, independent of N. More

rigorously, it is necessary to take Kequal to a power of L(N), which has a

small eﬀect on the ﬁnal answer.)

(a) Prove that a2−N≤2K√N+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 ﬁxed r > 0.

(c) Re-prove Proposition 3.47 using this better choice of values for a. Set

B=L(N)cand ﬁnd 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 a2−N=

2(+k)√N+ (+k)2≤2K√N+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 ﬁrst 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