\section{Computational Results}
\label{sec:results}

\subsection{Axis A: algebraic structure (H01--H07)}

The verification of the \secp{} parameters, the closed form of the GLV constants, the orbit counterexample and the
index-calculus probe were presented with the theory in Section~\ref{sec:secp}; Table~\ref{tab:opcount} gives the
operation counts behind hypothesis~\Hname{H03}, and Table~\ref{tab:ic} the index-calculus measurements behind
\Hname{H06}. The identity search tested \idTested{} candidate relations and found \idFound{}, all explained
(\idUnexplained{} unexplained; negative controls Q4~$=\idQfour$, Q5~$=\idQfive$ hits, against an expected chance count
of $10^{-73}$); the orbit-compatibility test failed for \orbitFails{} of \orbitTrials{} random pairs.

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Operation counts for one scalar multiplication on \secp{} (affine model, 200 random 256-bit scalars, mean $\pm$ sd). GLV sub-scalars never exceeded \glvKoneMax{} bits in \glvSamples{} samples.}
    \label{tab:opcount}
    \input{tables/scalar_mult_opcount}
\end{table}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Index-calculus probe on prime-field curves: decomposition of a random point as a sum of two factor-base points, $F=\{P: x(P)<p^{e}\}$ ($e=0.5$ or $0.6$). ``Oracle relations'' is the cost of collecting $|F|$ relations with a free decomposition oracle; ``Lin.\ alg.'' is $|F|^2$.}
    \label{tab:ic}
    \input{tables/index_calculus_probe}
\end{table}

\subsection{Axis A/B: ECDLP baselines and scaling (H08)}

Every one of the $3\,840$ generic and $2\,400$ $j=0$ instances was solved and verified (\scalingAllOk{} verified).
Figure~\ref{fig:scaling} shows group operations and wall-clock time against $n$ on log--log axes, and
Figure~\ref{fig:constants} the normalised cost $T/\sqrt n$; Table~\ref{tab:scaling} lists selected sizes and
Table~\ref{tab:fits} the fitted exponents.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{ecdlp_scaling.pdf}
  \caption{Empirical scaling of the generic ECDLP algorithms on random prime-order curves (60 instances per size,
  single thread, Apple M3 Ultra). Left: group operations with bootstrap 95\% intervals and the theoretical lines
  $\sqrt{\pi n/2}$ and $2\sqrt n$; right: wall-clock seconds. Generated by \code{analyze\_ecdlp.py}.}
  \label{fig:scaling}
\end{figure}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.85\textwidth]{ecdlp_constants.pdf}
  \caption{Normalised cost $T(n)/\sqrt n$ by size. The small-size excess of the distinguished-point variants is the
  post-collision overhead of 128 interleaved walks; above 44 bits the constants settle at their theoretical values.}
  \label{fig:constants}
\end{figure}

\begin{table}[htbp]
  \centering\scriptsize
    \caption{ECDLP baselines at selected sizes (mean group operations, bootstrap 95\% CI, normalised constant, theoretical constant, wall-clock).}
    \label{tab:scaling}
    \input{tables/ecdlp_scaling}
\end{table}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Empirical complexity exponents $\hat\alpha$ in $T(n)=a\,n^{\alpha}$ (least squares on size-level means, bootstrap 95\% CI). Fits on all sizes include the distinguished-point overhead at 20--28 bits; fits on $\ge 32$ bits and on iterations remove it.}
    \label{tab:fits}
    \input{tables/ecdlp_fits}
\end{table}

\paragraph{Exponents.} Restricted to $\ge 32$ bits, every algorithm has $\hat\alpha\in[\alphaGMin,\alphaGMax]$ with
confidence intervals containing or adjacent to $0.5$; on iterations the rho variants give $\hat\alpha$ between
$0.49$ and $0.50$. The log-factor model $a\,n^\alpha(\log n)^\beta$ does not improve the fit ($R^2>0.99$ already) and
returns $\beta$ indistinguishable from~0. There is no evidence of any deviation from square-root scaling in this
range, as expected.

