Errata

After now a year has passed since I submitted my Habilitation thesis “On arithmetic and the discrete logarithm problem in class groups of curves”, I realized some mistakes and inaccuracies. Two of the mistakes are quite important, and in fact a particular statement in the work is incorrect. The other mistakes and inaccuracies are relatively minor. I now first discuss the two important mistakes.

1. Lemma 2.109 and more generally the first item of Remark 2.106 are incorrect. It is not true that reductions along a divisor of degree 1 are always unique. Here is a counterexample: Let C/k be a hyperelliptic curve with a k-rational point P which is not a Weierstraß point. Let D̃ := P + ι(P) and let D_{0} := 2 ι(P) − P, where ι is the hyperelliptic involution. Then D̃ − D_{0} = 2P − ι(P), which is not linearly equivalent to a point. Thus D̃ is reduced along D_{0}, but |D̃| has dimension 1. The statements hold however if the divisor D_{0} is effective. In particular, reductions along a k-rational point are always unique. I remark that the incorrect statements mentioned here are not used in the index calculus algorithms in Chapter 3.

2. In order to prove Theorem 2, I wanted to apply Proposition 3.32 with C := \frac{1}{2g_{0}} (1 − \frac{1}{g_{0}} ) · \frac{log(\sqrt{2}−1)}{log(\sqrt{2})} (see page 154). However, this number is

negative as \sqrt{2} − 1 < 1. In fact, the Hasse-Weil bound does not give a non-trivial lower bound on # Cl^{0}(C) for q = 2, 3, 4. However, in Lachaud, Martin-Deschamps: Nombre de points de jacobiennes sur un corps fini (Acta. Arith. 56, 1990, pp. 329-340) the following lower bound on # Cl^{0}(C) is proven:

# Cl^{0}(C) ≥ \frac{(q − 1)^{2}}{(q + 1) · q} · \frac{1}{g + 1} · q^{g}

By this bound, we have # Cl^{0}(C) ∈ Õ(q^{g}) for all curves C/𝔽_{q}. With this result, Theorem 3 immediately implies Theorem 2. Additionally, the result from [Heß05] cited on page viii also holds if the expected running time is expressed in terms of # Cl^{0}(C) instead of q^{g}.

In addition to these mistakes, I have found some relatively minor inaccuracies which I list now in the order of occurrence.

• Page xi, line 4: Replace “[Sem98]” by “[Sem04]”.

• Page 100, line 5 of the proof of Lemma 2.108: Replace “then so is every divisor” by “then so is every effective divisor”.

• Page 122, Step 5 of the algorithm: Replace [γ]_{ℓ} by [\underline{γ}]_{ℓ}.

• Page 131, line -11: Replace “superpolynomial in the cardinality of the ground field” by “superpolynomial in the input length”.

• Page 133, Proposition 3.16: Replace the first four sentences by: “Let us fix some g ≥ 2. Then there exists some algorithm such that the following holds: Upon input of a curve C/𝔽_{q} of genus g, elements a, b ∈ Cl^{0}(C) and a system c_{1}, …, c_{u} whose size is polynomially bounded in log(q), if the algorithm terminates, it outputs the discrete logarithm of b with respect to a. Moreover, if c_{1}, …, c_{u} is a generating system, the expected running time of the algorithm is in Õ(q^{2−2g}).”

• Page 133, Proposition 2.17 and Proposition 3.18: Insert after “a curve C/𝔽_{q}”: “of genus g”.

• Page 137: Replace the “Procedure” by the following:

Procedure: Construction of the tree of large prime relations

Construct a labeled rooted tree T with vertex set contained in L ˙∪ {∗} as follows: Let T consist only of the root ∗, labeled with 0. Let N_{max} ⟵ ⌈q^{1−1/g+1/g^{2}}⌉. Let s ⟵ 1. Repeat

Repeat Choose s_{1}, …, s_{u} ∈ ℤ/Nℤ uniformly and independently at random. Compute the along P_{0} reduced divisor D in free representation with [D] − deg(D) · [P_{0}] = ∑_{j} s_{j}c_{j}. If D splits as D = ∑_{j} r_{j}F_{j} + Q with Q ∈ L − (F ∪ T),

