1\section{Computational Results}2\label{sec:results}34\subsection{Axis A: algebraic structure (H01--H07)}56The verification of the \secp{} parameters, the closed form of the GLV constants, the orbit counterexample and the7index-calculus probe were presented with the theory in Section~\ref{sec:secp}; Table~\ref{tab:opcount} gives the8operation counts behind hypothesis~\Hname{H03}, and Table~\ref{tab:ic} the index-calculus measurements behind9\Hname{H06}. The identity search tested \idTested{} candidate relations and found \idFound{}, all explained10(\idUnexplained{} unexplained; negative controls Q4~$=\idQfour$, Q5~$=\idQfive$ hits, against an expected chance count11of $10^{-73}$); the orbit-compatibility test failed for \orbitFails{} of \orbitTrials{} random pairs.1213\begin{table}[htbp]14 \centering\footnotesize15 \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.}16 \label{tab:opcount}17 \input{tables/scalar_mult_opcount}18\end{table}1920\begin{table}[htbp]21 \centering\footnotesize22 \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$.}23 \label{tab:ic}24 \input{tables/index_calculus_probe}25\end{table}2627\subsection{Axis A/B: ECDLP baselines and scaling (H08)}2829Every one of the $3\,840$ generic and $2\,400$ $j=0$ instances was solved and verified (\scalingAllOk{} verified).30Figure~\ref{fig:scaling} shows group operations and wall-clock time against $n$ on log--log axes, and31Figure~\ref{fig:constants} the normalised cost $T/\sqrt n$; Table~\ref{tab:scaling} lists selected sizes and32Table~\ref{tab:fits} the fitted exponents.3334\begin{figure}[htbp]35 \centering36 \includegraphics[width=\textwidth]{ecdlp_scaling.pdf}37 \caption{Empirical scaling of the generic ECDLP algorithms on random prime-order curves (60 instances per size,38 single thread, Apple M3 Ultra). Left: group operations with bootstrap 95\% intervals and the theoretical lines39 $\sqrt{\pi n/2}$ and $2\sqrt n$; right: wall-clock seconds. Generated by \code{analyze\_ecdlp.py}.}40 \label{fig:scaling}41\end{figure}4243\begin{figure}[htbp]44 \centering45 \includegraphics[width=0.85\textwidth]{ecdlp_constants.pdf}46 \caption{Normalised cost $T(n)/\sqrt n$ by size. The small-size excess of the distinguished-point variants is the47 post-collision overhead of 128 interleaved walks; above 44 bits the constants settle at their theoretical values.}48 \label{fig:constants}49\end{figure}5051\begin{table}[htbp]52 \centering\scriptsize53 \caption{ECDLP baselines at selected sizes (mean group operations, bootstrap 95\% CI, normalised constant, theoretical constant, wall-clock).}54 \label{tab:scaling}55 \input{tables/ecdlp_scaling}56\end{table}5758\begin{table}[htbp]59 \centering\footnotesize60 \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.}61 \label{tab:fits}62 \input{tables/ecdlp_fits}63\end{table}6465\paragraph{Exponents.} Restricted to $\ge 32$ bits, every algorithm has $\hat\alpha\in[\alphaGMin,\alphaGMax]$ with66confidence intervals containing or adjacent to $0.5$; on iterations the rho variants give $\hat\alpha$ between67$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) and68returns $\beta$ indistinguishable from~0. There is no evidence of any deviation from square-root scaling in this69range, as expected.7071\paragraph{Constants.} Pooled over the \rhoConstPooledN{} rho runs at $\ge\pooledMinBits$ bits, the number of72iterations is $\rhoConstPooled\,\sqrt n$ with 95\% CI $[\rhoConstPooledLo,\rhoConstPooledHi]$---the random-mapping73prediction is $\sqrt{\pi/2}=1.2533$, which the $r$-adding walk with $r\in\{20,128\}$ reproduces to three digits. With the74negation map the constant is $\negConstPooled$ $[\negConstPooledLo,\negConstPooledHi]$ against the prediction75$\sqrt{\pi/4}=0.8862$: a paired speed-up of $\negSpeedupPooled$ $[\negSpeedupPooledLo,\negSpeedupPooledHi]$ versus the76ideal $\sqrt2=1.414$, the shortfall being the residual fruitless-cycle handling and the look-ahead rejections77(Section~\ref{sec:dlog}). BSGS costs $\bsgsConstPooled\,\sqrt n$ $[\bsgsConstPooledLo,\bsgsConstPooledHi]$ group78operations (the engine's $x$-keyed table resolves $\pm j$, so the giant phase costs $n/(2m)$ and the total is79$1.5\sqrt n$ rather than $2\sqrt n$); the kangaroo on the full interval costs $\kangConstPooled\,\sqrt n$80$[\kangConstPooledLo,\kangConstPooledHi]$, close to the $2\sqrt w$ prediction. Floyd's cycle detection costs81$\floydConstBig\,\sqrt n$ (three evaluations per step) and Brent's $\brentConstBig\,\sqrt n$ at 48 bits, both as expected.8283\subsection{Axis A: automorphism classes on $j=0$ curves (H04)}8485Table~\ref{tab:j0} and Figure~\ref{fig:endo} give the result of hypothesis~\Hname{H04} on \jzeroPooledN{} paired86instances at $\ge\jzeroPooledMinBits$ bits (Apple M2 Ultra). In \emph{iterations}, the order-6 orbits deliver a87speed-up of $\jzeroNegAutSpeedup$ $[\jzeroNegAutSpeedupLo,\jzeroNegAutSpeedupHi]$ with $r=128$ and88$\jzeroNegAutRtwentySpeedup$ $[\jzeroNegAutRtwentySpeedupLo,\jzeroNegAutRtwentySpeedupHi]$ with $r=20$ against the ideal89$\sqrt6=2.449$; the normalised constant with $r=20$ is $\jzeroNegAutRtwentyConst\,\sqrt n$ against the prediction90$\sqrt{\pi/12}=0.5117$. The negation map alone and the $\phi$-orbits alone give $\jzeroNegSpeedup$ and91$\jzeroAutSpeedup$ against $\sqrt2$ and $\sqrt3$. Fruitless cycles are rare at these parameters92(\jzeroFruitlessPerK{} per 1000 iterations with $r=128$, \jzeroFruitlessPerKRtwenty{} with $r=20$) because the93look-ahead removes most 2-cycles before they form. The theory is therefore reproduced in the quantity it speaks94about.9596In \emph{wall-clock time}, however, the picture is different: canonicalisation raises the cost of one iteration from97\jzeroPlainNsIter{}~ns (plain) to \jzeroNegNsIter{}~ns (negation), \jzeroAutNsIter{}~ns ($\phi$-orbits) and98\jzeroNegAutNsIter{}~ns (both) in our engine, so the measured wall-clock speed-ups are $\jzeroNegWall$,99$\jzeroAutWall$ and $\jzeroNegAutWall$ respectively---the order-6 trick roughly breaks even and the negation map alone100\emph{loses} time. The reason is implementation-specific and instructive: our canonical representative literally101computes $\min\{x,\beta x,\beta^2x\}$ and $\min\{y,p-y\}$ with two field multiplications and several Montgomery102conversions per step, whereas the record-setting implementations fold the comparison into the batched inversion103and use cheaper sign conventions \citep{bos2010negation,bernstein2011correct,bos2012solving}. The lesson for the104mandate's question A2 is that equivalence classes reduce \emph{iterations} by exactly the predicted factor, and that105turning this into a time saving is an engineering problem whose outcome depends on the per-step cost of106canonicalisation relative to a group addition (here about $0.6$--$1.1$ additions).107108\begin{figure}[htbp]109 \centering110 \includegraphics[width=\textwidth]{ecdlp_endomorphism.pdf}111 \caption{Endomorphism benchmarking on synthetic $j=0$ curves. Left: paired iteration speed-up over plain rho by112 size, with the ideal $\sqrt2$, $\sqrt3$, $\sqrt6$ (dashed); right: fruitless cycles detected per 1000 iterations.}113 \label{fig:endo}114\end{figure}115116\begin{table}[htbp]117 \centering\footnotesize118 \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).}119 \label{tab:j0}120 \input{tables/ecdlp_j0}121\end{table}122123\subsection{Axis B: automated search over iteration functions (H09)}124125The sweep over $r$ and mixed walks (\sweepConfigs{} configurations $\times$ \sweepInstances{} instances;126Figure~\ref{fig:sweep}, Table~\ref{tab:sweep}) reproduces Teske's findings: $r=2$ and $r=3$ walks need127$\sweepRtwo\,\sqrt n$ and $\sweepRthree\,\sqrt n$ iterations (the negative control behaves as a bad random mapping128should), $r\ge 8$ walks cluster around the random-mapping constant, and mixed walks make no measurable difference129at these sizes. The best cell (\sweepBestCfg{}, $\sweepBestConst$ $[\sweepBestLo,\sweepBestHi]$) is not130distinguishable from the random-mapping value given the width of the intervals, and no configuration is131significantly below it. This is the expected negative result: an automated search confined to generic iteration132functions can at best recover the random-mapping constant, which Shoup's bound makes the floor up to the class-size133factor. We record it as a rejected shortcut, with the positive by-product that the search ranks the designs134correctly and quantifies the penalty for small~$r$.135136\begin{figure}[htbp]137 \centering138 \includegraphics[width=0.85\textwidth]{ecdlp_sweep_r.pdf}139 \caption{Iteration-function design sweep: iterations$/\sqrt n$ against the number of partitions $r$ for plain and140 mixed $r$-adding walks at 36 and 40 bits (40 instances per cell, bootstrap 95\% CI). The dashed line is the141 random-mapping constant $\sqrt{\pi/2}$.}142 \label{fig:sweep}143\end{figure}144145\begin{table}[htbp]146 \centering\footnotesize147 \caption{Iteration-function sweep (iterations$/\sqrt n$, mean of 40 instances per cell).}148 \label{tab:sweep}149 \input{tables/ecdlp_sweep_r}150\end{table}151152\subsection{Axis B: parallel efficiency and time--memory trade-offs (H10, H11)}153154Distinguished-point collision search on 56-bit instances scales to \parSpeedupSixteen$\times$ on 16 threads155(efficiency \parEffSixteen) and \parSpeedupMax$\times$ on \parMaxThreads{} threads (efficiency \parEffMax) of the156Apple M3 Ultra, with total group operations within a factor \parOpsRatioMax{} of the single-thread count157(Figure~\ref{fig:parallel}, Table~\ref{tab:parallel}); the efficiency loss at 28 threads reflects the mix of158performance and efficiency cores and the shared table, not an algorithmic limit. The time--memory study159(Figure~\ref{fig:tmto}, Table~\ref{tab:tmto}) confirms the deterministic BSGS trade-off $m+n/(2m)$ within160\tmtoBsgsMaxDev\% over memory sizes from $\tmtoBsgsMinM$ to $\tmtoBsgsMaxM$ entries, and shows the two-sided161trade-off of distinguished-point rho: dense distinguished points (density $2^{-2}$) store many points and pay a162restart cost per point, sparse ones (density $2^{-14}$) pay the post-collision overhead, and the optimum at 40 bits163lies 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.164165\begin{figure}[htbp]166 \centering167 \includegraphics[width=0.95\textwidth]{ecdlp_parallel.pdf}168 \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.}169 \label{fig:parallel}170\end{figure}171172\begin{figure}[htbp]173 \centering174 \includegraphics[width=\textwidth]{ecdlp_tmto.pdf}175 \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}$.}176 \label{fig:tmto}177\end{figure}178179\begin{table}[htbp]180 \centering\footnotesize181 \caption{Parallel efficiency of distinguished-point rho (56 bits, negation map, Apple M3 Ultra).}182 \label{tab:parallel}183 \input{tables/ecdlp_parallel}184\end{table}185186\begin{table}[htbp]187 \centering\footnotesize188 \caption{Time--memory trade-off measurements (means over 20 instances).}189 \label{tab:tmto}190 \input{tables/ecdlp_tmto}191\end{table}192193\subsection{Axis B: preprocessing (H12)}194195Table~\ref{tab:preproc} reports the Python reference experiment on 22- and 26-bit groups (\ppInstances{} instances per196cell). The online cost is $\ppRatioMean\,\sqrt{n/T}$ on average (range \ppRatioMin--\ppRatioMax{} across $T$ from197$2^4$ to $2^{12}$), so the per-instance speed-up over plain rho grows as $\sqrt T$ and reaches \ppSpeedupMax$\times$ at198$T=2^{12}$---at the price of an offline phase of about $\sqrt{nT}$ operations. The constant $\approx 1.5$ rather199than $1$ comes from the walk-length distribution (a walk from $Q$ must travel to a distinguished point \emph{and}200that point must have been stored) and matches the heuristic analysis of \citet{bernstein2013nonuniform}. The201trade-off is exactly the $ST^2=\tilde\Omega(n)$ curve of \citet{corrigangibbs2018discrete} and offers nothing below202$\sqrt n$ in total work.203204\begin{table}[htbp]205 \centering\footnotesize206 \caption{Discrete logarithms with preprocessing (Python reference, 20-partition walk independent of the target).}207 \label{tab:preproc}208 \input{tables/preprocessing}209\end{table}210211\subsection{Axis B: signature benchmarks (H13, H14)}212213Table~\ref{tab:sig-impl} and Figure~\ref{fig:sig} summarise the signature measurements. Three results stand out.214(i)~Implementation choice spans three orders of magnitude: the pure-Python reference verifies a BIP340 signature215in \sigPurePythonSchnorrVerifyMs~ms, \libsecp{} in \sigSchnorrVerifyLibsecpUs~$\mu$s216(\sigPurePythonVsLibsecp$\times$), with \kk{} at \sigSchnorrVerifyKkUs~$\mu$s and coincurve (\libsecp{}217through Python) essentially at the C speed. (ii)~ECDSA and Schnorr verification cost the same in \libsecp{} within2185\%, and signing differs between libraries more than between schemes: \kk{} signs faster (table-based219fixed-base multiplication) while \libsecp{} verifies $1.9\times$ faster (variable-base multiplication with GLV and220its optimised field arithmetic). (iii)~Batch verification with our Pippenger multi-scalar multiplication reaches221\batchBestUs~$\mu$s per signature at batch size \batchBestSize, a speed-up of $\batchSpeedupK$222$[\batchSpeedupKLo,\batchSpeedupKHi]$ over single verification in the same arithmetic and $\batchSpeedupLib\times$ over223\libsecp{}'s single verification; Straus interleaving plateaus near $2\times$ from batch size 32, and Pippenger224overtakes it only beyond about 256 signatures. About $3~\mu$s per signature of non-MSM work (the square root in225\code{lift\_x} and the tagged hash) bounds the attainable gain; the batch with one corrupted signature was rejected by226every back-end. The same curves on the Apple M3 Ultra are $1.3\times$ slower with identical shape. All of this is227known in kind \citep{bernstein2012high,wuille2020bip340}; the contribution is the measured, operation-counted228curve for \secp{} and the identification of the saturation mechanism.229230\begin{table}[htbp]231 \centering\footnotesize232 \caption{Signature implementations: median time per operation in microseconds (single thread, 7 repetitions of 2\,000 operations; laptop Apple M5 Max unless stated).}233 \label{tab:sig-impl}234 \input{tables/sig_implementations}235\end{table}236237\begin{figure}[htbp]238 \centering239 \includegraphics[width=\textwidth]{sig_batch_verification.pdf}240 \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}.}241 \label{fig:sig}242\end{figure}243244\input{sections/10b_results_sha}245