\section{Mathematical Structure of secp256k1}
\label{sec:secp}

\subsection{Verified domain parameters}

Table~\ref{tab:secp-params} lists the standardised parameters \citep{certicom2010sec2} together with the
derived quantities used in this paper. Every entry was computed twice with exact arithmetic---in our pure-Python
library and in PARI/GP~2.19---and the two implementations agree on all fourteen named checks
(\code{results/baselines/secp256k1\_facts.json}, hypothesis~\Hname{H01}).

\begin{table}[htbp]
  \centering\footnotesize
      \caption{secp256k1 parameters and derived algebraic invariants (all verified exactly in Python and PARI/GP).}
    \label{tab:secp-params}
  \resizebox{\textwidth}{!}{%
    \begin{tabular}{@{}llp{8.2cm}@{}}
      \toprule
      Quantity & Symbol & Value / verified property \\
      \midrule
      Field prime & $p$ & $2^{256}-2^{32}-977$; prime; $p\equiv 1 \pmod 3$, $p\equiv 3 \pmod 4$ \\
      Curve & $E$ & $y^2 = x^3 + 7$; $a=0$, $b=7$; $\Delta\ne 0$; $j(E)=0$ \\
      Group order & $n$ & \code{FFFF\ldots{}BAAEDCE6AF48A03BBFD25E8CD0364141}; prime; $\#E(\F_p)=n$ (SEA re-count) \\
      Cofactor & $h$ & $1$ \\
      Generator & $G$ & $x_G=$\code{79BE667E\ldots{}F81798}, $y_G=$\code{483ADA77\ldots{}10D4B8}; $G\in E$; $[n]G=\Oinf$ \\
      Trace of Frobenius & $t$ & $p+1-n = 432420386565659656852420866390673177327$ ($\approx 2^{128.3}$, $t^2\le 4p$) \\
      CM discriminant & & $t^2-4p = -3f^2$, $f = 303414439467246543595250775667605759171$ \\
      Endomorphism & $\beta$ & \code{7AE96A2B\ldots{}719501EE}; $\beta^3\equiv 1$, $\beta^2+\beta+1\equiv 0 \pmod p$ \\
      Eigenvalue & $\lambda$ & \code{5363AD4C\ldots{}1B23BD72}; $\lambda^3\equiv 1$, $\lambda^2+\lambda+1\equiv 0 \pmod n$; $(\beta x_G, y_G) = [\lambda]G$ \\
      GLV basis & $(a_1,b_1)$ & $a_1=$\code{3086D221A7D46BCDE86C90E49284EB15}, $b_1=-$\code{E4437ED6010E88286F547FA90ABFE4C3} \\
                & $(a_2,b_2)$ & $a_2=$\code{114CA50F7A8E2F3F657C1108D9D44CFD8}, $b_2=a_1$; $a_i+b_i\lambda\equiv 0 \pmod n$; $\det = n$ \\
      Anomalous? & & no ($n\ne p$) \\
      Embedding degree & $k$ & $\ord_n(p) > 10^{6}$ (PARI: $\ord_n(p)$ is a 253-bit integer); MOV/Frey--R\"uck inapplicable \\
      Twist order & $n'$ & $2p+2-n = 3^2\cdot 13^2\cdot 3319\cdot 22639\cdot q_{220}$, $q_{220}$ a 220-bit prime \\
      2-torsion / $x=0$ & & $x^3+7$ has no root in $\F_p$ (no point of order~2); $7$ is a non-residue (no point with $x=0$) \\
      $n-1$, $p-1$ & & $n-1 = 2^6\cdot 3\cdot 149\cdot 631\cdot(\ldots)$; $p-1 = 2\cdot 3\cdot 7\cdot 13441\cdot(\ldots)$ (large cofactors) \\
      \bottomrule
    \end{tabular}
  }
  \par\smallskip{\footnotesize Source: \code{experiments/baselines/secp256k1\_facts.py}. Hexadecimal values abbreviated; full values in the JSON result and in \code{src/wp34/secp256k1.py}.}

\end{table}

\subsection{Why the special form is interesting}

Three features distinguish \secp{} from a random prime-order curve: the special prime (fast reduction), $a=0$
(cheaper doubling: $\lambda = 3x^2/2y$), and $j=0$ with $p\equiv 1\pmod 3$, which gives the curve complex
multiplication by the Eisenstein integers and therefore an automorphism group of order~6 instead of~2. The first two
are pure implementation conveniences. The third has a precise algebraic content that we now make explicit.

