. 1
( 2)



>>

224 Solutions to Odd-Numbered Exercises 1.1“1.17



Solutions to Odd-Numbered Exercises

Section 1.1 (In the solutions, we will violate the convention of having plaintext in
lower case in order to increase readability due to the smaller font size we use herein.)

1.1 I THINK THEREFORE I AM
This is the phrase coined by the seventeenth century philosopher-mathematician
Ren´ Descartes, and may be said to be the signature of the basis of his reasoning.
e
It was originally given in Latin as: Cogito ergo sum.
1.3 BEHOLD THE SIGN
1.5 NON SEQUITUR
This is the Latin phrase for a conclusion that does not follow logically from the
premises.
1.7 TRUTH CONQUERS ALL THINGS
1.9 WAR IS IMMINENT
1.11 NEVER SAY ANYTHING
1.13 VANITY
1.15 Since

m = (01110011010010010011010000110000100011110000000011) =
(01110)(01101)(00100)(10011)(01000)
(01100)(00100)(01111)(00000)(00011),
then the decimal equivalents are

14, 13, 4, 19, 8, 12, 4, 15, 0, 3,

to which correspond the letters O, N, E, T, I, M, E, P, A, D, to give us the En-
glish plaintext:
ONE TIME PAD
1.17 Since k + c =

(11010111101111010101111011101011010) +

(10010100111110111011010011101101001) =
(01000011010001101110101000000110011) =
(01000)(01101)(00011)(01110)
(10100)(00001)(10011),
then the decimal equivalents are 8, 13, 3, 14, 20, 1, and 19. Hence, via Table
1.2, we get the English equivalents: I, N, D, O, U, B, T , to give us the English
plaintext:
IN DOUBT



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 1.19“1.47 225

1.19 Since k + c =

(11010111101111010101111011101011010) +

(11010100111110111110101011111001000) =
(00000011010001101011010000010010010) =
(00000)(01101)(00011)(01011)
(01000)(00100)(10010),
then the decimal equivalents are 0, 13, 3, 11, 8, 4, and 18. Hence, via Table
1.2, we get the English equivalents: A, N, D, L, I, E, S, to give us the English
plaintext: AND LIES

1.21 Since
k + c = (11010111101111010101111011101011010) +
(11111100000111110001010001111001011) =
(00101011101000100100101010010010001) =
(00101)(01110)(10001)(00100)
(10101)(00100)(10001),
then the decimal equivalents are 5, 14, 17, 4, 21, 4, and 17. Hence, via Table
1.2, we get the English equivalents: F, O, R, E, V, E, R, to give us the English
plaintext:
FOREVER
Section 1.2
1.23 SEARCH THE CAVES
1.25 BOMB THE CAMPS
1.27 SURROUND THE CITY
1.29 SHE CREATED A STATE
1.31 HE DESTROYED TOWNS
1.33 BOTH STRUGGLES END
1.35 FIND THE SECRET NOW
1.37 HAVE ANOTHER ONE
1.39 TRY TO REMEMBER
1.41 WHERE IS THE GOLD
Note that we discard the Z at the end since it was a ¬ller to make the last triplet.
1.43 SUMMERTIME
Note that we discard two copies of Z at the end since they were used as ¬ller to
make the last triplet.

1.45 LET™S ROLL
Note that the apostrophe is tacitly understood.
1.47 ALL EVIL DOERS FAIL



© 2003 by CRC Press LLC
226 Solutions to Odd-Numbered Exercises 1.49“1.65

1.49 TRUST HIM
1.51 SPLENDID
1.53 FORGED SIGNATURES
1.55 GOOD DEEDS PREVAIL
1.57 FILLED WITH REGRET
1.59 We use induction on n. If n = 2, then b2 > 2b1 > b1 , so S = {b1 , b2 } is a
superincreasing sequence. Assume that

S = {b1 , b2 , . . . , bn’1 },

which satis¬es
bj+1 > 2bj for 1 ¤ j ¤ n ’ 2
is a superincreasing sequence. Suppose that bn > 2bn’1 . Since S is a superin-
creasing sequence, then
n’2 n’1
bn > bn’1 + bn’1 > bn’1 + bj = bj .
j=1 j=1

Hence, by induction all such sets are superincreasing sequences.
Section 1.3
1.61 The key is MATH, and the plaintext is:

NEVER SAY NEVER AGAIN UNDER ANY
CIRCUMSTANCES WHATSOEVER
1.63 The key is FIX, and the plaintext is:

CRYPTOGRAPHERS MAKE VERY HIGH SALARIES
Note that we throw away two copies of Z tacked on the end as ¬ller to make up
the last trigram.
1.65 The key is FAIR, and the plaintext is:

JOHN NASH WAS A PIONEER OF GAME THEORY
Note that we throw away a Z tacked on the end as ¬ller to make up the last
trigram.S1
S1 John Forbes Nash (1928“) was born June 13, 1928 in Blue¬eld, West Virginia. He ¬rst
became interested in mathematics at the age of fourteen. He was inspired by Bell™s book Men
of Mathematics [18]. However, the mathematics that he learned at school bored him, and
coupled with his lack of social skills, caused his teachers to brand him as obtuse. In 1941,
Nash began the study of mathematics at Blue¬eld College where his mathematical talent
began to shine through to his educators. John won a Westinghouse scholarship and entered
Carnegie Tech (now Carnegie-Mellon University) in June 1945, where he intended to study
chemical engineering. Yet, his absorption into mathematics deepened, so he took courses in
tensor calculus and relativity, the latter being taught by the new head of department, John
Synge, who along with other professors in mathematics, saw Nash™s considerable talent and




© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 1.67“2.3 227

1.67 The key is GOLD, and the plaintext is:

ALL THAT GLITTERS IS NOT GOLD BUT
PLATINUM IS ALWAYS PRECIOUS
Note that we throw away a Z tacked on the end as ¬ller to make up the last
trigram.
Section 2.1
2.1 There are at most two solutions modulo a given prime. Thus, by the Chinese
Remainder Theorem there will be at most four modulo pq. We now exhibit
those four. We need only show that

±(xpa(q+1)/4 + yqa(p+1)/4 )
are square roots of a modulo pq since the other case has the same argument.
We have

(xpa(q+1)/4 + yqa(p+1)/4 )2 ≡ x2 p2 a(q+1)/2 + y 2 q 2 a(p+1)/2 ≡

x2 p2 z q+1 + y 2 q 2 z p+1 ≡ z 2 (x2 p2 z q’1 + y 2 q 2 z p’1 ) (mod n),
and since z p’1 ≡ 1 (mod p) and z q’1 ≡ 1 (mod q), then this is congruent to:

z 2 (x2 p2 + y 2 q 2 ) ≡ z 2 (xp + yq)2 ≡ z 2 ≡ a (mod n).

2.3 Alice selects m = 21 and sends w ≡ m2 ≡ 441 (mod n) to Bob. Bob selects c = 0
and sends it to Alice who computes r = 21, which gets sent back to Bob, who
computes r2 ≡ 441 ≡ w · tc (mod n). Thus we set a = 1 and execute another
A
round.
countenanced him to continue his mathematical journey. In 1948, he received a B.A. and an
M.A. in mathematics. In September 1948, he accepted a prestigious fellowship from Lefshetz,
head of the Mathematics Department at Princeton, to take up doctoral studies. During his
studies in 1949, he wrote a paper that would, forty-¬ve years later, earn him the Nobel prize
in economics. In 1950, he was granted his Ph.D. for a thesis called Non-Cooperative Games.
In the summer of that year, he was working for RAND Corporation, where he worked from
time to time over the later years. In 1952, he was teaching at MIT where he met Eleanor
Stier with whom he had a son on June 19, 1953. However, despite her persuasions, he did not
marry her. He did marry one of his students, Alicia Larde, in February 1957. By the end of
1958, with Alicia pregnant, he began a decline into schizophrenia. (The term Schizophrenia
was coined by Eugene Bleuler in 1908 to mean a “speci¬c type of alteration of thinking, feeling
and relation to the external world”.) An example of his descent into mental illness is given by
the following anecdote. One winter morning at MIT in 1959 he entered the lounge carrying
the New York Times and commented that the story in the upper left-hand corner of the
front page contained an enciphered message from extra-terrestrials, a message that only he
could decrypt. He saw hidden messages in everyday life that were symptoms of his delusions.
For decades, Nash was in and out of hospitals for treatment. Amazingly, his mathematical
output and academic success continued. By the early 1990s he had made a recovery from his
battle with the disease. In 1994, he won (jointly with Harsanyi and Selten) the Nobel Prize
in Economics for his research in game theory. By 1999, he was also honoured with the I. P.
Steele Prize by the American Mathematical Society for a “seminal contribution to research”.
For more on his life, the book: A Beautiful Mind [171] is recommended as is the movie of
the same name starring Russell Crowe who won a Golden Globe award on January 20, 2002,
for his penetrating portrayal of Nash™s life.



