\section{Generic and Algebraic Discrete-Logarithm Algorithms}
\label{sec:dlog}

This section states the algorithms we implemented (twice: a transparent Python reference and a Rust engine) with their
exact cost models; Section~\ref{sec:results} compares the models with measurements. Throughout, $G$ has prime order
$n$ and $Q=[d]G$.

\subsection{Baby-step giant-step}

Shanks' method \citep{shanks1971class} stores $m$ baby steps $\{[j]G: 0\le j<m\}$ in a hash table and walks giant
steps $Q-[im]G$ until a match $Q-[im]G=[j]G$ gives $d=im+j$. With $m=\lceil\sqrt n\rceil$ the cost is at most
$m+\lceil n/m\rceil\approx 2\sqrt n$ group operations and $\sqrt n$ table entries; with memory $m$ the time is
$m + n/m$, a deterministic time--memory trade-off. Two refinements matter: interleaving baby and giant steps halves
the expected (not worst-case) cost for uniformly random $d$, and using the negation map on the baby-step table saves a
further $\sqrt2$ \citep{bernstein2012two}. We benchmark the plain variant as the deterministic baseline.

\subsection{Pollard's rho and $r$-adding walks}

Pollard's rho \citep{pollard1978monte} iterates a pseudo-random map $f$ on $\langle G\rangle$ whose values are tracked as
$a_iG+b_iQ$; a collision $X_i=X_j$ with $b_i\ne b_j$ gives $d=(a_i-a_j)/(b_j-b_i)\bmod n$. If $f$ behaved as a uniformly
random mapping, the expected number of iterations before the first repetition would be $\sqrt{\pi n/2}\approx 1.2533\sqrt n$
\citep{flajolet1990random}. Pollard's original three-partition map is measurably worse than random; Teske's $r$-adding
walk $f(X)=X+M_{h(X)}$ with $r\approx 20$ precomputed multipliers $M_j=u_jG+v_jQ$ is within a few percent of the
random-mapping constant \citep{teske1998speeding,teske2001random}, and mixed walks that include occasional doublings
close the remaining gap. Cycle detection by Floyd's tortoise-and-hare costs three evaluations per step; Brent's
method \citep{brent1980improved} costs about one. Our Python reference implements Floyd; the Rust engine implements
Floyd, Brent and the distinguished-point variant below.

\subsection{Distinguished points and parallel collision search}

\citet{vanoorschot1999parallel} replace cycle detection by storing only \emph{distinguished points} (those whose
$x$-coordinate has $\theta^{-1}$ specific bits equal to zero) in a shared table; $t$ processors each run independent
walks from random starts $a_0G+b_0Q$, report distinguished points, and a collision between two walks with different
$(a,b)$ solves the instance. The expected total work is $\sqrt{\pi n/2}+ t/\theta$ group operations (the second term is
the extra distance walked after the collision point), memory is about $\theta\sqrt{\pi n/2}$ entries, and the
speed-up is linear in $t$ when $t/\theta\ll\sqrt n$. This is the algorithm behind every ECDLP record
\citep{bos2012solving,bernstein2016faster,bailey2009breaking}.

\subsection{Equivalence classes: negation map and automorphisms}

Replacing points by classes $\{\pm X\}$ halves the effective group size and divides the expected iterations by
$\sqrt2$; for the $j=0$ family the order-6 classes divide them by $\sqrt6$. The price is fruitless cycles: on classes,
the walk $X\mapsto X+M_j$ has probability about $1/(2r)$ of returning to $X$ after two steps (when the canonical
representative flips sign), creating 2-cycles that must be detected by a one-step look-ahead and escaped
\citep{bos2010negation,bernstein2011correct}; longer fruitless cycles ($4,6,\dots$) occur with probability $O(r^{-k/2})$
and are handled by periodic checks and a doubling escape. Our engine implements the look-ahead and a bounded-length
check and reports the number of cycles encountered.

\subsection{Pollard's kangaroo for intervals}

When $d$ is known to lie in an interval of width $w$, Pollard's kangaroo (lambda) method \citep{pollard1978monte,pollard2000kangaroos}
runs a tame kangaroo from a known point and a wild one from $Q$, both jumping by powers of two of mean $\approx\sqrt w/2$;
the wild kangaroo is caught at a trap in expected $\approx 2\sqrt w$ jumps. The van Oorschot--Wiener herd version is
parallel and uses distinguished points; \citet{galbraith2010interval} improve the constant to $\approx 1.71\sqrt w$ with
the negation map. We use the kangaroo as a second, structurally different baseline (and as the reason interval
restrictions on nonces or keys are dangerous).

\subsection{Pohlig--Hellman}

If $\ord(G)=\prod q_i^{e_i}$ is smooth, the DLP reduces to the prime-order subgroups and costs
$\sum_i e_i(\sqrt{q_i}+\log n)$ \citep{pohlig1978improved}; this is why $n$ must be prime (or have a large prime factor)
and why the cofactor~1 of \secp{} matters. Our reference implements it on small composite-order curves for completeness.

\subsection{Preprocessing (non-uniform) algorithms}

\citet{bernstein2013nonuniform} observe that a one-time table of $T$ distinguished points, each ending a walk of
length $W$ from a known multiple of $G$, lets every later instance be solved in about $n/(TW)$ online operations;
choosing $W=\sqrt{n/T}$ gives online cost $\sqrt{n/T}$ after $\sqrt{nT}$ preprocessing. \citet{corrigangibbs2018discrete}
prove that any generic algorithm with $S$ bits of advice and $T$ online queries satisfies $ST^2=\tilde\Omega(n)$, so this
trade-off is optimal up to logarithmic factors. Hypothesis~\Hname{H12} measures the constant.

\subsection{Lower bounds and what they rule out}

Shoup's theorem \citep{shoup1997lower} is unconditional within the generic-group model: an algorithm that only uses the
group operation (and equality tests) on $\langle G\rangle$ of prime order $n$ succeeds with probability $O(m^2/n)$ after
$m$ operations. Every algorithm above is generic, so none can have complexity $o(\sqrt n)$; constant-factor gains
from equivalence classes are the only room left (classes of size $c$ give at most $\sqrt c$, and $c\le 6$ for an
elliptic curve over $\F_p$ with $p>3$ since $\lvert\Aut(E)\rvert\le 6$). The automated search of
hypothesis~\Hname{H09} lives entirely in this model and therefore cannot find a shortcut; what it can find is a better
constant, and we report that it does not.

\subsection{Cost model and empirical complexity}

For each run we record the number of group additions and doublings, the number of field inversions (one per affine
operation in the reference; amortised in the engine), wall-clock time, CPU time summed over threads, table size and
peak resident memory. The empirical model
\begin{equation}
  T(n) = a\,n^{\alpha}(\log_2 n)^{\beta}
  \label{eq:empirical}
\end{equation}
is fitted by least squares on $\log T$ with $\beta$ either free or fixed to~0, and the speed-up of a candidate over a
baseline at size $n$ is $S(n)=T_{\text{baseline}}(n)/T_{\text{candidate}}(n)$ with a bootstrap confidence interval over
instances. For rho-type algorithms the number of iterations until collision has a Rayleigh-like distribution with
coefficient of variation $\sqrt{(4-\pi)/\pi}\approx 0.52$, so at least 20 instances per size are needed for a
$\pm 23\%$ standard error on the mean; we use 20--40.