AN INTRODUCTION TO MATHEMATICAL CRYPTOGRAPHYERRATA FOR THE FIRST EDITIONJEFFREY HOFFSTEIN, JILL PIPHER, JOSEPH H. SILVERMAN

Acknowledgements
We would like to thank the following people who have sent us comments and corrections: Stefanos Aivazidis, John B. Baena, Robert Bond, Reinier Broker, Rebecca
Constantine, Stephen Constantine, Christopher Davis, Steven Galbraith, Motahhareh Gharahi, David Hartz, Jeremy Huddleston, Calvin Jongsma, Maya Kaczorowski, Yamamoto Kato, Jonathan Katz, Ariella Kirsch, Ryo Masuda, Shahab
Mirzadeh, Kenneth Ribet, Ghassan Sarkis, Frederick Schmitt, Christine Schwartz,
David Singer, Michael Soltys, Bruce Stephens, Paulo Tanimoto, Ralph Wernsdorf,
Sebastian Welsch, Ralph Wernsdorf, Edward White, Pomona College Math 113(Spring 2009), University of California at Berkeley Math 116 (Spring 2009, 2010).
Page xiv, Line 7
Vigénere should be Vigenère. (The accent should be on the second e, not the ﬁrst e.)
Page xiv
In the last line of the summary of Chapter 6, “covereed” has an extra “e”.
Page 4, lines 2 and 11
The last part of the ciphertext should be SCVKC B, instead of SCVKV B, and theplaintext is caesar, not caeser. (But note that it has been corrected on line 14!).
Page 10, Line −13
Add commas to improve readability. Thus:
If a and b are integers, then we can add them, a + b, subtract them, a − b, andmultiply them, a · b. In each case, we get an integer as the result.
Page 12, Definition (Division Algorithm)
This is the deﬁnition of division with remainder, so it is not really an algorithm.
Further, for a given a and b, it is not entirely clear that q and r exist. The existence
is easy to prove, of course, for example by taking r to be the smallest positiveelement in the set {a − bn : n ∈ Z} and proving by contradiction that r < b. The
uniqueness also needs to be proved. Might be best to note that the statements need
to be proved, and make the proofs an exercise.

Date: June 27, 2012.
1

2

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 13, Statement of Theorem 1.7
The conclusion of Theorem 1.7 (the Euclidean algorithm) should be that the division step is execuated at most 2 log2 (b) + 2 times. Of course, one can replace thiswith ⌊2 log2 (b) + 2⌋. But in view of Remark 1.8, the real interest in the boundis that it is just a small multiple of log2 (b), and hence the Euclidean algorithm
terminates quite rapidly, even when b is quite large.
Page 20, Proof of Proposition 1.13
The proof of (b) does not include a proof that the inverse is unique modulo m. A
quick proof is to assume that b1 and b2 are both inverses of a modulo m and thencomputeb1 ≡ b1 · 1 ≡ β1 · (a · b2 ) ≡ (b1 · a) · b2 ≡ 1 · b2 ≡ b2

(mod m).

Page 21, Line 17
The text says here that the Euclidean algorithm takes 2 log2 (b) + 3 steps, but
Theorem 1.7 on page 13 should state (and does prove) that the Euclidean algorithm
takes at most ⌊2 log2 (b) + 2⌋ steps.
Page 21, Definition of Z/mZ
The book says “Note that whenever we perform an addition or multiplicationin Z/mZ, we always divide the result by m and take the remainder in order toobtain an element in Z/mZ.” This is a bit confusing. Really, we add or multiply
elements of Z and then divide in Z and take the remainder.
Page 22, Definition of (Z/mZ)∗
Again, if Z/mZ is deﬁned to be {0, 1, . . . , m − 1}, then the notion of an inverse isconfusing. Of course, the elements of Z/mZ are really equivalence classes, but that
introduces an entire extra level of complexity.
Page 27, Line −6
In the reference to [126, Chatper 7], the word Chapter is misspelled.
Page 28, Line −11“described in Exercise 1.28” should be “described in Exercise 1.29”
Page 32, Line 8
The book says that “In practice, the two algorithms tend to take about the sameamount of time.” This is true in the sense that naive implementations of each haverun time of O((log p)3 ). However, “Lehmer’s variant” of Euclid’s algorithm has a
run time of O((log p)2 ). So it might be worth putting in a footnote indicating thatthe run time issue is somewhat subtle.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

3

Page 33, Line 6
The chain of congruences
1 ≡ an ≡ akq+r ≡ (ak )r · ar ≡ 1r · ar ≡ ar(mod p).