\paragraph{Constants.} Pooled over the \rhoConstPooledN{} rho runs at $\ge\pooledMinBits$ bits, the number of
iterations is $\rhoConstPooled\,\sqrt n$ with 95\% CI $[\rhoConstPooledLo,\rhoConstPooledHi]$---the random-mapping
prediction is $\sqrt{\pi/2}=1.2533$, which the $r$-adding walk with $r\in\{20,128\}$ reproduces to three digits. With the
negation map the constant is $\negConstPooled$ $[\negConstPooledLo,\negConstPooledHi]$ against the prediction
$\sqrt{\pi/4}=0.8862$: a paired speed-up of $\negSpeedupPooled$ $[\negSpeedupPooledLo,\negSpeedupPooledHi]$ versus the
ideal $\sqrt2=1.414$, the shortfall being the residual fruitless-cycle handling and the look-ahead rejections
(Section~\ref{sec:dlog}). BSGS costs $\bsgsConstPooled\,\sqrt n$ $[\bsgsConstPooledLo,\bsgsConstPooledHi]$ group
operations (the engine's $x$-keyed table resolves $\pm j$, so the giant phase costs $n/(2m)$ and the total is
$1.5\sqrt n$ rather than $2\sqrt n$); the kangaroo on the full interval costs $\kangConstPooled\,\sqrt n$
$[\kangConstPooledLo,\kangConstPooledHi]$, close to the $2\sqrt w$ prediction. Floyd's cycle detection costs
$\floydConstBig\,\sqrt n$ (three evaluations per step) and Brent's $\brentConstBig\,\sqrt n$ at 48 bits, both as expected.

\subsection{Axis A: automorphism classes on $j=0$ curves (H04)}

Table~\ref{tab:j0} and Figure~\ref{fig:endo} give the result of hypothesis~\Hname{H04} on \jzeroPooledN{} paired
instances at $\ge\jzeroPooledMinBits$ bits (Apple M2 Ultra). In \emph{iterations}, the order-6 orbits deliver a
speed-up of $\jzeroNegAutSpeedup$ $[\jzeroNegAutSpeedupLo,\jzeroNegAutSpeedupHi]$ with $r=128$ and
$\jzeroNegAutRtwentySpeedup$ $[\jzeroNegAutRtwentySpeedupLo,\jzeroNegAutRtwentySpeedupHi]$ with $r=20$ against the ideal
$\sqrt6=2.449$; the normalised constant with $r=20$ is $\jzeroNegAutRtwentyConst\,\sqrt n$ against the prediction
$\sqrt{\pi/12}=0.5117$. The negation map alone and the $\phi$-orbits alone give $\jzeroNegSpeedup$ and
$\jzeroAutSpeedup$ against $\sqrt2$ and $\sqrt3$. Fruitless cycles are rare at these parameters
(\jzeroFruitlessPerK{} per 1000 iterations with $r=128$, \jzeroFruitlessPerKRtwenty{} with $r=20$) because the
look-ahead removes most 2-cycles before they form. The theory is therefore reproduced in the quantity it speaks
about.

In \emph{wall-clock time}, however, the picture is different: canonicalisation raises the cost of one iteration from
\jzeroPlainNsIter{}~ns (plain) to \jzeroNegNsIter{}~ns (negation), \jzeroAutNsIter{}~ns ($\phi$-orbits) and
\jzeroNegAutNsIter{}~ns (both) in our engine, so the measured wall-clock speed-ups are $\jzeroNegWall$,
$\jzeroAutWall$ and $\jzeroNegAutWall$ respectively---the order-6 trick roughly breaks even and the negation map alone
\emph{loses} time. The reason is implementation-specific and instructive: our canonical representative literally
computes $\min\{x,\beta x,\beta^2x\}$ and $\min\{y,p-y\}$ with two field multiplications and several Montgomery
conversions per step, whereas the record-setting implementations fold the comparison into the batched inversion
and use cheaper sign conventions \citep{bos2010negation,bernstein2011correct,bos2012solving}. The lesson for the
mandate's question A2 is that equivalence classes reduce \emph{iterations} by exactly the predicted factor, and that
turning this into a time saving is an engineering problem whose outcome depends on the per-step cost of
canonicalisation relative to a group addition (here about $0.6$--$1.1$ additions).

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{ecdlp_endomorphism.pdf}
  \caption{Endomorphism benchmarking on synthetic $j=0$ curves. Left: paired iteration speed-up over plain rho by
  size, with the ideal $\sqrt2$, $\sqrt3$, $\sqrt6$ (dashed); right: fruitless cycles detected per 1000 iterations.}
  \label{fig:endo}