\begin{proposition}\label{prop:end}
Let $E/\F_p$ be ordinary with $j(E)=0$ and $p\equiv 1\pmod 3$. Then $\End(E)=\Z[\omega]$, every endomorphism is
$u+v\phi$ with $u,v\in\Z$ and has degree $u^2-uv+v^2$, and $\Aut(E) = \{\pm 1,\pm\phi,\pm\phi^2\}\cong\Z/6$.
\end{proposition}
\begin{proof}
$\phi$ is an automorphism of order~3 defined over $\F_p$, so $\Z[\phi]\cong\Z[\omega]\subseteq\End(E)$. Since $E$ is
ordinary, $\End(E)$ is an order in the imaginary quadratic field $\End(E)\otimes\Q \supseteq \Q(\omega)=\Q(\sqrt{-3})$,
hence equal to $\Q(\sqrt{-3})$, whose unique maximal order is $\Z[\omega]$. Thus $\End(E)=\Z[\omega]$. The degree of an
endomorphism is its norm, $\Norm(u+v\omega)=u^2-uv+v^2$, and the units of $\Z[\omega]$ are the six sixth roots of
unity \citep[Thm.~III.10.1, Ex.~III.10.?]{silverman2009arithmetic}.
\end{proof}

The Frobenius $\pi$ lies in $\Z[\omega]$ with $\Norm(\pi)=p$ and $\Tr(\pi)=t$, so $\pi = (t\pm f\sqrt{-3})/2$ and
$4p = t^2+3f^2$---the identity the automated search of Section~\ref{sec:framework} found in the form
``$t^2 + 3b_1^2 = 4p$''. For \secp{} we verified $t^2-4p=-3f^2$ exactly (Table~\ref{tab:secp-params}). Proposition~\ref{prop:end}
answers research question~A1 at the structural level: there is no efficiently computable endomorphism beyond
$\Z[\phi]$, because there is no endomorphism beyond $\Z[\phi]$ at all. The smallest non-unit endomorphism,
$1-\phi$ of degree~3, is computable with one addition ($P - \phi(P)$) but is simply the sum of two things we already
have.

\subsection{The GLV lattice is the ideal $(\bar\pi-1)$}

\begin{proposition}\label{prop:glv}
Let $L=\{(k_1,k_2)\in\Z^2 : k_1+k_2\lambda\equiv 0 \pmod n\}$ be the GLV lattice. Under the identification
$(k_1,k_2)\leftrightarrow k_1+k_2\omega$, $L$ is the principal ideal $(\bar\pi-1)\Z[\omega]$, where
$\bar\pi=(t-f\sqrt{-3})/2$ is the Frobenius conjugate for which $\omega\mapsto\lambda$ sends $\bar\pi-1$ to~$0$.
Consequently
\begin{equation}
\begin{aligned}
  (a_1,b_1) &= \Big(\tfrac{t-f}{2}-1,\ -f\Big), & (a_2,b_2) &= (a_1-b_1,\ a_1)\ \ (=\omega\cdot(a_1+b_1\omega)\text{ up to sign}),\\
  a_1^2-a_1b_1+b_1^2 &= n ,
\end{aligned}
  \label{eq:glvclosed}
\end{equation}
and these are exactly the constants hard-coded in \libsecp{}.
\end{proposition}
\begin{proof}
The map $\rho:\Z[\omega]\to\Z/n\Z$, $\omega\mapsto\lambda$, is a ring homomorphism because $\lambda^2+\lambda+1\equiv 0$.
Its kernel is an ideal of index $n$, hence of norm $n$; $\Z[\omega]$ is a principal ideal domain, so the kernel is
$(\alpha)$ with $\Norm(\alpha)=n$. Now $n=\#E(\F_p)=\Norm(\pi-1)=\Norm(\bar\pi-1)$ and $\pi$ acts on $E(\F_p)$ as the
identity, so $\pi-1$ kills every point and one of $\pi-1$, $\bar\pi-1$ lies in $\ker\rho$ (which one depends on the
labelling of $\omega$ versus $\lambda$); call it $\bar\pi-1$. Since $(\bar\pi-1)$ and $\ker\rho$ are ideals of the same
norm with one containing the other, they are equal. Writing $\sqrt{-3}=2\omega+1$ gives
\[\bar\pi-1 = \tfrac{t-f}{2}-1-f\omega,\]
i.e.\ $(a_1,b_1)$ as stated; multiplying by the unit $\omega$ gives the second
basis vector; and $\Norm(\bar\pi-1)=n$ is~\eqref{eq:glvclosed}. The identification with the \libsecp{} constants is an
exact integer check (\code{identity\_search.json}, field \code{closed\_form\_matches\_libsecp256k1}).
\end{proof}

We are not aware of a place where the \libsecp{} constants are written in this closed form (the library's comments
derive them by the extended Euclidean algorithm, as in \citet{gallant2001faster}); the ideal-theoretic description of the
GLV lattice for CM curves is classical \citep{sica2002analysis,galbraith2011endomorphisms}. We therefore classify
Proposition~\ref{prop:glv} as a known result independently reproduced, with an explicit form that may be of
expository use. It immediately yields the sharp bound $\max(\lvert k_1\rvert,\lvert k_2\rvert)\le \lvert a_1\rvert + \lvert b_1\rvert$ for
Babai rounding; empirically both sub-scalars have at most 128 bits (hypothesis~\Hname{H03}).