should be
1 ≡ an ≡ akq+r ≡ (ak )q · ar ≡ 1q · ar ≡ ar (mod p).
(In the middle formula, (ak )r is changed to (ak )q , and in the next formula, 1r ischanged to 1q .)Page 36, Line 19“Germany introduced a new Enigama machine”. The name of the machine has an
extra “a”, it should be “Enigma”.
Page 38, Property 4 in the middle of the page
What is described is actually a known plaintext attack (KPA), not a chosen plaintext
attack (CPA). In a CPA, the attacker is allowed to chose any plaintext and be given
the corresponding ciphertext. For example, an attacker can always mount a CPA
against a public key cryptosystem, since he can encrypt any plaintext that hedesires. It is clear that if a system is secure against CPA, then it is secure against
KPA.
Pages 38, 42, 43, 44, 56, 57
All of the references to “chosen plaintext attack” should be changed to “known
plaintext attack”.
Page 47, Problem 1.1(b)There is an extra “L” in the ciphertext. The block in the middle that currently
reads “ZLJYL ALZAO” should read “ZLJYL AZAO”.
Page 53, Exercise 1.32(e)The problem says to “verify that there are exactly ϕ(229) of them,” but it should
say to “verify that there are exactly ϕ(228) of them.”
Page 53, Exercise 1.33
Also need to specify that g ̸≡ 0 (mod p).
Page 58, Line 3“(For example, if k = 23 and d = 6, then. . . ” should be “(For example, if k = 87
and d = 6, then. . . ”
Page 62, Line 1“probem” should be “problem”
Page 64, Line 11
logp (h) = 11235 should be log2 (h) = 11235. (The base of the logarithm is 2.)
Page 68 and following
Tahir ElGamal now prefers that his name be spelled Tahir Elgamal (according toWikipedia).

4

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 68, Middle Displayed Computation
Mention that the quantity (ca1 )−1 can be eﬃcently computed as cp−1−a.
1Page 69, line −13
The text says that “If Eve can solve the discrete logarithm problem, she can ﬁnd aand decrypt the message. Otherwise it appears diﬃcult for Eve to ﬁnd the plaintext,. . . .” In fact, it is enough for her to be able to solve the DHP, which wasintroduced on page 67. Mention this in the text, and add an exercise to prove thatsolving DHP breaks ElGamal. Note that this provides a converse to Proposition
2.10.
Page 73, Example (f )Although the group G is noncommutative, the matrices used as an example actuallycommute. The example should read
(
)(
) (
)(
)
1 1
1 1
1 1
1 1
̸=
.
0 1
1 0
1 0
0 1
Page 74, Proof of Proposition 2.13
There is some confusion with i and j in the ﬁrst paragraph of the proof. It should
read as follows:
Proof. Since G is ﬁnite, the sequencea, a2 , a3 , a4 , . . .
must eventually contain a repetition. That is, there exist positive integers i and jwith j < i such that ai = aj . Multiplying both sides by a−j and applying the grouplaws leads to ai−j = e. Since i − j > 0, this proves that some power of a is equal
to e. We let d be the smallest positive exponent satisfying ad = e.
Page 74, Proof of Proposition 2.13
The last line of the proof should be “Therefore k = dq, so d | k.” (It currently saysd | q.)
Page 74, First Paragraph
What is said is correct, but if one were really going to use a brute force method tosolve the DLP, one could do it in fewer steps by computing successively g, g 2 , g 3 , . . .,where computing g i+1 is done by multiplying the previously computed g i by g.
Page 80, Line −10
The books says that “Step (3) takes O(log n) steps,” but it should say that “Step (3)takes O(n log n) steps.” (One can’t even sort n elements in fewer than n steps, sinceeach element must be examined at least once!)
Page 87, Line 4“supppose” should be “suppose”.
Page 94, Part (c)We should say that R is always a ring, and it is a ﬁeld precisely when n is prime.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

5Page 102, Line −13“we can create new ﬁnite ﬁelds with a prime number of elements” should be we cancreate new ﬁnite ﬁelds with a prime power number of elements.
Page 104, Line −2“The primitive element theorem” should be “The primitive root theorem”, which
is how Theorem 1.31 is labeled.
Page 106, Line 2“if and only if its discrete logarithm logg (a) modulo p” should be “if and only if its
discrete logarithm logg (a) modulo p − 1”.
Page 106 and elsewhere
In some places it is called the “decision Diﬃe–Hellman problem” and in other places
it’s called the “Diﬃe–Hellman decision problem”. Probably this should be madeconsistant, with the former being the more common usage.
Page 107, Exercise 2.11
The second displayed equation should say τ 2 = e, not τ 2 = 1.
Page 109, Exercise 2.20
x = a + cn should be x = a + cm in line 3, and x = a + cn + ymn should be
x = a + cm + ymn in line 5.
Page 109, Exercise 2.22
This exercise says that it is “non-constructive,” but in principle the proof is constructive, since the rings are ﬁnite, so one can always compute the inverse to themap by trying all possible inverse images. What the proof does not give is aneﬃcient way to compute the inverse map.
Page 109, Exercise 2.22, displayed equation
There should be ellipses between the mZ2 Z and the mZk Z . Thus it should read
Z
Z
Z
Z
−→
×
× ··· ×mZ
m1 Z m2 Z
mk Z
a mod m 7−→ (a mod m1 , a mod m2 , . . . , a mod mk )(2.25)

Page 109, Exercise 2.24
The exercise should specify that a is an integer that is not divisible by p.
Page 110, Exercise 2.25
In this problem, p and q should be odd primes.
Page 115, Proposition 3.2
Add an exercise for Section 3.1 that describes what happens when gcd(e, p− 1) > 1,
and in the text refer the reader to the exercise. In particular, point out that inthis case, the solution x is not uniquely determined. (For the exercise, refer thereader to Theorem 1.11, the extended Euclidean algorithm, as the key to solving
the problem.)

6

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 116, Line 3“z de ≡ z (mod z)” should be “z de ≡ z (mod p)”.
Page 121, Line 17“since it takes only four squarings and one multiplication to compute m65537 ” shouldbe “since it takes only sixteen squarings and one multiplication to compute m65537 ”.
Page 126
Alford, Granville, and Pomerance proved that there were inﬁnitely many Carmichael number in 1994, not in 1984. (More precisely, their paper appeared in 1994.)
Page 127, Table 3.2
The loop in Steps 5–8 is somewhat confusing. The idea is that Steps 6 and 7 are
repeated exactly k times. But Step 5 says that i runs from 0 to k − 1, while Step 8
increments i. It might be clearer if Step 8 simply said:
8. End i-loop
Page 130, Line 16“To do this,, he ﬁrst. . . ” has a double comma.
Page 132, Lines 2–3√√
Put in a note that running time O( n) is exponential because n is exponential
in the number of bits required to write down the number n. Refer the reader backto Section 2.6 for the formal deﬁnitions of exponential-time and polynomial-time.
Page 132, Line 3
There is a missing period at the end of this sentence.
Page 147, Theorem 3.42
It would make more sense to say that 0 < ϵ < 21 . If ϵ > 12 , then the lower boundon B is larger than the upper bound, so there are no allowable values of B.
Page 171, Proposition 3.64
The two parts of the proposition are both labeled (a).
Page 176, Exercise 3.2
Should specify that the integers e and f are positive.
Page 178, Exercise 3.10
In the second displayed equation, it says c1 =≡ mg1s1 (mod N ). The equal sign isextraneous, it should read c1 ≡ mg1s1 (mod N ).
Page 178, Line 12 of Exercise 3.10
“Alice use the Chinese remainder theorem to solve the pair of congruences” shouldbe “Alice uses the Chinese remainder theorem to solve the pair of congruences”.
(Missing “s”.)

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

7

Page 179, Exercise 3.14(c)Parts (b) and (c) are the same. The correct value for (c) is(c) n = 294439.
Page 184, Exercise 3.34(c)The deﬁnition of u should have a β 2 terms, instead of two β 3 terms. So this exercise
should read:(c) u = 6 − 5β + 3β 2 + 3β 3 and v = −2 + 7β + 6β 2 .
Page 186, Last line of Exercise 3.38(a)“ that are congruent to 3 modulo p” should be “ that are congruent to 3 modulo 4”.
Page 186, Exercise 3.40
This problem should specify that the prime p satisﬁes p ≡ 1 (mod 3). It might beworth adding the following part (d) to the problem:(d) Suppose instead that p ≡ 2 (mod 3). Prove that for every integer a there is an
integer c satisfying a ≡ c3 (mod p). In other words, if p ≡ 2 (mod 3), show thatevery number is a cube modulo p.
This may be further generalized as follows: if gcd(m, p − 1) = 1, then every
number is an mth -power modulo p.
Pages 190–191, Examples 4.1 and 4.2
The phrasing of these examples is somewhat ambiguous, especially in Example 4.1
where it says “How many possibilities are there?” This could be interpreted as thenumber of (ordered) pairs of classes, which would be 20 · 20. It might be clearer
to ask “How many student–class possibilities are there?” Or change the examples
to, say, ordering food at a restaurant, where there are (say) two appetizers and
20 entrées pm the menu, and the example computes how many diﬀerent meals are
possible.
Page 205, Line 17–19“Similarly, if the keyword happens to start with B, then its second letter would be B
shifted by γ2 , its third letter would be A shifted by γ3 , etc.” should be “Similarly,
if the keyword happens to start with B, then its second letter would be B shiftedby γ2 , its third letter would be B shifted by γ3 , etc.” (The reference to A in thissentence should be to B.)
Page 217, Example 4.26
The Prisoner Paradox can be confusing for students, but since it is not a fundamental part of the course, the authors do not feel it deserves more than half a page.
The following material is thus made available as a supplement for instructors andstudents:
Before Alice gets any information from the jailer, there are three outcomes, eachof which has equal probability, so
Pr(Alice released) = 1/3,
Pr(Bob released) = 1/3,
Pr(Carl released) = 1/3.

8

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Next suppose that the jailer tells Alice the name of someone who will stay jailed,
but when the jailer has a choice, i.e., when both Bob and Carl will stay jailed, hepicks one at random. Then
Pr(Alice released and jailer says “Bob”) = 1/6,
Pr(Alice released and jailer says “Carl”) = 1/6,
Pr(Bob released and jailer says “Carl”) = 1/3,
Pr(Carl released and jailer says “Bob”) = 1/3.
So the fact that the jailer told Alice that Bob will stay jailed means that
1
1/6
= ,
Pr(Alice released | jailer says “Bob”) =1/6 + 1/3
3
so Alice’s chances of being released are still 13 .
Finally, suppose that the jailer tells Alice the name of someone who will stayjailed, but when the jailer has a choice, he always chooses Bob. Then
Pr(Alice released and jailer says “Bob”) = 1/3,
Pr(Alice released and jailer says “Carl”) = 0,
Pr(Bob released and jailer says “Carl”) = 1/3,
Pr(Carl released and jailer says “Bob”) = 1/3.
So the fact that the jailer told Alice that Bob will stay jailed means that
1/3
1
Pr(Alice released | jailer says “Bob”) == ,1/3 + 1/3
2
so in this scenario Alice’s probability of being released has increased to 12 .
Page 220, Section 4.3.4
This section can be diﬃcult for students (and instructors) who have not previously
studied probability. It has been suggested that in each of the examples, we explicitly
describe the sample space Ω, although once one becomes familiar with the languageof probability, this is seldom done. In particular, note that the sample space inExample 4.31 is an inﬁnite set.
Here is expanded text for Examples 4.29 and 4.31.
Example 4.29. The sample space Ω consists of all binary strings ω = b1 b2 . . . bnof length n, where bi = 0 if the i’th experiment is a failure and bi = 1 if thei’th experiment is a success. The value of the random variable X at ω is simply
X(ω) = b1 + b2 + · · · + bn , which is the number of successes. Using the randomvariable X, we can express the probability of the event ω asPr({ω}) = pX(ω) (1 − p)n−X(ω) .
(Do you see why this is the correct formula?)

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

9Example 4.31. The sample space Ω consists of all binary strings ω = b1 b2 b3 . . .,where bi = 0 if the i’th toss is tails and bi = 1 if the i’th toss is heads. This is an
example of an inﬁnite probability space. The way in which we assign probabilities
to events is by specifying a certain number of initial tosses. So for any given ﬁnite
binary string β1 β2 . . . βn , we assign a probability()
Pr {ω ∈ Ω : ω starts β1 β2 . . . βn } = p(# of βi equal to 1) (1 − p)(# of βi equal to 0) .
The random variable X is deﬁned byX(ω) = X(b1 b2 b3 . . .) = (smallest i such that bi = 1).
Then

{
} {
}
{X = n} = ω ∈ Ω : X(ω) = n = 000. . . 00} 1bn+1 bn+2 . . . .
| {zn − 1 zerosHencefX (n) = Pr(X = n) = (1 − p)n−1 p.
Page 221 and following
On page 221 the balls in the urns are black and white, while later in the chapter(e.g., page 228) they are red and blue. Maybe it would be best to make the colors
consistant.
Page 223, Line 17, Example 4.32
“Further the events F and S are independent” should be “Further the randomvariables F and S are independent”
Page 223, Line −9“easy because X and Y are independent” should be “easy because F and S are
independent”. (The events X and Y are not independent since X + Y = 2.)Page 223, Example 4.32
It could be mentioned that the second part of this example (picking two coins without replacement) is a special case of Example 4.30 (hypergeometric distribution)that starts on the bottom of page 221. Thus the 47 appearing as the last line ofpage 223 is the formula (4.24) on page 222 evaluated with N = 7, m = 4, n = 2,
i = 1, which yields( )( )
4 3
41 1( ) = .
7
7
2
Page 225, Line 3“The prompts” should be “This prompts”.

10

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 230, Lines 13–15“the “red balls” are the eight marked cards in the second deck, and the “blue balls”
are the other 48 cards in the second deck” should be “the “red balls” are the eightmarked cards in the second deck, and the “blue balls” are the other 44 cards in thesecond deck”. (If we take 8 card away from 52 cards, there are 44 cards left, not
48!)
Page 230, Example 4.40
The previous discussion and Theorem 4.38 deal with probabilities of selection withreplacement, but this example is diﬀerent. From the way it is phrased, Bob selects
100, 000 elements, puts them back into the set, and then selects another 100, 000
elements. It is actually not clear if either or both subsets are selected with replacement. In order for the formula to be exactly correct, the ﬁrst set should be chosen
without replacement, the second with replacement.
Of course, since the set has 10 billion elements and the sample sets only have
100, 000 elements, the issue of replacement should not greatly aﬀect the answer.
The same applies to Example 4.41, as long as n is small compared to N . But thisshould be explained.
Page 230, Line −14“Theorem 4.38(a)says” needs a space between (a) and “says”.
Page 232 and Elsewhere
The discrete logarithm problem is stated using diﬀerent notations in diﬀerent partsof the book. Thus:
Section 2.7:g x = h.
Section 4.4.3: hx = b.
Section 4.5.2: g t = a.
To the extent possible, it would be good to use a consistant notation.
Page 232 Proposition 4.44
This proposition is included to illustrate the running time of a randomized algorithm
and as a warm-up for Pollard’s rho algorithm. But it is also true that the babystepgiantstep algorithm describedin Proposition 2.22 accomplishes the same task and√is guaranteed to have O( N ) running time. It might be worth making an explicit
comment to this eﬀect.
Page 233, First displayed equation
The middle term should be 1 − (1 − n/N )n , not (1 − n/N )n . Thus the entire line
should read
(
)
(
2
n )n
at least one matchProb≈ 1 − e−n /N .
≈1− 1−
between (4.31) and (4.32)
N
Page 233, Line 6–7
The text currently says: “then our probability of getting√ a match is approximately 99.98%.” It has been pointed out that taking n = 3 N gives a probabilityof 99.987659%, which is closer to 99.99%. So change it to “then our probability ofgetting a match is greater than 99.98%.”

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

11

Page 233, Line −5“moduluo” should be “modulo”.
Page 240, Line 4
g i−j = aℓ−j should be g i−k = aℓ−j .
Page 243, Line 15
In the list of powers of 19, the quantity 19135645 should be 44690, not 23894.
Page 244, Section 4.6.1
This section may be diﬃcult for students whose ﬁrst introduction to probability
theory was reading Section 4.3. In particular, the deﬁnition of a random variable
on page 220 says that a random variable is a function X : Ω → R, while the randomvariables M , K, and C used in Section 4.6.1 do not have this form. Thus if we
let M, K, and C denote the sets of plaintexts, keys, and ciphertexts, then there we
start with a probability space (Ω, Pr) and deﬁne random variables M , K, and C to
be functions
M : Ω → M,
K : Ω → K,
C : Ω → C.
Then for any particular plaintext m ∈ M, we have()
fM (m) = Pr(M = m) = Pr {ω ∈ Ω : M (ω) = m} ,and similarly for K and C. The distribution functions fM , fK , and fC are related
to one another via the encryption/decryption formula dk (ek (m)) = m, which iswhat leads to formula (4.47) on page 245.
Page 245, Formula (4.47)
This formula is not correct if there are some keys k such that c is not the encryptionof any plaintext. The correct formula is∑()
fK (k)fM dk (c) .
(4.47)fC (c) =k∈Ksuch thatc∈ek (M)In other words, we should sum only over those keys k for which c is a possible
ciphertext. A more detailed derivation of (4.47) goes as follows and reveals the
problem:∑f (c) =
f (k)f (c | k)
k∈K

=

=

∑

f (k)

∑

k∈K

m∈M

∑

∑

k∈K

f (k)

(using the decomposition formula, Exercise 4.23)
f (m)f (c | k and m)(using the decomposition formula again)f (m).

m∈Mek (m)=c

The last equality follows from the fact that{
1 if c = ek (m),f (c | k and m) =0 if c ̸= ek (m).

(∗)

12

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Now consider the set{}
S = m ∈ M : ek (m) = c .

If c ∈/ ek (M), then it is clear that S = ∅. On the other hand, if c ∈ ek (M), say
c = ek (m′ ), thenek (dk (c)) = ek (dk (ek (m′ ))) = ek (m′ ) = c,so dk (c) ∈ S. Conversely, if m ∈ S, then dk (c) = dk (ek (m)) = m. This proves that{{}dk (c)
if c ∈ ek (M),S=∅
if c ∈/ ek (M).
Hence the inner sum in (∗) equals f (dk (c)) if c ∈ ek (M), and it equals 0 otherwise.
This gives the corrected version of formula (4.47).
Page 246, Line −13“ the number of keys must also be at least as large as the number of ciphertexts”
should be “ the number of keys must also be at least as large as the number ofplaintexts”. Note that this is what we prove, #K ≥ #M.
Page 246, Proposition 4.54
It should be stated explicitly in Proposition 4.54 that we assume that f (m) > 0
for all plaintexts m ∈ M. Note that this is a reasonable assumption, since there
is no practical reason to include plaintexts in M that are never used. Further,
Proposition 4.54 is false without this assumption, since we can always make M
arbitrarily large by adjoining plaintexts that cannot occur (and thus that have noassociated ciphertexts). The proof breaks down at the line f (c | m) = f (c) > 0,
since the conditional probability f (c | m) is not deﬁned if f (m) = 0. As analternative, we could deﬁne M+ = {m ∈ M : f (m) > 0}, and then the conclusionof Proposition 4.54 is #K ≥ #M+ .
Page 252, Definition of Concavity and Theorem 4.59
The deﬁnition of concave (4.52) is a non-strict inequality, which it must be if weallow α in the closed interval [0, 1]. But then a linear function is concave, in whichcase Theorem 4.59 is not correct, since if F is a linear function, then equalityin (4.53) holds for all values of t1 , . . . , tn . So either change the deﬁnition to use
strict concavity, i.e., make (4.52) a strict inequality that is supposed to hold for
all 0 < α < 1, or in Theorem 4.59 say that equality holds in (4.53) if and only ifeither F is a linear function or t1 = · · · = tn .
Page 253, Corollary 4.60
The wording of Corollary 4.60 should be changed, since a random variable is not anexperiment and the xi are real numbers, not events. The event is {ω : X(ω) = xi },which can be abbreviated X = xi . Here is a reformulation of the corollary.
Corollary 4.6. Let X be a random variable that takes on finitely many possible
values x1 , . . . , xn .
(a) H(X) ≤ log2 (n).
(b) H(X) = log2 (n) if and only if every event X = xi occurs with the same probability 1/n.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

13

Page 254, Lines 4–7
The displayed equation ends with 23 ≈ 0.585. This should read 32 = 1.5. The
following line says: “Notice that H(M ) is considerably smaller than log2 (3) ≈1.585,. . . ”. This should be replaced with: “Notice that H(M ) is somewhat smaller
than log2 (3) ≈ 1.585,. . . ”.
Page 255, Line 4
The value at the end of this displayed equation is incorrect. It should read
( )
( )
( )
1
3
8
1
3
1 3
H(C) = − log2
− 2 · log2
= + log2≈ 1.56,
4
4
8
8
2 4
3
Page 255, Lines 6–8
Due to the correction on Line 4, we need to change Line 6 to read:H(K | C) = H(K) + H(M ) − H(C) ≈ 1 + 1.5 − 1.56 ≈ 0.94.
The next two lines say “This is quite low, which conﬁrms our intuition that in thiscryptosystem, an average ciphertext reveals a signiﬁcant amount of information
about the key.” Either remove these lines, or change them to reﬂect the fact thatthe entropy is not particularly low.
Page 256, Definition of H(L)The entropy of L is deﬁned as the limit
H(Ln ),n→∞n
but it’s not clear that the limit exists. In practice, one should probably deﬁne
upper and lower entropies H(L) and H(L) using a limsup and liminf, and then theinequality at the bottom of page 256 would be written as
H(L) = lim

1.0 ≤ H(L) ≤ H(L) ≤ 1.5,
but it’s probably not worth going into such detail. Instead, can just say that H(L)is the limit, if the limit exists, and that experimentally it appears that
H(Ln )
1.0 ≤
≤ 1.5
n
as n increases.
Page 257, Line −13
This displayed equation should read
e:M→C

and

e′ : M′ → C ′(In the text there is a missing prime on the second M.)

14

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 258, Middle
The description of Post’s correspondence problem is incorrect. In the correct description, one is allowed to use pairs an unlimited number of times. Here is thecorrected description of that paragraph.
There are uncountably many undecidable problems in mathematics, some ofwhich have simple and interesting formulations. Here is an example of an easy tostate undecidable problem called Post’s correspondence problem [96]. Suppose thatyou are given a sequence of pairs of strings,(s1 , t1 ), (s2 , t2 ), (s3 , t3 ), . . . , (sk , tk ),where a string is simply a list of characters from some alphabet containing at least
two letters. The correspondence problem asks you to decide whether there is an
integer r ≥ 1 and a list of indicesi1 , i2 , . . . , ir

between 1 and k(4.55)

such that the concatenations
si1 ∥ si2 ∥ · · · ∥ sirandti1 ∥ ti2 ∥ · · · ∥ tir

are equal.

(4.56)

Note that if we bound the value of r, say r ≤ r0 , then the problem becomes
decidable, since there are only a ﬁnite number of concatentations to check. The
problem with r restricted in this way is called the bounded Post correspondence
problem.
Page 259, Line 7
The quote marks before ”nondeterministic” are backwards, it should be “nondeterministic”.
Page 259, Paragraph after the Definition
Regarding the discussion of P versus NP, the book says that the Post’s Correspondence Problem is in NP. That is not true. First, all languages in NP are decidable.
Second, the book says that “given a subsequence of pairs (4.55) whose concatenations (4.56) are alleged to be the same, then it takes a polynomial number of steps
to verify that the concatenations are indeed the same.” But it has to be polynomialin the size of the input problem, and the proof (or certiﬁcate) in the PCP problem(if it exists) can be very long. (The authors thank Michael Soltys and Christopher
Davis for this correction.) What is true is that there is a variation of Post’s problem
which is NP complete. This is the bounded Post correspondence problem (see thecorrection for page 258). Here is the corrected version of this paragraph:
For example, the bounded Post correspondence problem is in N P. It is clearthat if you are given a list of indices (4.55) of bounded length such that the concatenations (4.56) are alleged to be the same, it takes a polynomial number of steps
to verify that the concatenations are indeed the same. On the other hand, exhaustively checking all possible concatenations of length up to r0 takes an exponential
number of steps. It is less clear, but can be proven, that one cannot ﬁnd a solution
in a polynomial number of steps.
Page 259, Line −8“inuuition” shoud be “intuition”.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

15

Page 270, Exercise 4.27
The last sentence says that this exercise generalizes Section 4.3.3 with δ = 0.01 andp = 12 . It should say with δ = 0.99, since δ is the probability that m has property A,
while in Section 4.3.3, E is the event that an integer does not have property A and
we’re given that Pr(E) = 0.01. Alternatively, one can deﬁne δ to be the probability
that m does not have property A.
Page 271, Exercise 4.31
Parts of this problem are easier using the operator Θ = xd, since Θ(xn ) = nxn .
dx(So the monomials are eigenfunctions for Θ.) Then
(∞
)
(
)
∞
∑
∑
1
Θk
= Θk
xn =
nk xn ,
1−x
n=0
n=0

valid for |x| < 1. It is not clear if it is worth introducing Θ in the text, but thismaterial may be used by interested instructors or students.
Page 272, Exercise 4.32(d)The hint should be to (4.29) on page 221, not (4.23) on page 221.
Page 286, Remark 5.7
Rather than ﬁrst deﬁning elliptic curves over Fp in general, and then excluding
p = 2 and 3, it might be better to exclude them from the start.
Page 288, Line −9 and −7
There’s an arithmetic error in these calculations, although it does not aﬀect theﬁnal answer. (λ should be 12, not 1, although note that 12 is the same as −1, since
we’re working in F13 .) These lines should read as follows:λ=3x21 + A
3 · 92 + 3
246
=
=
= 12
2y1
2·7
14

and ν = y1 − λx1 = 7 − 12 · 9 = 3.

Thenx3 = λ2 − x1 − x2 = (12)2 − 9 − 9 = 9and y3 = −(λx3 + ν) = −(12 · 9 + 3) = 6,

Page 288, Line −6“for the X-and Y-coordinates” should have a space after the dash following the X.
Thus it should read “for the X- and Y-coordinates.”
Page 295, Line above equation (5.6)
Replace “for some t ≥ 1” by “for some t ≥ 2”, since we want at least two consecutive
ones.
Page 299, Last line of Section 5.4.1“ their shared secret value is the x-coordinate x = 593, which is the same for both
points” should be “ their shared secret value is the x-coordinate x = 509, which isthe same for both points”. Note that 509 is the x-coordinate of their shared point.
The value 593 is the value of xA .

16

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 299, 338, 350, . . .
The use of the term ephemeral key in the text is somewhat non-standard. The
usual deﬁnition of an ephemeral key in cryptography is a key that is generated foreach execution of a key establishment process. In the text it is used to denote aquantity that is used for encryption, but that changes each time a new plaintext isencrypted, hence its “ephemeral” nature. The occurrences of the term “ephemeralkey” in the text are listed in the index on page 508.
Page 300, Table 5.6 and in several other places“ciphtertext” should be “ciphertext”
Page 312, Theorem 5.29√
“Notice that Hasse’s theorem (Theorem 5.11) says that |t| ≤ p” should be “Notice√that Hasse’s theorem (Theorem 5.11) says that |t| ≤ 2 p”. (There’s a missing 2 inthe upper bound for Hasse’s theorem.)
Page 312, Line -4
This displayed equation should read
τ 2 (Q) − t · τ (Q) + p · Q = O,(The “zero” on the right-hand side is O, not the number 0.)
Page 313, Line −1
This line says “equation τ 2 + τ + 2 when it acts on points of E(F2k ),” but it should
read “equation τ 2 + τ + 2 = 0 when it acts on points of E(F2k ),” (an equation needs
an equal sign!).
Page 316, Line 4This displayed equation should read{}E[m] = P ∈ E : mP = O .
(The notation [m]P is also a common notation, but it is not the notation used inthis book.)
Page 317, Second Paragraph
The text says “In a similar manner, if E is an elliptic curve,
E : Y 2 = X 3 + AX + B,
and if f (X, Y ) is a rational function of two variables, then there are points of E
where the numerator of f vanishes. . . ” Add a sentence explaining that f deﬁnes afunction on E in the sense that if P = (x, y) is any point of E, then we deﬁne f (P )to equal f (x, y), i.e., evaluate the rational function f (X, Y ) as the point (X, Y ) =(x, y).

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

17

Page 317, Section 5.8.2
When discussing poles and zeros of rational functions on an elliptic curve, add asentence to emphasize the fact that the coordinates of the poles and zeros may welllie in some extension ﬁeld. In particular, if E is deﬁned over Fp , the poles and zerosof a rational function f have coordinates in Fpk for some k, but the value of k will,in general, depend on the function f .
Should also mention that the zero function does not have a divisor, since itvanishes at every point.
Page 317, Example 5.35
Clarify that Y represents the function on the elliptic curve E deﬁned by
Y (P ) = (the y-coordinate of the point P ).
So the function Y vanishes at the three points (αi , 0), i = 1, 2, 3. That explains the
positive part of the divisor div(Y ). In order to get the negative part explicitly, one
needs to change coordinates. But can mention that it follows from Theorem 5.36(b)on the next page. Thus Y clearly has no poles at the ﬁnite points of E, sinceY (x, y) = y, so its only possible pole is at O. Hence
div(Y ) = [P1 ] + [P2 ] + [P3 ] − n[O]for some integer n. Now Theorem 5.36(b) tells us that deg(div(Y )) = 0, which
gives n = 3.
Page 318, Theorem 5.36(a)Say that f and f ′ are nonzero rational functions.
Page 318, Last Paragraph
It has been suggested that it would helpful to oﬀer some explanation as to why
the divisor of X − α is 2[P ] − 2[O], and not [P ] − [O], or at least to add such an
explanation to this errata sheet.
There are various ways to see that div(X − α) is 2[P ] − 2[O]. In particular, thefact that (α, 0) is a point on E means that α is a root of the cubic used to deﬁne E,
so the equation of E has the form
E : Y 2 = (X − α)(X 2 + aX + b).
Further, the polynomials of X − α and X 2 + aX + b have no common roots (thisis where we use the nonsingularity of E), so they have no common zeros. And ofcourse, their only pole is the point O. It follows that div(X−α) and div(X 2 +aX+b)
have no points in common except for O. But
2 div(Y ) = div(X − α) + div(X 2 + aX + b),
which shows that the zeros of X − α appear with even multiplicity. Of course, theonly zero of X − α is the point P = (α, 0), which shows thatdiv(X − α) = 2n[P ] − 2n[O]for some integer n ≥ 1. (Note that the total number of zeros and poles sums tozero.)

18

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

There are various ways to prove that n equals 1. For example, we can provethat Y is a local uniformizer at P , i.e., it vanishes to order 1 at P . To do that, weconsider the local ring at P , which is the ring{}f (X, Y )R=
: Y 2 = X 3 + AX + B and g(α, 0) ̸= 0 .
g(X, Y )In other words, we take all rational functions whose denominator does not vanish
at P . This is a local right whose maximal ideal is generated by X − α and Y . But
sinceY2
X −α= 2and X 2 + aX + b does not vanish at P ,X + aX + b
we see that X −α is in the ideal of R generated by Y , so Y is a uniformizer. Indeed,this shows that X − α generates the same ideal as Y 2 , so
ordP (X − α) = 2 ordP (Y ) = 2.
Page 319, Section 5.8.3
Add [123, Section III.8] as a reference for the Weil pairing and for the proof of
Theorem 5.38.
Page 321, Section 5.8.4
Add [123 (2nd edition, 2009), Section XI.8] as a reference for additional material
on Miller’s algorithm.
Page 324, Section 5.8.5
Add [123 (2nd edition, 2009), Section XI.9] as a reference for the Tate pairing.
Page 326 and 328
After Step 4 of the MOV algorithm, if it turns out that α = 1, then one needs togo back to Step 2 and choose a new point T . This may happen even if T ′ ̸= O,
e.g., if T ′ happens to be a multiple of P .
Page 328, Table 5.9, Step 2
It is natural to ask how one generates a random point T ∈ E(Fpk ) with T ∈/ E(Fp ).
One method is to choose random values x ∈ Fpk and check if x3 + Ax + B is asquare in Fpk . An easy way to do this is
z is a square in Fpk⇐⇒

z (p −1)/2 = 1.
k

(We are assuming here that p is an odd prime, of course.) There then exist practical(i.e., polynomial time) algorithms to compute square roots in ﬁnite ﬁelds, but
to describe them would take us too far aﬁeld. (See (26, §§1.5.1, 1.5.2) for thecase k = 1.)
Page 332, Last displayed equation
This line is true, but the logic of the line is a bit confusing. It would be better towrite: “Since P is a point of order ℓ, Proposition 5.51(b) says thatℓϕ(P ) = ϕ(ℓP ) = ϕ(O) = O,so ϕ(P ) is a point of order ℓ.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

19

Page 337, Line −15
The book says: “Let êℓ be the associated modiﬁed Weil height.” First, it should
be “Weil pairing,” not “Weil height.” Second, this is slightly diﬀerent from theterminology on page 330, so change it to “Let êℓ be the modiﬁed Weil pairing
relative to the map.”
Page 337–338
The hash function H1 needs to select points of order ℓ, not arbitrary points in E(Fq ).
So H1 should be deﬁned by
H1 : {User IDs} −→ E(Fq )[ℓ].
This needs to be changed on page 337, line −10 and page 338 line 5 of Table 5.11.
Page 337–338
It might be worthwhile to explain how to construct a hash function like H1 thattakes its values in E(Fq )[ℓ]. Here is one method. Note that Tom has already ﬁxed apoint in P ∈ E(Fq )[ℓ] of order ℓ. So we can take the User ID, call it i, and use it asa seed for a pseudorandom number generator (see Section 8.2) to get a number m.
Then we set H1 (i) = mP . (In practice, one needs to be a bit more careful so as toensure that as i varies, the values of m mod ℓ are uniformly distributed modulo ℓ.)Page 338, Table 5.11
In Master Key Creation, Tom should choose s modulo ℓ, not modulo m.
Page 338, Table 5.11
In Decryption, Alice should compute
C2 xor H2 (êℓ (QAlice , C1 )).
(The H2 is missing in the text.)
Page 344, Exercise 5.22(b)The displayed equation should readtk = t1 tk−1 − 2tk−2

for all k ≥ 3.

There are two corrections: the ptk−2 is changed to 2tk−2 , and the condition t ≥ 3
has been changed to k ≥ 3.
Could add a part (e) to this problem (or create a new problem) to prove asimilar recursion for general elliptic curves. Using the formula in Theorem 5.29 on
page 312, let
tk = pk + 1 − #E(Fpk ).
Then one can show thattk = t1 tk−1 − ptk−2

for all k ≥ 3.

Page 339, Exercise 5.3
The equation should readx3 + Ax + B = (x − e1 )(x − e2 )(x − e3 ).
(The text has a typo (x − e1 )(x − e2 )(x − e2 ).)20

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 344, Exercise 5.23
The upper bound on ℓ should be ℓ ≤ 2⌈log n⌉+1. We say in the proof of Proposition
5.30 that it is possible to get ℓ ≈ log n and we give a reference. However, the algorithm given in Exercise 5.23 seems to only return an expansion with ℓ ≤ 2⌈log n⌉+1.
Page 346, Exercise 5.32
The exercise says the formula is true “provided that the Tate pairings on the righthand side are computed properly.” This may cause some confusion. (How can they
be computed “improperly”?) Instead say “provided that the Tate pairings on theright-hand side are computed consistently.”
Page 347, Exercise 5.40
It should say to “Use the distortion map on E from Exercise 5.37 to compute. . . ,”not the distortion map from Exercises 5.38 and 5.39. (Note that the curve in
Exercises 5.38 and 5.39 is a diﬀerent curve.)
Page 350, Line 1
Also need to require gcd(f, g) = 1, since later in (6.1) we compute f −1 a (mod g).
Page 351, Table 6.1
Line 3: Need to require that gcd(f, q) = 1, as well as gcd(f, g) = 1.
Line 10: It says a ≡ √f e (mod e), but it should be√a ≡ f e (mod q) .
Line 6: It says m < q/2, but it should be m < q/4. (This is done correctly on
page 350.)
Page 353, Example 6.2
It is not true that S = 27 has a unique representation, since it is also 4 + 23. The
problem is that 9, 14, and 23 are all in the set M, and 23 = 9 + 14. Could changechange to S = 21, which has the unique representation 21 = 3 + 4 + 13.
Page 365, Line 4
There is a typo in the deﬁnition of w3 . It should be w3 = v1 + 2v2
Page 366, Line −2“Then very vector” should be “Then every vector”.
Page 373, Theorem 6.28
In the statement of Theorem 6.28 (Minkowski’s theorem), add the assumption that
S is bounded, since the proof uses this fact. (In fact, the ﬁrst part of the theorem
is true even if S is not bounded, since we can ﬁrst replace S with S ∩ B for asuﬃciently large ball centered at the origin. If B is large enough, we will have
Vol(S ∩ B) > 2n Vol(L). However, the second half of the theorem won’t work, since
if Vol(S) = 2n Vol(L), then Vol(S ∩ B) < 2n Vol(L) for any ball B.)

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

21

Page 374, Fifth displayed equation
The end of this sentence is missing. It should read “We now observe that the vector
S is symmetric,so −a2 is in S

1
a1 +
2
|

z( }| ){
1
− a2
2
{z
}

this is the midpoint of the line
segment from a1 to −a2 ,so it is in S by convexity

is in the set S.”
Page 377, Line −12
The text reads “we use the estimate (6.30) from Theorem 6.19,” but it should be“we use the estimate (6.19) from Theorem 6.30.”
Page 385, Line 10“he selects a small vector m as his plaintext” should be “he selects a small vector
m with integer coordinates as his plaintext”.
Page 386, Table 6.3
The Encryption part of the table says that Bob should computee = x1 v1 + · · · + xn vn + r.
This is not correct, he should computee = x1 w1 + · · · + xn wn + r,
since Alice’s public key is w1 , . . . , wn , not v1 , . . . , vn .
Page 379, Line −10
It reads “parallelepiped L + v”, but it should say “parallelepiped F + v”.
Page 382, Line −1
The v1 and v2 in this formula should be v1′ and v2′ .
Page 386, Table 6.3
Line 10: It sayse = x1 v1 + · · · + xn vn + r,
but it should reade = m1 w1 + · · · + mn wn + r,
Line 11: “ciphtertext” should be “ciphertext”.
Page 387, Line 7
Since e ≈ 75.76w1 −· · · , when it is rounded, the vector v′ should be v′ = 76w1 +· · · .

22

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 387, Remark 6.37
There are potential problems with choosing the ephemeral key deterministically assuggested in this remark. Note that one wants security against chosen plaintext
attacks, i.e., an attacker should not be able to determine whether a guessed plaintext corresponds to the given ciphertext. A solution is to add randomness to theplaintext. Naively, one might simply concatenate a random string to the plaintext,
but there are various reasons why this is not a good idea. In practice some sort ofencoding method is applied to the plaintext and a random string. This encoding
method (at least) has the properties that it is easy to invert and that changing
any bit of either the plaintext or the random string has an unpredictable eﬀect on
every bit of the output. Then this “randomized” plaintext is encrypted using anephemeral key.
Page 393, Line −14
The text says that the coeﬃcients of m(x) are “between − 21 p and 21 p.” This isambiguous if p is even, since in that case we want to include exactly one of theendpoints. The correct statement is that if p is even, then the coeﬃcients should
satisfy − 21 p < mi ≤ 21 p.
Page 393, Line −14“the plaintext m(x) is is a polynomial” has a repeated “is”.
Page 393, Equations (6.34), (6.35), (6.36)
It might be worth noting that when we say that the congruence holds modulo q,
the computation is being done in Rq .
Page 394, Table 6.4
There is actually no need to require that p be prime. However, if p is even, then one
doesn’t get a set of coset representative modulo p that is symmetric around 0, sosome choice needs to be made. Thus it’s probably easiest for expositional purposes
to at least assume that p is odd. In real-world applications, there may be situations
where one would take p = 2 and q odd.
Page 395, Remark 6.50
There are potential problems with choosing the ephemeral key deterministically assuggested in this remark. See the correction to Remark 6.37 on page 387. The
same comments apply to this remark.
Page 395, Line 6“possible coeﬃcient fo f ⋆ m” should be “possible coeﬃcient of f ⋆ m”.
Page 395, Third displayed formula
The ﬁrst line readsb(x) = Fp (x) ⋆ afrom (6.36).
But (6.36) is really just a congruence modulo p, so replace this line with a congruenceb(x) ≡ Fp (x) ⋆ a (mod p)
from (6.36).
Then should make the next line a congruence, too.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

23

Page 401, Proposition 6.61
This proposition assumes that q ≈ 6d, but the NTRU decryption condition isq > (6d + 1)p, so we should really assume that q ≈ 6dp. In practice, one might takep = 3, so q ≈ 18d ≈ 6N , which changes the numbers in the statement and proof√of Proposition 6.61. However, the conclusion that (f , g) is a factor of O(1/ N )smaller than predicted by the Gaussian heuristic is still valid.
Page 407, Line 11 (line after (6.51))
It reads “where F is the volume. . . .” It should read “where Vol(F) is the volume. . . .”Page 408, top
The next-to-last entry in the last line of the matrix M displayed at the top of thepage should read µn,n−1 , not µn−1,n .
Page 409, Equation (6.56)
There are two terms in this formula that should have squares on them. It currently
reads
(
)
3
1 ∗
∗
∥vi∗ ∥2 ≥− µ2i,i−1 ∥vi−1∥ ≥ ∥vi−1∥.
42
It should read
(
)
3
1 ∗ 2
∗ 2
2
∗
∥vi ∥ ≥
− µi,i−1 ∥vi−1∥2 ≥ ∥vi−1∥ .
42
Page 410, Line 13
This displayed formula starts∥vi ∥n ≤ · · · ,but it should be∥v1 ∥n ≤ · · · .
Page 411, Table 6.7
There are two mistakes in this description of the LLL algorithm. First, the loop
in Steps [5]–[7] should count down, not up. This is necessary becaue the span of{v1 , . . . , vj } is the same as the span of {v1∗ , . . . , vj∗ }, while the span of {vj , . . . , vk−1 }∗is not necessarily the same as the span of {vj∗ , . . . , vk−1
} Second, there is a typo∗in the formula in Step [6], it should be vj , not vj . (Otherwise the new value of vk
won’t necessarily be in the lattice!). So Steps [5]–[7] should read as follows:[5]

Loop j = k − 1, k − 2, . . . , 3, 2, 1

[6]

Set vk = vk − ⌊µk,j ⌉vj[7]

End j Loop

[Size Reduction]

24

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

Page 414, First paragraph and following
The given lower bound for D and its derivation are correct, but needlessly complicated. We have assumed that the lattice L is contained in Zn , so its basis
vectors v1 , . . . , vn have integer entries. Thus the same is true of Lℓ , which isspanned by v1 , . . . , vℓ . Letting Bℓ be the n-by-ℓ matrix of this matrix, we see thatdℓ = (det Lℓ )2 = det(Bℓt Bℓ ) is a ∏nonzero integer. Hence it trivially satisﬁes dℓ ≥ 1.
n
It is then immediate that D = ℓ=1 dℓ ≥ 1, which is much stronger than (6.60).
This lower bound completes the proof that the LLL algorithm terminates. Further,it simpliﬁes the analysis of the running time of LLL on the rest of this page andgives the stronger result that the running time is O(n2 log B). The statement ofTheorem 6.68 on page 4.11 should be adjusted accordingly.
Page 422, Exercise 6.3
There are two mistakes in this problem. First, the underlying sequence is not superincreasing, because the last two numbers in the list are 3253 and 6500. However, it
is still true that each number in the list is larger than the sum of all of the previous
numbers, which suﬃces to make the algorithm in Proposition 6.5 work. Second, thenumber S = 26560 cannot be written as a sum of elements from the list, because
it is too large. Here is a revised version of Exercise 6.3.
Alice’s public key for a knapsack cryptosystem is
M = (5186, 2779, 5955, 2307, 6599, 6771, 6296, 7306, 4115, 637).
Eve intercepts the encrypted message S = 4398. She also breaks into Alice’s computer and steals Alice’s secret multiplier A = 4392 and secret modulus B = 8387.
Use this information to ﬁnd Alice’s superincreasing private sequence r and thendecrypt the message.
Page 425, Exercise 6.17(b)The Hadamard ratio should have a square root. So it should read: “What is the()1/2
value of the Hadamard ratio det(L)/∥v1 ∥∥v2 ∥?”Page 431, Exercise 6.43
(a) “Prove a more version of Theorem 6.66” should be “Prove a version of Theorem 6.66 assuming this alternative Lovász condition.”(b) “Prove a version of Theorem 6.68” should be “Prove a version of Theorem 6.68
assuming this alternative Lovász condition.”
Page 433, Table 6.9, Step [5] of SWAP
In Step [5] of the SWAP subroutine, the value of B should be
B = Bk + µ2 Bk−1 .
(The book has a minus sign.)
Page 437, Line 4“It his thus” should be “It is thus”.

ERRATA FOR INTRO TO MATH CRYPTO — 1ST EDITION

25

Page 440, Section 7.2
In a future edition, possibly discuss RSA signing of private messages, i.e., Alicesends a signed encrypted message to Bob by using Alices private key and Bob’s
public key.
Page 442, top of pageThe numerical values of v and s have been swapped. So line 4 should readS ≡ Ds (mod N ),S ≡ 10707771051235 ≡ 153337(mod 2430101).

line 6 should readD = 1070777

andS = 153337.

and line 10 should readS v mod N,

153337948047 ≡ 1070777(mod 2430101).

Page 442–447, Section 7.3
For ElGamal signatures, the random quantity e needs to satisfy gcd(e, p − 1) = 1,
since the quantity e−1 mod p − 1 is used. For DSA the corresponding requirement
is gcd(e, q) = 1, or equivalently, q - e, since q is prime.
Page 442, Line 3 of Table 7.2“primtive” should be “primitive”.
Page 444, Second line of fourth displayed equation
The congruence for S2 should be modulo 21738, not 21736, since p = 21739 andthe congruence is modulo p − 1.
Page 466, Second line of second paragraph of Remark 8.1
Remove the word “and” from the phrase “a bit string of length n and into anotherbit string of length n.”
Page 490, Middle
In the deﬁnition of H(X), “teh” should be “the”.
Page 497, References [82]–[85]These should refer to NIST (National Institute of Standards and Technology), not
to NSB (National Bureau of Standards).
Page 499, Item [123]This bibliography item should be updated to refer to the second edition, publishedin 2009.