insert an edge from ∗ to Q into T, labeled with (r_{j})_{j} (in sparse representation).

If D splits as D = ∑_{j} r_{j}F_{j} + r_{P} P + Q with P ∈ T_{s−1}, Q ∈

L − (F ∪ T) and r_{P} > 0,

insert an edge from P to Q into T, labeled with (r_{j})_{j} and r_{P}. In both cases label Q with s and the edge with (r_{j})_{j} (in sparse representation).

Until T contains min{2^{s−1} · ⌈q^{1−1/g}⌉, N_{max}} edges.

If the number of edges equals N_{max}, STOP.

Let s ⟵ s + 1.

• Page 139, line 12: Replace “[D − P_{0}]” by “[D − g · P_{0}]”.

• Page 143, last paragraph: Replace “D_{0}” by “E” (twice) and “an divisor” by “a divisor”.

• Page 146, line 12: Replace “uniformly randomly generated divisors” by “a uniformly randomly distributed divisor”.

• Page 150, Step 2 in the algorithm for Lemma 3.27: Replace “For i = 0, …, ⌈\frac{n}{m}⌉” by “For ℓ = 0, …, ⌈\frac{n}{m}⌉”.

• Page 152, line -3: Replace “is is” by “is”.

• Page 153, in the paragraph below Theorem 2. Replace “As in Proposition 2.117, the divisor classes are represented by an along D_{0} reduced divisors, where the height of D_{0} is polynomially bounded in d” by “As in Proposition 2.117, the divisor classes are represented by along D_{0} reduced divisors, where D_{0} has degree 1 and a height which is polynomially bounded in d”.

• Page 156, line 20: Replace “g^{Ω(1)}” by “\frac{1}{g^{Ω(1)}} ”.

• Page 163, line -5: Replace “merely merely” by “merely”.

• Page 167, Propositions 3.42 and 3.43: Perform changes analogously to the changes for Propositions 3.16 and 3.17 on page 133.

• Page 171: Perform changes in the “procedure” similarly to the changes in the “procedure” on page 137.

• Page 172: Replace lines 10-22 by the following:

“We thus obtain: A tree of large prime relations of size ⌈q^{1− \frac{1}{n}} ⌉ is constructed in an expected time of Õ(q^{2− \frac{2}{n}}). Let us now assume that we are in Stage s with s ≥ 2. We set

M := F^{n−2} × (F ∪ T_{s−1}) × (L − T) .

Now for q large enough (and independently of T, in particular independently of s) this set has cardinality ≥ (q^{1− \frac{1}{n}})^{n−2} · 2^{s−2} · q^{1− \frac{1}{n}} · \frac{q}{4} = 2^{s−2} · (q^{1− \frac{1}{n}})^{n−1} · \frac{q}{4}. For q large enough the probability that one try gives rise to a new edge is

≥ \frac{D}{16} · 2^{s−2} · q^{−(1− \frac{1}{n})} .

This implies that for q large enough (independently of s) the following holds: Given any tree T_{s−1} with 2^{s−2} · ⌈q^{1− \frac{1}{n}} ⌉ edges, the expected number of tries until a tree T with min\{2^{s−1} · ⌈q^{1− \frac{1}{n}} ⌉, N_{max}\} edges is constructed is

≤ \frac{32}{D} · (q + 1)^{2− \frac{2}{n}} .”

• Page 181, line 2 of Proposition 3.64: Replace “n · d^{n}” by “n! · d^{n}”.

• Page 191, line 14: Replace “Res_{k}^{K}(A)” by “Res_{k}^{K}(A′)”.

• Page 193, line 19: Replace “is is” by “is”.

• Page 217, line 16: Replace “in in” by “in”.

• Page 228, line -1: Replace “[Gau04]” by “[Gau04b]”.

• Page 229, line 4: Replace “Wie” by “Wir”.

Leipzig, May 7 2009 Claus Diem