\end{figure}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Equivalence classes on $j=0$ curves: iterations, paired iteration speed-up, cost per iteration and wall-clock speed-up (pooled over sizes $\ge \jzeroPooledMinBits$ bits for iterations, $\ge 40$ bits for time; Apple M2 Ultra, one thread).}
    \label{tab:j0}
    \input{tables/ecdlp_j0}
\end{table}

\subsection{Axis B: automated search over iteration functions (H09)}

The sweep over $r$ and mixed walks (\sweepConfigs{} configurations $\times$ \sweepInstances{} instances;
Figure~\ref{fig:sweep}, Table~\ref{tab:sweep}) reproduces Teske's findings: $r=2$ and $r=3$ walks need
$\sweepRtwo\,\sqrt n$ and $\sweepRthree\,\sqrt n$ iterations (the negative control behaves as a bad random mapping
should), $r\ge 8$ walks cluster around the random-mapping constant, and mixed walks make no measurable difference
at these sizes. The best cell (\sweepBestCfg{}, $\sweepBestConst$ $[\sweepBestLo,\sweepBestHi]$) is not
distinguishable from the random-mapping value given the width of the intervals, and no configuration is
significantly below it. This is the expected negative result: an automated search confined to generic iteration
functions can at best recover the random-mapping constant, which Shoup's bound makes the floor up to the class-size
factor. We record it as a rejected shortcut, with the positive by-product that the search ranks the designs
correctly and quantifies the penalty for small~$r$.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.85\textwidth]{ecdlp_sweep_r.pdf}
  \caption{Iteration-function design sweep: iterations$/\sqrt n$ against the number of partitions $r$ for plain and
  mixed $r$-adding walks at 36 and 40 bits (40 instances per cell, bootstrap 95\% CI). The dashed line is the
  random-mapping constant $\sqrt{\pi/2}$.}
  \label{fig:sweep}
\end{figure}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Iteration-function sweep (iterations$/\sqrt n$, mean of 40 instances per cell).}
    \label{tab:sweep}
    \input{tables/ecdlp_sweep_r}
\end{table}

\subsection{Axis B: parallel efficiency and time--memory trade-offs (H10, H11)}

Distinguished-point collision search on 56-bit instances scales to \parSpeedupSixteen$\times$ on 16 threads
(efficiency \parEffSixteen) and \parSpeedupMax$\times$ on \parMaxThreads{} threads (efficiency \parEffMax) of the
Apple M3 Ultra, with total group operations within a factor \parOpsRatioMax{} of the single-thread count
(Figure~\ref{fig:parallel}, Table~\ref{tab:parallel}); the efficiency loss at 28 threads reflects the mix of
performance and efficiency cores and the shared table, not an algorithmic limit. The time--memory study
(Figure~\ref{fig:tmto}, Table~\ref{tab:tmto}) confirms the deterministic BSGS trade-off $m+n/(2m)$ within
\tmtoBsgsMaxDev\% over memory sizes from $\tmtoBsgsMinM$ to $\tmtoBsgsMaxM$ entries, and shows the two-sided
trade-off of distinguished-point rho: dense distinguished points (density $2^{-2}$) store many points and pay a
restart cost per point, sparse ones (density $2^{-14}$) pay the post-collision overhead, and the optimum at 40 bits
lies between densities $2^{-8}$ and $2^{-10}$, where the cost is within 5\% of $\sqrt{\pi n/2}$ with one to four thousand stored points.

\begin{figure}[htbp]
  \centering
  \includegraphics[width=0.95\textwidth]{ecdlp_parallel.pdf}
  \caption{Parallel collision search (56-bit instances, rho with negation map, Apple M3 Ultra, 12 instances per point): throughput speed-up and total work relative to one thread.}
  \label{fig:parallel}
\end{figure}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{ecdlp_tmto.pdf}
  \caption{Time--memory trade-off. Left: BSGS at 36 bits against the memory $m$ (dashed: $m+n/(2m)$). Right: distinguished-point rho at 40 bits against the number of stored points (labels: DP density), with bootstrap 95\% intervals; dashed: $\sqrt{\pi n/2}$.}
  \label{fig:tmto}