© 2003 by CRC Press LLC
228 Solutions to Odd-Numbered Exercises 2.3“2.23

Alice selects m = 12 and sends w = 144 to Bob. Bob selects c = 1, which Alice
subsequently uses to compute r ≡ 12 · 111 ≡ 1332 (mod n) and sends r to Bob,
who then B veri¬es that

r2 ≡ 757855 ≡ 144 · 12321 ≡ w · tc (mod n).
A

Since a is now set to zero, Bob accepts Alice™s proof.
Section 2.2
2.5 First, note that we have for each i = 0, 1, . . . , aj ’ 1,
aj ’1
(j)
b k pk
xi = (S1)
j
k=i

and
βi = ±xi ,
so
(p’1)/pi+1 i+1
≡ ±(p’1)xi /pj
j
βi (mod p).
Thus, it su¬ces to prove:
(j)
i+1
±(p’1)xi /pj ≡ ±(p’1)bi /pj
(mod p),

which holds precisely when
(j)
(p ’ 1)bi
(p ’ 1)xi
≡ (mod p ’ 1)
i+1
pj
pj

by Fermat™s Little Theorem. From (S1),
(j)
(p ’ 1)(xi ’ pi bi )
(j)
(p ’ 1)bi
(p ’ 1)xi j
’ = =
i+1 i+1
pj
pj pj
«  « 
aj ’1 aj ’1
p’1 
bk pk ’ bi pi  = (p ’ 1)  bk pk’i’1  ,
(j) (j) (j)
j j j
i+1
pj k=i k=i+1

which is congruent to 0 modulo p ’ 1.
2.7 log2 (19) ≡ 35 (mod 37).
2.9 log3 (31) ≡ 1176 (mod 1579).
2.11 log3 (7) ≡ 1227 (mod 1721).
2.13 log10 (3) ≡ 813 (mod 1783).
2.15 log14 (5) ≡ 718 (mod 1871).
2.17 log23 (3) ≡ 490 (mod 2161).
2.19 log13 (2) ≡ 1300 (mod 2351).
2.21 log19 (3) ≡ 1402 (mod 2689).
2.23 log22 (3) ≡ 2314 (mod 3361).




© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 2.25“3.11 229

Section 2.3
2.25 69.
2.27 91.
2.29 7.
2.31 First, we determine d, the deciphering key, by using the Euclidean algorithm to
solve 69d + 166x = 1, and d = 77, x = ’32 yields the least positive value of d, so
we decipher via 8577 ≡ 12 (mod 167), 5077 ≡ 4 (mod 167), 9677 ≡ 18 (mod 167),
077 ≡ 0 (mod 167), and 2777 ≡ 6 (mod 167). Thus, via Table 1.2, we get the
letter equivalents of 12, 4, 18, 18, 0, 6, 4 to be

MESSAGE.

2.33 As in Exercise 2.31, we determine that d = 1053 and decipher to get plaintext
numerical equivalents 8, 13, 19, 0, 2, 19, which decrypt to

INTACT.

2.35 k = 2245.
2.37 k = 2902.
2.39 k = 871.
2.41 k = 1876.
2.43 k = 571.
2.45 k = 637.
2.47 k = 2425.
Section 3.1
3.1 By solving 7d + 16600y = 1, where (p ’ 1)(q ’ 1) = 16600, we get that d = 4743
with y = ’2. Thus, x = 8081.
3.3 As in Exercise 3.1 above, 7d + 33820y = 1, yields d = 9663, y = ’2, and x = 723.
3.5 As above, 7d + 1082400y = 1, yields d = 773143, y = ’5, and x = 315043.
3.7 As above, 7d + 3706560y = 1, yields d = 2647543, y = ’5, and x = 168536.
3.9 As above, 5d + 4726896y = 1, yields d = 3781517, y = ’4, and x = 4598308.
3.11 Since ed ≡ 1 (mod (p ’ 1)(q ’ 1)), there exists a g ∈ Z such that

ed = 1 + g(p ’ 1)(q ’ 1).

If p x, then by Fermat™s Little Theorem, xp’1 ≡ 1 (mod p). Hence,

xed ≡ x1+g(p’1)(q’1) ≡ x(xg(q’1) )p’1 ≡ x (mod p). (S2)

If p x, then (S2) holds again since x ≡ 0 (mod p). Hence,

xed ≡ x (mod p)

for any x. Similarly, xed ≡ x (mod q). Since p = q, xed ≡ x (mod n). Thus,

(xe )d ≡ xed ≡ x (mod n).



© 2003 by CRC Press LLC
230 Solutions to Odd-Numbered Exercises 3.13“3.27

d
3.13 Since x ≡ c ≡ cd (y e )d ≡ xy (mod n), then Mallory computes

x ≡ x y ’1 (mod n).

Section 3.2
3.15 Let ∈ N be the least value such that n < N +1 . Such an must exist since
n ∈ N and N > 1. Moreover, is unique. If n < N , then this contradicts the
minimality of + 1 in this regard. Thus, N ¤ n < N +1 since n > N .
3.17 Let k > be chosen, so that N k ≥ N +1 > n, and suppose that we have a
plaintext message blocks m, m1 such that m > n. Then if

me ≡ me (mod n),
1

we get, upon decryption m ≡ med ≡ med ≡ m1 (mod n). Thus, there is a
1
nonnegative integer r such that m = m1 + nr. However, m > n, so r > 0.
Hence, the same ciphertext block c ≡ me ≡ me (mod n) will yield (at least) two
1
di¬erent plaintext messages, m and m ’ nr, only one of which will be correct.
As an illustration, if k = 3 = + 1 in Example 3.10, then POW has 3-digit
base 26 numerical equivalent 15 · 262 + 14 · 26 + 23 = 10526, which enciphers as
10526701 ≡ 1420 (mod 1943). However, deciphering yields

142029 ≡ 811 (mod 1943),

and of the values 811 + 1943j for j = 0, 1, 2, 3, 4, 5, only j = 5 yields 10526.
3.19 Using the solution of Exercise 3.14, we know that p = 3371 and q = 3449.
3.21 As in Exercise 3.19, we have p = 4651 and q = 5003.
3.23 As in Exercise 3.19, we have p = 5657 and q = 6397.
3.25 As in Exercise 3.19, we have p = 9203 and q = 9533.
3.27 We write the cryptogram as 5-digit base 26 integers since = 4:

EGSIO = 4 · 264 + 6 · 263 + 18 · 262 + 8 · 26 + 14 = 1945750,

XEWXG = 23 · 264 + 4 · 263 + 22 · 262 + 23 · 26 + 6 = 10596228,
and

DPXMA = 3 · 264 + 15 · 263 + 23 · 262 + 12 · 26 + 0 = 1650428.

Then determine the deciphering key via ed+φ(n)x = 11d+10758720 = 1, which
gives d = 1956131 (for x = ’2). Thus, deciphering:

1945750d ≡ 111414 (mod n), 10596228d ≡ 213617 (mod n),

and 1650428d ≡ 301506 (mod n).
Also, since
111414 = 6 · 263 + 8 · 262 + 21 · 26 + 4 = GIVE
213617 = 12 · 263 + 4 · 262 + 0 · 26 + 1 = MEAB,
301506 = 17 · 263 + 4 · 262 + 0 · 26 + 10 = REAK,
we have the plaintext: GIVE ME A BREAK.



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 3.29“3.39 231

3.29 As in Exercise 3.27, we write:

FENFL = 5 · 264 + 4 · 263 + 13 · 262 + 5 · 26 + 11 = 2364113,

PLNMZ = 15 · 264 + 11 · 263 + 13 · 262 + 12 · 26 + 25 = 7057101,
and

XLMPS = 23 · 264 + 11 · 263 + 12 · 262 + 15 · 26 + 18 = 10712304.

Thus, deciphering:

2364113d ≡ 2122640 (mod n), 7057101d ≡ 199958 (mod n),

and 10712304d ≡ 339408 (mod n),
and since,

2122640 = 4 · 263 + 16 · 262 + 20 · 26 + 0 = EQUA

199958 = 11 · 263 + 9 · 262 + 20 · 26 + 18 = LJUS,
339408 = 19 · 263 + 8 · 262 + 2 · 26 + 4 = TICE,
we have the plaintext: EQUAL JUSTICE.
3.31 As above:

BOTDT = 1 · 264 + 14 · 263 + 19 · 262 + 3 · 26 + 19 = 715981,

and
ICBYJ = 8 · 264 + 2 · 263 + 1 · 262 + 24 · 26 + 9 = 3692269,
and deciphering:

715981d ≡ 93634 (mod n), and 3692269d ≡ 321207 (mod n).

Then,
93634 = 5 · 263 + 8 · 262 + 13 · 26 + 8 = FINI
321207 = 18 · 263 + 7 · 262 + 4 · 26 + 3 = SHED,
so the plaintext is FINISHED.
Section 3.3
3.33 (±b )p’1’a = 32409’1’6 ≡ 379 (mod 409), and

(±b )’a m±ab ≡ 379 · 12 ≡ 49 = m (mod 409).

3.35 (±b )p’1’a = 512941’1’14 ≡ 864 (mod 941), and

(±b )’a m±ab ≡ 864 · 303 ≡ 194 = m (mod 941).

3.37 (±b )’a = (3, 3, 2)’44 = (1, 4, 1), so

±’ab m±ab = (1, 4, 1)(0, 2, 1) = (4, 4, 4) = m.

3.39 (±b )’a = (0, 3, 1)’24 = (1, 0, 0), so

±’ab m±ab = (1, 0, 0)(4, 0, 4) = (0, 1, 0) = m.



© 2003 by CRC Press LLC
232 Solutions to Odd-Numbered Exercises 3.41“3.59

3.41 Mallory intercepts meA and encrypts with his own enciphering key meA eM . Then
he sends it back to Alice, impersonating Bob. Alice, thinking it is Bob, sends
back meA eM dA = meM , which Mallory intercepts. He then easily decrypts via
his deciphering key to get meM dM = m. This demonstrates how easily the
system is compromised by such an attack and why it requires more security, in
terms of authentication of communicating entities, if it is to be used.
3.43 Bob has public key (p, ±, ±a ) = (15485863, 6, 7776), which Alice obtains. She
converts the English plaintext via Table 1.2 on page 3 to the numerical equiv-
alents: 19, 14, 3, 0, 24. Since 265 < p < 266 , she can represent the plaintext
message as a single 5-digit base 26 integer:

19 · 264 + 14 · 263 + 3 · 262 + 0 · 26 + 24 = 8930660.

She ¬rst computes ±b = 669 ≡ 13733130 (mod p), then

m±ab ≡ 8930660 · 777669 ≡ 4578170 (mod p).

She sends c = (13733130, 4578170) to Bob. He uses his private key to compute

(±b )p’1’a ≡ 137331301548585863’1’5 ≡ 2620662 (mod p)

and
(±b )’a m±ab ≡ 2620662 · 4578170 ≡ 8930660 ≡ m (mod p),
and using Table 1.2, he converts back to the English plaintext.
Section 3.4
3.45 Since each entity needs both the enciphering key and deciphering key to be kept
secret, this is “n choose 2”, namely, the binomial coe¬cient:

n
= n!/((n ’ 2)!2!) = n(n ’ 1)/2.
2

3.47 Since
(k )d ≡ 4019872802607 ≡ 234561 (mod n),
then k = (2, 3, 4, 5, 6, 1), from which we deduce that k’1 = (6, 1, 2, 3, 4, 5), so
k’1 (c) = (18, 8, 11, 21, 4, 17) = SILVER.
3.49 (k )d ≡ 1525853802607 ≡ 421653 (mod n), k = (4, 2, 1, 6, 5, 3), and k’1 =
(3, 2, 6, 1, 5, 4). Thus, k’1 (c) = (1, 0, 3, 9, 14, 1) = BAD JOB.
3.51 (k )d ≡ 7155548802607 ≡ 624315 (mod n), k = (6, 2, 4, 3, 1, 5), and k’1 =
(5, 2, 4, 3, 6, 1), so k’1 (c) = (5, 17, 8, 4, 13, 3) = FRIEND.
3.53 (k )d ≡ 371155802607 ≡ 214365 (mod n), k = (2, 1, 4, 3, 6, 5), and k’1 =
(2, 1, 4, 3, 6, 5), so k’1 (c) = (12, 14, 13, 8, 4, 18) = MONIES.
3.55 (k )d ≡ 8182887802607 ≡ 462135 (mod n), k = (4, 6, 2, 1, 3, 5), and k’1 =
(4, 3, 5, 1, 6, 2), so k’1 (c) = (0, 17, 0, 1, 8, 2) = ARABIC.
3.57 (k )d ≡ 4125753802607 ≡ 246351 (mod n), k = (2, 4, 6, 3, 5, 1), and k’1 =
(6, 1, 4, 2, 5, 3), so k’1 (c) = (7, 8, 19, 12, 0, 13) = HITMAN.
3.59 (k )d ≡ 1968543802607 ≡ 613245 (mod n), k = (6, 1, 3, 2, 4, 5), and k’1 =
(2, 4, 3, 5, 6, 1), so k’1 (c) = (3, 0, 17, 10, 4, 17) = DARKER.



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 3.61“4.9 233

3.61 (k )d ≡ 7066510802607 ≡ 415263 (mod n), k = (4, 1, 5, 2, 6, 3), and k’1 =
(2, 4, 6, 1, 3, 5), so k’1 (c) = (25, 4, 1, 17, 0, 18) = ZEBRAS.
Section 4.2
e
4.1 Let p|n be prime and set c = m(n’1)/q where q is a prime, e ∈ N and q e ||b. There-
e e’1
fore, since gcd(m(n’1)/q ’ 1, n) = 1, cq ≡ 1 (mod p), but cq ≡ 1 (mod p).
Thus, ordp (c) = q e , so q e (p ’ 1) by Proposition C.19. Since q was arbitrarily

chosen, p ≡ 1 (mod b). For the last assertion of the exercise, assume b > n ’

1, but n is composite. Let p be the smallest prime dividing n. Then p ¤ n, so
√ √
n ≥ p > b ≥ n, a contradiction. Hence, n is prime.
4.3 If n is prime, then by Exercise 4.1 we have the result with m = mq for all q (n’1).
Conversely, if such mq exist, then by the Chinese Remainder Theorem, we may
¬nd a solution x = m to the system of congruences

x ≡ mq (mod q e )