\subsection{Orbits, equivalence classes and the limits of the automorphism trick}

The group $\Aut(E)$ acts on $E(\F_p)\setminus\{\Oinf\}$ freely (no non-identity automorphism fixes a point of prime
order $n>3$ other than $\Oinf$), so the orbits $\{\pm P,\pm\phi P,\pm\phi^2P\}$ all have size~6 and the orbit space has
$(n-1)/6$ elements. Pollard's rho can be run on orbits because a canonical representative (for instance the point with
minimal $x$ among $\{x,\beta x,\beta^2 x\}$ and then minimal $y$) can be computed with two field multiplications, and
the scalar bookkeeping is adjusted by powers of $\lambda$ and signs \citep{wiener1999faster,duursma1999speeding,gallant2000improving}.
The random-mapping heuristic then predicts $\sqrt{\pi n/12}$ iterations instead of $\sqrt{\pi n/2}$: a factor
$\sqrt6\approx 2.45$. Two costs must be paid: canonicalisation, and \emph{fruitless cycles}---short cycles of the
iteration that contain no useful collision, whose frequency is $\Theta(1/r)$ for an $r$-adding walk on classes and
which must be detected and escaped \citep{bos2010negation,bernstein2011correct}. Section~\ref{sec:results} measures
the achieved factor and the cycle overhead (hypothesis~\Hname{H04}).

Could the orbit space do more than save a constant? Hypothesis~\Hname{H05} formalises the natural conjecture that
$E(\F_p)/\Aut(E)$ carries a group structure compatible with the projection, which would reduce the DLP to a group of
order $\approx n/6$ (and, iterating, suggest further reductions). It is false.

\begin{proposition}\label{prop:noquotient}
There is no group structure on the orbit set $E(\F_p)/\Aut(E)$ for which the projection is a homomorphism.
\end{proposition}
\begin{proof}
If the projection were a homomorphism, its kernel would be the orbit of $\Oinf$, which is $\{\Oinf\}$, so the
projection would be injective---contradicting the fact that the other orbits have six elements. Equivalently,
$P\sim\phi P$ and $Q\sim Q$ would force $P+Q\sim\phi P+Q$; on synthetic 16-, 20- and 24-bit $j=0$ curves this fails
for
every one of $1500$ random pairs (file \code{orbit\_quotient\_counterexample.json} under \code{results/theory/}).
\end{proof}

The same argument applies to any finite group of automorphisms fixing the identity: equivalence classes under
automorphisms are compatible with \emph{iterations} (which is all rho needs) but never with the group law. This is
the precise sense in which the structure of \secp{} yields a constant and nothing more (research questions~A2, A5).

\subsection{Algebraic attacks: an exact exclusion table}

The reductions that beat the generic bound each need a verifiable property. The MOV/Frey--R\"uck transfer to
$\F_{p^k}^*$ needs a small embedding degree $k=\ord_n(p)$ \citep{menezes1993reducing,frey1994remark}; for \secp{}, $k$
is a 253-bit integer. The anomalous-curve attack needs $n=p$ \citep{semaev1998evaluation,smart1999discrete,satoh1998fermat};
here $n\ne p$. Attacks through invalid points on the twist need a smooth twist order; the twist cofactor is a 220-bit
prime \citep{bernstein2014safecurves}. Weil-descent and summation-polynomial index calculus need an extension field or a
subfield structure \citep{semaev2004summation,gaudry2009index,diem2011discrete,petit2012elliptic}; $\F_p$ with $p$ prime
has none. Hypothesis~\Hname{H06} quantifies the last point experimentally: with a factor base $F=\{P: x(P)<\sqrt p\}$ a
random point decomposes as a sum of two factor-base points with probability $1-e^{-\lvert F\rvert^2/2n}\approx 0.4$ (measured
$0.31$--$0.44$ on 16--28-bit curves, in agreement with the Poisson prediction), but finding the decomposition
without an oracle costs $\lvert F\rvert$ operations per trial, and even with a free oracle the $\lvert F\rvert$ relations cost
$\ge 2.4\sqrt n$ and the linear algebra $\lvert F\rvert^2\approx n$. Semaev's $S_3$ polynomial, which we re-derived and
verified symbolically (check~S4), has degree~2 in each variable, so the $m=2$ decomposition is a square-root problem
in disguise; for $m\ge 3$ the decomposition step itself becomes the bottleneck over prime fields. No algorithm with
complexity below $\sqrt n$ is known for this setting \citep{galbraith2016recent}, and our experiments give no hint of one.