1\section{Generic and Algebraic Discrete-Logarithm Algorithms}2\label{sec:dlog}34This section states the algorithms we implemented (twice: a transparent Python reference and a Rust engine) with their5exact cost models; Section~\ref{sec:results} compares the models with measurements. Throughout, $G$ has prime order6$n$ and $Q=[d]G$.78\subsection{Baby-step giant-step}910Shanks' method \citep{shanks1971class} stores $m$ baby steps $\{[j]G: 0\le j<m\}$ in a hash table and walks giant11steps $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 most12$m+\lceil n/m\rceil\approx 2\sqrt n$ group operations and $\sqrt n$ table entries; with memory $m$ the time is13$m + n/m$, a deterministic time--memory trade-off. Two refinements matter: interleaving baby and giant steps halves14the expected (not worst-case) cost for uniformly random $d$, and using the negation map on the baby-step table saves a15further $\sqrt2$ \citep{bernstein2012two}. We benchmark the plain variant as the deterministic baseline.1617\subsection{Pollard's rho and $r$-adding walks}1819Pollard's rho \citep{pollard1978monte} iterates a pseudo-random map $f$ on $\langle G\rangle$ whose values are tracked as20$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 uniformly21random mapping, the expected number of iterations before the first repetition would be $\sqrt{\pi n/2}\approx 1.2533\sqrt n$22\citep{flajolet1990random}. Pollard's original three-partition map is measurably worse than random; Teske's $r$-adding23walk $f(X)=X+M_{h(X)}$ with $r\approx 20$ precomputed multipliers $M_j=u_jG+v_jQ$ is within a few percent of the24random-mapping constant \citep{teske1998speeding,teske2001random}, and mixed walks that include occasional doublings25close the remaining gap. Cycle detection by Floyd's tortoise-and-hare costs three evaluations per step; Brent's26method \citep{brent1980improved} costs about one. Our Python reference implements Floyd; the Rust engine implements27Floyd, Brent and the distinguished-point variant below.2829\subsection{Distinguished points and parallel collision search}3031\citet{vanoorschot1999parallel} replace cycle detection by storing only \emph{distinguished points} (those whose32$x$-coordinate has $\theta^{-1}$ specific bits equal to zero) in a shared table; $t$ processors each run independent33walks from random starts $a_0G+b_0Q$, report distinguished points, and a collision between two walks with different34$(a,b)$ solves the instance. The expected total work is $\sqrt{\pi n/2}+ t/\theta$ group operations (the second term is35the extra distance walked after the collision point), memory is about $\theta\sqrt{\pi n/2}$ entries, and the36speed-up is linear in $t$ when $t/\theta\ll\sqrt n$. This is the algorithm behind every ECDLP record37\citep{bos2012solving,bernstein2016faster,bailey2009breaking}.3839\subsection{Equivalence classes: negation map and automorphisms}4041Replacing points by classes $\{\pm X\}$ halves the effective group size and divides the expected iterations by42$\sqrt2$; for the $j=0$ family the order-6 classes divide them by $\sqrt6$. The price is fruitless cycles: on classes,43the walk $X\mapsto X+M_j$ has probability about $1/(2r)$ of returning to $X$ after two steps (when the canonical44representative flips sign), creating 2-cycles that must be detected by a one-step look-ahead and escaped45\citep{bos2010negation,bernstein2011correct}; longer fruitless cycles ($4,6,\dots$) occur with probability $O(r^{-k/2})$46and are handled by periodic checks and a doubling escape. Our engine implements the look-ahead and a bounded-length47check and reports the number of cycles encountered.4849\subsection{Pollard's kangaroo for intervals}5051When $d$ is known to lie in an interval of width $w$, Pollard's kangaroo (lambda) method \citep{pollard1978monte,pollard2000kangaroos}52runs 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$;53the wild kangaroo is caught at a trap in expected $\approx 2\sqrt w$ jumps. The van Oorschot--Wiener herd version is54parallel and uses distinguished points; \citet{galbraith2010interval} improve the constant to $\approx 1.71\sqrt w$ with55the negation map. We use the kangaroo as a second, structurally different baseline (and as the reason interval56restrictions on nonces or keys are dangerous).5758\subsection{Pohlig--Hellman}5960If $\ord(G)=\prod q_i^{e_i}$ is smooth, the DLP reduces to the prime-order subgroups and costs61$\sum_i e_i(\sqrt{q_i}+\log n)$ \citep{pohlig1978improved}; this is why $n$ must be prime (or have a large prime factor)62and why the cofactor~1 of \secp{} matters. Our reference implements it on small composite-order curves for completeness.6364\subsection{Preprocessing (non-uniform) algorithms}6566\citet{bernstein2013nonuniform} observe that a one-time table of $T$ distinguished points, each ending a walk of67length $W$ from a known multiple of $G$, lets every later instance be solved in about $n/(TW)$ online operations;68choosing $W=\sqrt{n/T}$ gives online cost $\sqrt{n/T}$ after $\sqrt{nT}$ preprocessing. \citet{corrigangibbs2018discrete}69prove that any generic algorithm with $S$ bits of advice and $T$ online queries satisfies $ST^2=\tilde\Omega(n)$, so this70trade-off is optimal up to logarithmic factors. Hypothesis~\Hname{H12} measures the constant.7172\subsection{Lower bounds and what they rule out}7374Shoup's theorem \citep{shoup1997lower} is unconditional within the generic-group model: an algorithm that only uses the75group operation (and equality tests) on $\langle G\rangle$ of prime order $n$ succeeds with probability $O(m^2/n)$ after76$m$ operations. Every algorithm above is generic, so none can have complexity $o(\sqrt n)$; constant-factor gains77from equivalence classes are the only room left (classes of size $c$ give at most $\sqrt c$, and $c\le 6$ for an78elliptic curve over $\F_p$ with $p>3$ since $\lvert\Aut(E)\rvert\le 6$). The automated search of79hypothesis~\Hname{H09} lives entirely in this model and therefore cannot find a shortcut; what it can find is a better80constant, and we report that it does not.8182\subsection{Cost model and empirical complexity}8384For each run we record the number of group additions and doublings, the number of field inversions (one per affine85operation in the reference; amortised in the engine), wall-clock time, CPU time summed over threads, table size and86peak resident memory. The empirical model87\begin{equation}88 T(n) = a\,n^{\alpha}(\log_2 n)^{\beta}89 \label{eq:empirical}90\end{equation}91is fitted by least squares on $\log T$ with $\beta$ either free or fixed to~0, and the speed-up of a candidate over a92baseline at size $n$ is $S(n)=T_{\text{baseline}}(n)/T_{\text{candidate}}(n)$ with a bootstrap confidence interval over93instances. For rho-type algorithms the number of iterations until collision has a Rayleigh-like distribution with94coefficient of variation $\sqrt{(4-\pi)/\pi}\approx 0.52$, so at least 20 instances per size are needed for a95$\pm 23\%$ standard error on the mean; we use 20--40.96