for all primes q such that q e ||(n ’ 1). Thus, the result now follows from Exercise
4.1.
4.5 If Fn is prime, the result follows from Exercise 4.4. Conversely, if p be a prime
Fn ’1 Fn ’1
≡ ’1 (mod p), so 3 2 ≡ ’1 (mod p). If b =
divisor of Fn , then 3 2
ordp (3), then b (Fn ’ 1) by Proposition C.19. Thus b = 2m for some integer
m with 1 ¤ m ¤ 2n . Suppose that m = 2n . Then
2n ’1 2n ’m’1
m
’1 ≡ 32 = (32 )2 ≡ 1 (mod p),

so p = 2, a contradiction. Hence,
n
ordp (3) = 22 = Fn ’ 1.

By Fermat™s Little Theorem and Proposition C.19, ordp (3)|p’1. Hence, p = Fn .
4.7 Assume ¬rst that (pj ’ 1) (n ’ 1) for all j = 1, 2, . . . , r. If gcd(a, n) = 1, then
gcd(a, pj ) = 1 for all j = 1, 2, . . . , r. Thus, apj ’1 ≡ 1 (mod pj ), by Fermat™s
Little Theorem. Since n ’ 1 = mj (pj ’ 1) for some mj ∈ N,

an’1 ≡ amj (pj ’1) ≡ (apj ’1 )mj ≡ 1 (mod pj ).
r
Hence, an’1 ≡ 1 (mod namely, an’1 ≡ 1 (mod n).
j=1 pj ),
≡ 1 (mod n) for each a with gcd(a, n) = 1. In
n’1
Conversely, suppose that a
particular, if a is a primitive root modulo p, for any prime divisor p of n, then
(p ’ 1) (n ’ 1), by Proposition C.19 on page 216.

Section 4.3
4.9 If b2 ≡ 1 (mod pa ), then pa (b + 1)(b ’ 1). Notice that p cannot divide both
(b’1) and b+1 since that would mean b’1 ≡ b+1 (mod p). so ’1 ≡ 1 (mod p),
forcing p = 2, a contradiction. Thus, either pa (b ’ 1) or pa (b + 1). In other
words, b ≡ ±1 (mod pa ). Conversely, if b ≡ ±1 (mod pa ), then b2 ≡ 1 (mod pa ).



© 2003 by CRC Press LLC
234 Solutions to Odd-Numbered Exercises 4.11“4.27

4.11 They are both Carmichael numbers for the following reasons, using Exercise 4.7.
For n = 8911 = 7 · 19 · 67, each of 6, 18 and 66 divide n ’ 1. For n = 10585 =
5 · 29 · 73, all of 4, 28, and 72 divide n ’ 1. Also, 10585 is an Euler pseudoprime
to base 2 since
2
≡ 25292 (mod 10585).
10585
4.13 By Exercise 4.8, E(n) is a subgroup of (Z/nZ)— . Since the cardinality of (Z/nZ)—
is φ(n) by Example C.17, and since n is composite, then E(n) = (Z/nZ)— by
Exercise 4.12, so E(n) is a proper subgroup of (Z/nZ)— . Thus, by Example
C.17, |E(n)| φ(n). Hence, |E(n)| ¤ φ(n)/2 since |E(n)| = φ(n) and φ(n) is
even when n > 2.
4.15 Since, by repeated squaring, we get 214670 ≡ ’1 (mod 29341) and ( 29341 ) = ’1,
2

then 29341 is an Euler pseudoprime to base 2 since 29341 = 13 · 37 · 61.
4.17 As above, we get, 231372 ≡ 1 ≡ ( 62745 ) (mod 62745), and since 62745 = 3 · 5 ·
2

47 · 89, then 62745 is an Euler pseudoprime to base 2.
4.19 Let n = 2821. Then by the repeated squaring method, we determine that
31410 ≡ 1 ≡ ( 2821 ) (mod 2821). Since 2821 = 7 · 13 · 31, then 2821 is an Euler
3

pseudoprime to base 3. Moreover, since 6, 12, and 30 all divide n ’ 1 = 2820,
then by Exercise 4.7, 2821 is a Carmichael number.
Section 4.4
4.21 If n ∈ spsp(a), then ad ≡ 1 (mod n) for some divisor d of n ’ 1. Thus,
(ad )(n’1)/d ≡ 1(n’1)/d ≡ 1 (mod n), whence n ∈ psp(a).
4.23 Let g = gcd((x ’ y), n). We need only show that g = 1, n. If g = 1, then
since n (x ’ y)(x + y), we must have n (x + y), contradicting the hypothesis
that x ≡ ’y (mod n). If g = n, then x ≡ y (mod n), a contradiction to the
hypothesis that x ≡ y (mod n). Hence, since g n, it is a nontrivial factor of it.
4.25 Each is a strong pseudoprime to base 2 for the following reasons. For n = 15841,
n ’ 1 = 25 · 495 and 2495 ≡ 1 (mod n). For n = 29341, n ’ 1 = 22 · 7335 and
22·7335 ≡ ’1 (mod n), while 27335 ≡ ±1 (mod n). For n = 52633, n ’ 1 = 23 ·
6579 and 26579 ≡ 1 (mod n). For n = 252601, n ’ 1 = 23 · 31575, and we have
both 22·31575 ≡ ’1 (mod n) and 231575 ≡ ±1 (mod n).
They are all Carmichael numbers for the following reasons, using Exercise 4.7.
For n = 15841 = 7 · 31 · 73, all of 6, 30, and 72 divide n ’ 1. For n = 29341 =
13 · 67 · 61, all of 12, 66, and 60 divide n ’ 1. For n = 52633 = 7 · 73 · 103, all
of 6, 72, and 102 divide n ’ 1. For n = 252601 = 41 · 61 · 101, all of 40, 60, and
100 divide n ’ 1.
4.27 Let n be a Carmichael number that is a strong pseudoprime to every base a
prime to n. Furthermore, suppose that n ’ 1 = 2t m where t ∈ N and m is odd.
Let a be a primitive root modulo any prime p dividing n. If am ≡ 1 (mod n),
then am ≡ 1 (mod p). However, since a is a primitive root modulo p, then by
Proposition C.19, (p ’ 1) m, a contradiction. Suppose that there exists a
j j+1
value of j such that 0 ¤ j ¤ t ’ 1, and a2 ≡ ’1 (mod n). Then a2 ≡1
m m

(mod p), so (p ’ 1) (2j+1 m) as above. Thus,
j j+1 j+1
’1 ≡ a2 m
≡ (a(p’1)/2 )(2 m)/(p’1)
≡ (’1)2 m
≡ 1 (mod p),



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 4.27“5.5 235

a contradiction since p is odd. Hence, no such Carmichael number can exist.
4.29 For a = 2 we have n ’ 1 = 24 · 35; 235 ≡ 263 (mod 561); 22·35 ≡ 166 (mod 561);
24·35 ≡ 67 (mod 561); and 28·35 ≡ 1 (mod 561). Hence, 561 is composite by the
strong pseudoprimality test.
4.31 Since 120 = 23 · 15 and 315 ≡ 1 (mod 121), then 121 is a strong pseudoprime to
base 3.
4.33 Since 24 = 23 · 3; 73 ≡ 18 (mod 25); and 182 ≡ ’1 (mod 25), then 25 is a strong
pseudoprime to base 7.
4.35 Since a(n’1)/2 ≡ ( n ) (mod n), then an’1 ≡ 1 (mod n).
a


4.37 If n = pb ∈ psp(a), and n ’ 1 = 2t m where m is odd, then

(a(n’1)/2 )2 ≡ 1 (mod n),