\end{figure}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Parallel efficiency of distinguished-point rho (56 bits, negation map, Apple M3 Ultra).}
    \label{tab:parallel}
    \input{tables/ecdlp_parallel}
\end{table}

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Time--memory trade-off measurements (means over 20 instances).}
    \label{tab:tmto}
    \input{tables/ecdlp_tmto}
\end{table}

\subsection{Axis B: preprocessing (H12)}

Table~\ref{tab:preproc} reports the Python reference experiment on 22- and 26-bit groups (\ppInstances{} instances per
cell). The online cost is $\ppRatioMean\,\sqrt{n/T}$ on average (range \ppRatioMin--\ppRatioMax{} across $T$ from
$2^4$ to $2^{12}$), so the per-instance speed-up over plain rho grows as $\sqrt T$ and reaches \ppSpeedupMax$\times$ at
$T=2^{12}$---at the price of an offline phase of about $\sqrt{nT}$ operations. The constant $\approx 1.5$ rather
than $1$ comes from the walk-length distribution (a walk from $Q$ must travel to a distinguished point \emph{and}
that point must have been stored) and matches the heuristic analysis of \citet{bernstein2013nonuniform}. The
trade-off is exactly the $ST^2=\tilde\Omega(n)$ curve of \citet{corrigangibbs2018discrete} and offers nothing below
$\sqrt n$ in total work.

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Discrete logarithms with preprocessing (Python reference, 20-partition walk independent of the target).}
    \label{tab:preproc}
    \input{tables/preprocessing}
\end{table}

\subsection{Axis B: signature benchmarks (H13, H14)}

Table~\ref{tab:sig-impl} and Figure~\ref{fig:sig} summarise the signature measurements. Three results stand out.
(i)~Implementation choice spans three orders of magnitude: the pure-Python reference verifies a BIP340 signature
in \sigPurePythonSchnorrVerifyMs~ms, \libsecp{} in \sigSchnorrVerifyLibsecpUs~$\mu$s
(\sigPurePythonVsLibsecp$\times$), with \kk{} at \sigSchnorrVerifyKkUs~$\mu$s and coincurve (\libsecp{}
through Python) essentially at the C speed. (ii)~ECDSA and Schnorr verification cost the same in \libsecp{} within
5\%, and signing differs between libraries more than between schemes: \kk{} signs faster (table-based
fixed-base multiplication) while \libsecp{} verifies $1.9\times$ faster (variable-base multiplication with GLV and
its optimised field arithmetic). (iii)~Batch verification with our Pippenger multi-scalar multiplication reaches
\batchBestUs~$\mu$s per signature at batch size \batchBestSize, a speed-up of $\batchSpeedupK$
$[\batchSpeedupKLo,\batchSpeedupKHi]$ over single verification in the same arithmetic and $\batchSpeedupLib\times$ over
\libsecp{}'s single verification; Straus interleaving plateaus near $2\times$ from batch size 32, and Pippenger
overtakes it only beyond about 256 signatures. About $3~\mu$s per signature of non-MSM work (the square root in
\code{lift\_x} and the tagged hash) bounds the attainable gain; the batch with one corrupted signature was rejected by
every back-end. The same curves on the Apple M3 Ultra are $1.3\times$ slower with identical shape. All of this is
known in kind \citep{bernstein2012high,wuille2020bip340}; the contribution is the measured, operation-counted
curve for \secp{} and the identification of the saturation mechanism.

\begin{table}[htbp]
  \centering\footnotesize
    \caption{Signature implementations: median time per operation in microseconds (single thread, 7 repetitions of 2\,000 operations; laptop Apple M5 Max unless stated).}
    \label{tab:sig-impl}
    \input{tables/sig_implementations}
\end{table}

\begin{figure}[htbp]
  \centering
  \includegraphics[width=\textwidth]{sig_batch_verification.pdf}
  \caption{BIP340 batch verification: time per signature against batch size for Straus, Pippenger and the \kk{} linear-combination routines on two hosts, with the single-verification reference lines, and the speed-up with bootstrap 95\% intervals. Generated by \code{figures/make\_sig\_figures.py}.}
  \label{fig:sig}
\end{figure}

\input{sections/10b_results_sha}