so by Exercise 4.9, a(n’1)/2 ≡ ±1 (mod n). If a(n’1)/2 ≡ 1 (mod n), and n ’ 1
is even we repeat the above argument to get a(n’1)/4 ≡ ±1 (mod n) and keep
repeating it which ultimately achieves that n ∈ spsp(a). The converse follows
from Exercise 4.21.
Section 5.1
a
5.1 We use induction on a to show that x2 ≡ 1 (mod 2a+2 ) for all odd x ∈ Z. If
a = 1, then it is easy to see that x2 ≡ 1 (mod 8), so we may assume that
a’1
x2 ≡ 1 (mod 2a+1 ).
a
Therefore, x2 = (1 + 2a+1 t)2 for some t ∈ Z. In other words,
a
x2 ≡ 1 (mod 2a+2 ).
a
5.3 Let n = r pj j be a prime factorization of n, with p1 = 2. By Exercise 5.2,
j=1
»(n) is a universal exponent for n. We must prove that it is minimal. Let gj be
a
a primitive root modulo pj j for each j = 2, 3, . . . , r, which exist by the Primitive
Root Theorem C.21 on page 216. Thus, by the Chinese Remainder Theorem
C.13, the system of congruences
a
x ≡ 3 (mod 2a1 ), and x ≡ gj (mod pj j ), (2 ¤ j ¤ r),

has a solution x = a which is unique modulo n. If am ≡ 1 (mod n) for some
a
m ∈ N, then am ≡ 1 (mod pj j ) for each j, so ordpaj (a) m, by Proposition C.19.
j
a
Thus, since a satis¬es the r congruences above, then »(pj j ) = ordpaj (a). Hence,
j
a
»(pj j ) m for all j. Therefore, »(n) m. We have shown that »(n) = ordn (a).

5.5 We have e = 25 · 405. Choose a = 2 and compute 2405 ≡ 1 (mod n), so we go to
step (1) and choose another base, a = 3. We compute

x0 ≡ 3405 ≡ 2820 (mod n),

then x1 ≡ 28202 ≡ 218 (mod n), and x2 ≡ 2182 ≡ 1 (mod n). Since we know
that x1 ≡ ±1 (mod n), then gcd(217, 15841) = 217 is a factor of n. Indeed
n = 217 · 73.



© 2003 by CRC Press LLC
236 Solutions to Odd-Numbered Exercises 5.7“5.19

5.7 Since e = 22 · 26643, we may try a = 2 and compute,

x0 ≡ 226643 ≡ 25719 ≡ ±1 (mod n),

then x1 ≡ 257192 ≡ 1 (mod n). Hence, gcd(25718, 107381) = 167 is a factor of
n. In fact, n = 167 · 643.
5.9 Since e = 23 · 1831595, then we choose a base a = 3 and compute as follows where
all congruences are assumed modulo n.

x0 ≡ 31831595 ≡ 10750120; x1 ≡ 107501202 ≡ 13251402;

and x2 ≡ 132514022 ≡ 1. Since x1 ≡ ±1, then gcd(n, 13251401) = 3371, and
n = 3371 · 4349.
5.11 Since e = 2 · 223713, then we choose a = 2 and compute the following where all
congruences ae modulo n. Since 2223713 ≡ 1, we need a new base. We select
a = 3 and compute

x0 ≡ 3223713 ≡ 23944214; x1 ≡ 239442142 ≡ 1,

and since x0 ≡ ±1, then gcd(x0 ’ 1, n) = 7103 n. Indeed n = 6679 · 7103.

5.13 We have that e = 23 · 1600875 and we select a = 2 to compute the following
where all congruences are modulo n. Since x0 ≡ 21600875 ≡ 76859538 ≡ ’1, we
must choose a new base a = 3.Then

31600875 ≡ 44940756; x1 ≡ x2 ≡ 9649071; x2 ≡ x2 ≡ 1;
0 1


and since x1 ≡ ±1, then gcd(x1 ’ 1, n) = 8539 n, and n = 8539 · 9001.
5.15 Since 3 is a primitive root of F6 = 18446744073709551617 if n is prime,
then we know that 3e/2 ≡ ’1 (mod n) if indeed it is prime. By repeated
squaring, we calculate that 3e/2 ≡ 3653528722731049759 ≡ ±1 (mod n), so
gcd(3653528722731049758, n) = 274177 n. Indeed we now have factored the
sixth Fermat number since

F6 = 274177 · 67280421310721.

Section 5.2
5.17 We check that gcd(aj ’ 1, n) = 1 for all j = 1, 2, . . . , 6, then

a7 ≡ 86977 ≡ 4747 (mod n),

gcd(4746, n) = 113, and n = 113 · 107. Note that 112 = 24 · 7 is B-smooth.
5.19 We compute that gcd(aj ’ 1, n) = 1 for j = 1, 2, . . . , 7. Then we check that

a8 ≡ 324948 ≡ 12320 (mod n),

gcd(12319, 37151) = 97, and n = 97 · 383. Here 96 = 25 · 3 is B-smooth.




© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 5.21“5.23 237

5.21 Randomly select a1 = 614, then

b1 ≡ 6142 ≡ 840 ≡ 23 · 3 · 5 · 7 (mod n),

so b1 is 7-smooth, and we keep it. Randomly select a2 = 51 and compute
512 ≡ 2601 (mod n), which is not 7-smooth since it is divisible by only 3 from
S4 and is not a perfect power of 3, so we discard it. Randomly select a2 = 1009
and compute
b2 ≡ 10092 ≡ 2 · 3 · 53 (mod n),
which is then saved. Randomly select a3 = 45 and compute

b3 ≡ 452 ≡ 34 · 52 (mod n),

which is saved. Randomly select a4 = 56 and compute

b4 ≡ 562 ≡ 26 · 72 (mod n),

and it is kept. Randomly select a5 = 100 and compute 1002 ≡ 1451 (mod n),
which is not divisible by any of the primes in S4 so it is discarded. Randomly
select a5 = 983 and compute

b5 ≡ 9832 ≡ 22 · 32 · 7 (mod n),

and save it. We have reached r + 1 = 5 such bi , so we now search for the subset
T. Notice that b3 and b4 are squares themselves. However, for b3 , x = 45,
y = 32 · 5 and x ’ y = 0. Similarly for b4 , the same thing happens, so we need
another subset. We see that if we choose T = {1, 2, 5}, then we get

bi ≡ 6142 · 10092 · 9832 ≡ 26 · 34 · 54 · 72 (mod n).
i∈T

Thus,
x≡ ai ≡ 614 · 1009 · 983 ≡ 6043 (mod n),
i∈T

and
y ≡ 23 · 32 · 52 · 7 ≡ 4051 (mod n).
Thus x2 ≡ y 2 (mod n) and

gcd(x ’ y, n) = gcd(6043 ’ 4051, 8549) = gcd(1992, 8549) = 83.

In fact, 8549 = 83 · 103. Of course, sometimes luck plays a role. Suppose that
the ¬rst random choice that we made was a1 = 744. Then since

7442 ≡ 28 · 52 (mod n)

and gcd(744 ’ 24 · 5, n) = gcd(664, 8549) = 83, then we have a quick and simple
factorization. However, one cannot rely on luck alone, and this is unlikely to
happen for the large numbers that are used in practice.
Section 5.3
5.23 6P = (2238, 2448)




© 2003 by CRC Press LLC
238 Solutions to Odd-Numbered Exercises 5.25“6.1

5.25 Since each point jP = (xj , yj ) on E(Z/nZ) has at most n2 possibilities for any
j, then there exists a value k such that jP = kP .
5.27 Let = qk + s where 0 ¤ s < k. Since kP = o, then qkP = o. Therefore, by
Exercise 5.26, ( ’ qk)P = sP = o. However, since s < k and k is the least
positive such value, then s = 0, and we have proved that k .
5.29 2P ≡ (9’1 , ’82 · 27’1 ) ≡ (442, 2501) (mod n). However, to compute 6P we
must compute 4P ≡ (’26567/242064, 352876013/119095488) ≡ o (mod n) since
gcd(242064, 3977) = 41, and indeed 3977 = 41 · 97.
5.31 2P ≡ (4055, 10810) (mod n) and 4P ≡ (363, 16880) (mod n), but
18984764783665 82719639550389910598
6P ≡ ≡ o (mod n)
,
25724631321 4125947892943869
since gcd(25724631321, 18247) = 71, and 18247 = 71 · 257.
5.33 We compute that 2P ≡ (4268, 11378) (mod n) and 4P ≡ (9877, 27743) (mod n),
but 6P is as in Exercise 5.31 and gcd((25724631321, 38411) = 71. We have
factored n = 38411 = 71 · 541.
Section 5.4
5.35 Since (a) holds, then
√ √ √
k
2(1/2k) i=1 (1/k)
k
2n 2n 2n
2
a≈ = = ,
M M M
i=1

so the ¬rst condition is satis¬ed in (5.11). Since b2 ≡ n (mod a2 ) given the
solution to the system of congruences via the Chinese Remainder Theorem,
then a2 (b2 ’ n), so (b2 ’ n)/a2 = c ∈ Z, which is the second condition. If
b ≥ a2 /2, then replace b by b ’ a2 , and we have |b| < a2 /2, which is the last
condition.
For the choices given, we set a = 11 · 17 = 187, and compute b1 = 23 since
232 ≡ n (mod 112 ) and b2 = 79 since 792 ≡ n (mod 172 ). Then we use the
Chinese Remainder Theorem to solve b ≡ 23 (mod 112 ) and b ≡ 79 (mod 172 )
for b = 11639. Since b2 ≡ 31384 ≡ n (mod a2 ), then c = (b2 ’ n)/a2 = 1802.
Section 6.1
r r
6.1 Let m1 = si /r and m2 = j=1 tj /r. First we observe that,
i=1

r r r
1
var({si }r ) 2
s2 + m2 =
(si ’ m1 ) /r = ’ 2m1
= si
i=1 i 1
r
i=1 i=1 i=1

r r r r r r
1 1 1
s2 s2 s2 ’m2 ,
’ 2m1 ’ m1
si + m1 si = si =
i i i 1
r r r
i=1 i=1 i=1 i=1 i=1 i=1
var({tj }r ) var({si }i=1 +{tj }j=1 ).
r r
and a similar result holds for and for There-
j=1
fore, if we let
r r r r
1 1
m= 2 (si + tj ) = 2 r si + r tj = m1 + m2 ,
r r
i=1 j=1 i=1 j=1




© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 6.1“6.13 239

then
r r
1
var({si }r {tj }r ) (si + tj )2 ’ (m1 + m2 )2 =
+ =2
i=1 j=1
r i=1 j=1

r r r
1
s2 r t2 ’ (m1 + m2 )2 =
+ 2si tj +
i j
r2 i=1 j=1 j=1
r r r r
1 1 2
s2 t2 tj ’ m2 ’ m2 ’ 2m1 m2 =
+ +2 si
i j 1 2
r r r
i=1 j=1 i=1 j=1
r r
1 1
s2 ’ m2 + t2 ’ m2 = var({si }r ) + var({tj }r ).
i 1 j 2 i=1 j=1
r r
i=1 j=1

Also, var({si }r ) = 0 = var({si }r ) for {si }ri=1 = {4, 4, 4, 4, }, since
i=1 i=1
m = 4, and for {tj }r = {5, 10, 50, 100}, var({tj }r ) = 23275/16 and
j=1 j=1

var({tj }r ) = 38.14.
j=1


Section 6.2
6.3 Using the Chinese remainder theorem, there is a solution to x ≡ ci ≡ m3 (mod ni )
for each i = 1, 2, 3. Since m3 < n1 n2 n3 , then x = m3 . By computing the cube
root of the integer x, we retrieve m.
6.5 We solve 1 = ed + φ(n)x = 5d + 5903364x and get d = 1180673 for x = ’1.
6.7 As above, we solve 1 = ed + φ(n)x = 3d + 20734288x and get d = 13822859 for
x = ’2.
6.9 As above, we solve 1 = ed + φ(n)x = 3d + 56579188x and get d = 37719459 for
x = ’2.
6.11 Since d < φ(n), and 0 < m ¤ e, then Eve can multiply ed ’ m(n ’ p ’ q + 1) = 1
by p and reduce modulo 2n/4 to get

(ed)p ’ mp(n ’ p + 1) + mn ≡ p (mod 2n/4 ),

which may be rewrite as

mnp2 ’ (mn + m + 1 + ed)p + mn ≡ 0 (mod 2n/4 ).

Since Eve knows n/4 of the least signi¬cant bits of d, she knows ed modulo 2n/4 .
Now Eve can try each of the possible values of p and use Theorem 6.8 to test
each one. Hence, after at most e log2 e trials, she has factored n.
Section 6.3
6.13 By Exercise 5.2 on page 95, a»(n)+1 ≡ a (mod n) for all a prime to n. If p n,
then we need only show that p divides a»(n)+1 ’ a for each prime dividing n
since n is squarefree. However, a»(n)+1 ≡ a ≡ 0 (mod p) for each such a. This
completes the proof. However, if n is not squarefree, then this does not hold in
general. For instance, if n = 12, then »(12) = 2 and

10»(12)+1 ≡ 103 ≡ 4 ≡ 10 (mod 12).



© 2003 by CRC Press LLC
240 Solutions to Odd-Numbered Exercises 6.15“7.9

6.15 Since modular exponentiation is computationally easy using, for instance, the
repeated squaring method, but ¬nding f ’1 (y) ≡ y d (mod n) is computationally
infeasible without knowledge of d, then this is a one-way, trapdoor function with
d as the trapdoor. See the discussion in Section 5.1, especially the discussion at
the bottom of page 94.
6.17 Use the extended Euclidean algorithm C.5 on page 213 on e and 2n to ¬nd
integers d and m such that ed + 2n m = 1. Then destroy all records of p, q,
n , and m , and keep d as the private key (trapdoor). Thus, me ≡ c (mod n) is
the enciphering function and cd ≡ m (mod n) is the deciphering function where
ed ≡ 1 (mod φ(n)).
Section 6.4
6.19 We have that n = 2AB + 1 = 307 and mn’1 ≡ 2306 ≡ 1 (mod n) and
gcd(m(n’1)/p , n) = gcd(218 ’ 1, 307) = 1, so 307 is a provable prime and since
307 = (100110011)2 , it is a 9-bit prime.
6.21 Since n = 2AB + 1 = 2311, and 22310 ≡ 1 (mod n) with gcd(2462 ’ 1, n) = 1,
then 2311 is a provable prime and 2311 = (100100000111)2 , which is 12 bits so
we are done.
6.23 (a) Since f : (Z/nZ)— ’ (Z/nZ)— , then there are only ¬nitely many possibilities
for sa , so eventually sa+1 ≡ sj for some j ¤ .
j’1
(b) f (2) = (8, 512, 161, 2), so = 4 which is the answer to (c).
Section 7.1
7.1 Alice is identi¬ed since,

δ ≡ ±y v r ≡ ±k+er v r ≡ ±k+er ±’er ≡ ±k ≡ γ (mod p).

7.3 Alice computes y ≡ k + er ≡ 1001 + 151 · 512 (mod 1559), and Bob computes

δ ≡ ±y v r ≡ 49363 · 460512 ≡ 502 ≡ γ ≡ 501 (mod 3119),

so Bob rejects Alice™s proof of identity.
7.5 As above, y ≡ 4 + 8 · 3 ≡ 11 (mod 17), and

δ ≡ 366811 · 45083 ≡ 4104 ≡ γ (mod 7481),

so Bob accepts Alice™s proof of identity.
7.7 In step (9), Bob must verify Trent™s signature. However, since v = v then s = s,
so verT (k) ((IA , v , s )) = 0, and Bob rejects the proof of identity.
7.9 Alice computes
y1 ≡ k1 + e1 r ≡ 10 + 25 · 8 ≡ 1 (mod q)
y2 ≡ k2 + e2 r ≡ 9 + 27 · 8 ≡ 5 (mod q),
and sends them to Bob who computes

δ ≡ ±11 · ±22 · v r ≡ 4431 · 25415 · 17688 ≡ 2490 ≡ γ (mod p),
y y


so he accepts Alice™s proof of identity.



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 7.11“7.35 241

7.11 As above,
y1 ≡ 1007 + 998 · 256 ≡ 1144 (mod q)
y2 ≡ 506 + 5 · 256 ≡ 1786 (mod q).
Then Bob computes,

δ ≡ 251144 · 11331786 · 771256 ≡ 3009 ≡ γ (mod p),

so Bob rejects Alice™s proof of identity.


Section 7.2
7.13 Since sigk (m)e ≡ 15971133 ≡ 911 ≡ m (mod 20497), then Bob accepts Alice™s
signature.
7.15 Since sigk (m)e ≡ 317905611 ≡ 116106 ≡ 1111 ≡ m (mod 58320), then Bob
rejects Alice™s signature.
7.17 We have, sd z ’1 ≡ z ed md z ’1 ≡ zmd z ’1 ≡ md (mod n), since ed ≡ 1 (mod φ(n)).
Alice does not know if she is signing away her life savings or confessing to a
murder she did not commit. Hence, for her to sign blindly requires safeguards.
7.19 δ ≡ y β β γ ≡ 11227 227207 ≡ 25 (mod p) and σ ≡ ±m ≡ 52 ≡ 25 (mod p), so it is
accepted.
7.21 As above, δ ≡ 711330 33037 ≡ 495 (mod p), and σ ≡ 11191 ≡ 495, so it is accepted.
7.23 We have,
’1
y β1 β1 1 ≡ ±aβ1 ±(r1 +ar2 )γ1 ≡ ±aβ1 ±(r1 +ar2 )(’β1 r2
γ )

’1 ’1
±aβ1 ±’β1 r1 r2 ’β1 a
≡ ±’β1 r1 r2 ≡ ±γ1 r1 ≡ ±m1 (mod p).
7.25 Since β, γ, and m are known, then knowledge of r means that he may compute
a ≡ (m ’ rγ)β ’1 (mod p ’ 1).
7.27 When Alice sends her valid signature to Bob, we have:

δ ≡ ±γ y h ≡ ±r+eh ±’eh ≡ ±r ≡ β (mod p).

7.29 Bob computes δ ≡ ±γ · y h ≡ 12206 · 1456101 ≡ 913 ≡ β (mod p), so he accepts
Alice™s signature.
7.31 As above, Bob computes δ ≡ 107925 · 42721 ≡ 1217 ≡ β (mod p), so he accepts.
Section 7.3
7.33 Since we have that A is unique to Alice and

f Ak ≡ g11 g22 (g11 g22 )k ≡ g11 +ke1 g22 +ke2 ≡ g11 g22 (mod p),
f f e e f f


then Alice™s identity is indeed veri¬ed.
7.35 Since only the bank knows x, then only the bank can send a response satisfying
both
±r ≡ ±xc+w ≡ (±x )c ±w ≡ hc y2 (mod p)
and
Ar ≡ Axc+w ≡ (Ax )c Aw ≡ mc y3 (mod p).



© 2003 by CRC Press LLC
242 Solutions to Odd-Numbered Exercises 7.37“8.5

7.37 By Exercise 7.34, XY ≡ y1 (mod p), and y1 ≡ Ax (mod p) with A ≡ 1 (mod p)
by step (1) of the protocol for opening Alice™s account. Also, x ∈ (Z/qZ)— , by
step (3) of the setup stage, so x ≡ 0 (mod q), which completes the proof.

Section 8.1
8.1 First we observe that
xi ’ x
≡ 0 (mod p)
Kk (xi ) =
xk ’ x
1¤ ¤t
=k


if i = k since Kk (xi ) has a factor (xi ’ xi )/(xk ’ xi ). Also,
Kk (xk ) ≡ 1 (mod p)
since all factors are of the form (xk ’ x )/(xk ’ x ) = 1. We note that
1/(xk ’ x ) ≡ (xk ’ x )’1 (mod p),
so as long as k = , such inverses exist. Therefore,
t
f (xi ) ≡ mk Kk (xi ) ≡ mi (mod p)
k=1

for i = 1, 2, . . . , t.
8.3 Although g(x) produces the same values, it does so at only one of the three values
of xi that f (x) produces them. We have
f (1) ≡ g(1) ≡ 7 (mod p),
but
g(2) ≡ f (3) ≡ 1407 (mod p), g(3) ≡ f (5) ≡ 334 (mod p).
and

Note that
(x ’ 2)(x ’ 3) (x ’ 1)(x ’ 3) (x ’ 1)(x ’ 2)
g(x) ≡ 7 + 1407 + 334 (mod p),
(1 ’ 2)(1 ’ 3) (2 ’ 1)(2 ’ 3) (3 ’ 1)(3 ’ 2)
whereas,
(x ’ 3)(x ’ 5) (x ’ 1)(x ’ 5) (x ’ 1)(x ’ 3)
f (x) ≡ 7 + 1407 + 334 (mod p),
(1 ’ 3)(1 ’ 5) (3 ’ 1)(3 ’ 5) (5 ’ 1)(5 ’ 3)
and, of course, f (0) ≡ 3301 (mod p), while g(0) ≡ 2856, which is not the original
message.
8.5 We calculate p(x) for x = 1, 3, 5 and get (1, 488), (3, 2400), and (5, 1881). Then
we compute the Lagrange interpolation formula to get,
2431 2 4343 11037
f (x) = ’ x’
x+ .
8 2 8
Since 8’1 ≡ 529 (mod p), 2’1 ≡ 2116 (mod p), and
’2431 · 529 ≡ 225; 4343 · 2116 ≡ 56; ’11037 · 529 ≡ 207,
all modulo p, then we recover the message at f (0) ≡ p(0) ≡ 207.



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 8.7“8.15 243

8.7 As above, we calculate (1, 1087), (3, 1677), (5, 2819), and plug this into the La-
grange interpolation formula to get immediately that f (x) = 69x2 + 19x + 999.
8.9 We have, m+rp = 50909 < 248605 = a1 ·a2 ·a3 . Thus we compute s1 ≡ 4 (mod 5),
s2 ≡ 5 (mod 7), and s3 ≡ 1188 (mod 7109). When the participants poll their
shares and use the Chinese Remainder Theorem, they recover

50909 ≡ 519 ≡ m (mod 5039).

8.11 As above, rp + m = 713371 < a1 · a2 · a3 = 770110;

s1 ≡ 1 (mod 10), s2 ≡ 10 (mod 11), and s3 ≡ 6270 (mod 7001).

The Chinese Remainder Theorem recovers 713371 ≡ 3071 ≡ m (mod p).
8.13 We compute,
c1 ≡ 90 ’ 15 · 59 ’ 52 · 409 ≡ 69 (mod 503),
c2 ≡ 90 ’ 11 · 59 ’ 123 · 409 ≡ 440 (mod 503),
c3 ≡ 90 ’ 308 · 59 ’ 400 · 409 ≡ 404 (mod 503),
so the distributed hyperplanes are,

≡ 69 + 15x1 + 52x2 ; ≡ 440 + 11x1 + 123x2 ; ≡ 404 + 308x1 + 400x2 ,
1 2 3


all congruences modulo 503. Plugging these values into (8.4), we get,


« « « 
’1 ’69
15 52 x1
 11 ’1   x2  =  ’440  = C.
123
AX =
’1 ’404
308 400 x3

then solving for det(A) = 22195, and using Cramer™s rule, we get

(x1 , x2 , x3 ) = (105323/22195, ’110043/22195, ’2610936/22195).

However, 22195’1 ≡ 8 (mod 503) and

105323 · 8 ≡ 59; ’110043 · 8 ≡ 409; ’2610936 · 8 ≡ 90,

all congruences modulo 503. Thus, (m1 , m2 , m3 ) = (59, 409, 90), and the secret
message m1 = 59 is retrieved.
8.15 As above,
c1 ≡ 718 ’ 297 · 107 ’ 306 · 1 ≡ 269 (mod 719),
c2 ≡ 718 ’ 419 · 107 ’ 537 · 1 ≡ 645 (mod 719),
c3 ≡ 718 ’ 698 · 107 ’ 709 · 1 ≡ 99 (mod 719),
so the distributed hyperplanes are,

≡ 269+297x1 +306x2 ; ≡ 645+419x1 +537x2 ; ≡ 99+698x1 +709x2 ,
1 2 3


all congruences modulo 719. Thus,




© 2003 by CRC Press LLC
244 Solutions to Odd-Numbered Exercises 8.15“8.19


« « « 
’1 ’269
297 306 x1
 419 ’1   x2  =  ’645  = C.
537
AX =
’1 ’99
698 709 x3

then solving for det(A) = 43465, we get
(x1 , x2 , x3 ) = (190798/43465, ’171516/43465, 3175039/8693).
However, 43465’1 ≡ 323 (mod 719), 8693’1 ≡ 177 (mod 719), and
190798 · 323 ≡ 107; ’171516 · 323 ≡ 1; 3175039 · 177 ≡ 718,
all congruences modulo 719. Thus, (m1 , m2 , m3 ) = (107, 1, 718), and the secret
message m1 = 107 is retrieved.
t
8.17 In matrix-theoretic terms, the equation mk ≡ m + cj xj (mod p) is written
k
j=1
as

« «  « 
··· xt’1
1 x1 c0 m1
1
¬ ·¬ ·¬ ·
··· xt’1 c1 m2
1 x2
¬ ·¬ ·¬ ·
2
·≡¬
AC = ¬ ·¬ · (mod p).
. .
. . . .
   
. .
. . . . . .
. . . .
··· t’1
ct mt
1 xt xt
We now show that
(xk ’ xi )
det(A) = (S3)
1¤i<k¤t

We use induction on t. If t = 2, then
1 x1
det(xj ) = = x2 ’ x1 .
k 1 x2
This is the induction step. Now assume that the result holds for all such n — n
matrices with n < t. If cof(Aj,k ) denotes the cofactor of the matrix A = (xj ),
k
then by (C.37),
t
det(xj ) xj cof(Aj,k ).
=
k k
i=1
By induction hypothesis, the result holds for each Aj,k , so the entire result holds.
Since we have shown that (S3) holds, it is clear that det(A) ≡ 0 (mod p) if an
only if xk ≡ xi (mod p) for some i = k.

Section 8.2
8.19 We have,
sdA (pe + IB )eA ≡ ±eB dA ((cB ’ IB )de + IB )eA ≡ ±eB dA (cB ’ IB + IB )eA ≡
B
B

±eB dA (cB )eA ≡ ±eB dA ±dB eA ≡ ±eB dA +eA dB ≡ k (mod n),
and
sdB (pe + IA )eB ≡ ±eA dB ((cA ’ IA )de + IA )eB ≡ ±eA dB (cA ’ IA + IA )eB ≡
A
A

±eA dB (cA )eB ≡ ±eA dB ±dA eB ≡ ±eA dB +dA eB ≡ k (mod n).



© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 8.21“8.27 245

8.21 All congruences are modulo n = 48959 = pq. We perform the calculations within
the scheme. Alice and Bob, respectively, compute, cA ≡ ±dA ≡ 310279 ≡ 38953
and cB ≡ ±dB ≡ 332773 ≡ 11653, and Trent computes

pA ≡ (cA ’ IA )d ≡ (38953 ’ 21)9701 ≡ 35736,

and
pB ≡ (cB ’ IB )d ≡ (11653 ’ 93)9701 ≡ 30197.
Then Alice and Bob compute, respectively,

sA ≡ ±eA ≡ 3151 ≡ 3211,

and
sB ≡ ±eB ≡ 337 ≡ 26897.
Lastly, Alice and Bob, respectively, compute,

k ≡ sdA (pe + IB )eA ≡ 2689710279 (301975 + 93)151 ≡ 28578,
B
B

and
k ≡ sdB (pe + IA )eB ≡ 321132773 (357365 + 21)37 ≡ 28578,
A
A

the self-certi¬ed shared key.
8.23 As above, we do the calculations. All congruences are modulo n = 295907 = pq.

cA ≡ 72021 ≡ 204856, and cB ≡ 73011 ≡ 59114,

pA ≡ (204856 ’ 156)290315 ≡ 26211,
pB ≡ (59114 ’ 1001)290315 ≡ 217630,
sA ≡ 714033 ≡ 90187, and sB ≡ 7221675 ≡ 15244,
k ≡ 152442021 (217630131 + 1001)14033 ≡ 124394,
and lastly Bob™s calculation,

k ≡ 901873011 (26211131 + 156)221675 ≡ 124394,

to establish the shared key.
8.25 Trent computes, with all congruences modulo p,

p(x, y) ≡ 11 + 13(x + y) + 200xy,

fA (x) ≡ 141 + 210x; fB (x) ≡ 122 + 380x; fC (x) ≡ 183 + 24x;
from which are computed the session keys,

kA,B ≡ 316; kA,C ≡ 423; kB,C ≡ 203.

8.27 As above,
p(x, y) ≡ 5 + 15(x + y) + 25xy,
fA (x) ≡ 287 + 485x; fB (x) ≡ 186 + 47x; fC (x) ≡ 95 + 165x;
from which we get,

kA,B ≡ 746; kA,C ≡ 770; kB,C ≡ 468.



© 2003 by CRC Press LLC
246 Solutions to Odd-Numbered Exercises 8.29“9.3

8.29 As above,
p(x, y) ≡ 5 + 808(x + y) + 700xy,
fA (x) ≡ 620 + 127x; fB (x) ≡ 524 + 883x; fC (x) ≡ 495 + 733x;
from which we get,

kA,B ≡ 21; kA,C ≡ 210; kB,C ≡ 33.

8.31 Since Mallory has

fM (x) ≡ r1 + r2 kM + (r2 + r3 kM )x (mod p),

and Eve has
fE (x) ≡ r1 + r2 kE + (r2 + r3 kE )x (mod p),
then they have the four modular equations,

aM ≡ r1 + r2 kM (mod p),

bM ≡ r2 + r3 kM (mod p),
aE ≡ r1 + r2 kE (mod p),
and
bE ≡ r2 + r3 kE (mod p).
Hence, they have four equations in three unknowns from which elementary al-
gebra will yield a unique solution for r1 , r2 , r3 .


Section 9.1
9.1 Since Monty knows e, he can easily forge messages at will, and they will go
undetected due to the RSA conjecture. If Hostvania violates the treaty by
engaging in an underground nuclear test, it can point its ¬nger at Monty as the
perpetrator, and Monty could not disavow this claim since he knows e, and is
capable of forgeries.


Section 9.2
9.3 Bob veri¬es Alice™s signature by using her public key to get,

DeA (DdA (c)) ≡ c (mod n).

Then he uses his private key to obtain,

DdB (c) ≡ m (mod n),

where
eB dB ≡ 1 (mod (p2 ’ 1)(q 2 ’ 1)).




© 2003 by CRC Press LLC
Solutions to Odd-Numbered Exercises 9.5“9.9 247

9.5 Since
e’m(m’1)/(2n) ≈ 1 ’ pc ,
then
’m(m ’ 1)/(2n) ≈ ln(1 ’ pc ).
Hence,
m2 ’ m ≈ ’2n ln(1 ’ pc ),
and so
m2 ≈ ’2n ln(1 ’ pc ) ≈ 2n ln(1/(1 ’ pc )),
since we can safely ignore the smaller factor of ’m in an approximation. Thus,

m≈ 2n ln(1/(1 ’ pc )).

If pc = 1/2, then √
m ≈ 1.17 n.


. 1
( 2)



>>