# Find a curve cycle that can efficiently reason about Ed25519/Curve25519

Problem: Find $p$, $q$ prime and as small as feasible such that there exists a cycle $E_p/\mathbb{F}_p$ and $E_q/\mathbb{F}_q$, and some different $E'_p/\mathbb{F}_p$ has order $r = 2^{255} - 19$ times some small cofactor $h$.

If $p$ and $q$ are prime then the cycle necessarily exists. $E'_p$ does not need to have $|D| = 3$, so the problem is essentially to find prime $p \equiv 1 \pmod{6}$ and $E'_p$, $p$ as small as feasible, so that $\# E'_p = hr$, and then hope that one of the possibilities for $q$ is prime.

> The [curve cycle search](https://github.com/daira/curvesearch/blob/master/amicable.sage) requires $p \equiv 1 \pmod{6}$. The problem statement does not require $E_p$ and $E_q$ to have any other nice properties.

Constructing $p$ and $E'_p$ by Cocks--Pinch or Dupont--Enge--Morain would give $p$ and $q$ about twice the size of $hr$. So it is better to construct it more directly by CM.

For a CM curve $E'_p$ we have $\# E'_p = hr \in \left\{p + 1 \pm T_p, p + 1 \pm \frac{3V}{2} \pm \frac{T_p}{2}\right\}$ for integers $T_p$ and $V$. Without loss of generality assume $T_p$ and $V$ are positive; also the cycle condition requires $T_p \equiv 1 \pmod{6}$.

> All 6 possibilities can only occur if $E'_p$ has $j$-invariant 0. In that case one of them will be $q$, but the other 5 are possibilities for $hr$. See [[IEEE Std 1363-2000]](https://perso.telecom-paristech.fr/guilley/recherche/cryptoprocesseurs/ieee/00891000.pdf), section A.14.2.3, item 6.

Case $hr = p + 1 + T_p$:

We have $T_p = hr - p - 1$ and the norm equation for $E_p$, i.e. $4p = |D|V^2 + T_p^2$. So:

\begin{array}{rl}
4p\!\!\!&= 3V^2 + (hr-1 - p)^2 \\
&= 3V^2 + (hr-1)^2 - 2(hr-1)p + p^2 \\
0\!\!\!&= 3V^2 + (hr-1)^2 - 2(hr+1)p + p^2
\end{array}

Using the quadratic formula for $ap^2 + bp + c = 0$ with $a = 1$, $b = -2(hr+1)$ and $c = 3V^2 + (hr-1)^2$, we get

\begin{array}{rl}
p\!\!\!&= \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\
&= \frac{2(hr+1) \pm \sqrt{4(hr+1)^2 - 4 \cdot (3V^2 + (hr-1)^2)}}{2} \\
&= hr + 1 \pm \sqrt{(hr+1)^2 - 3V^2 - (r-1)^2} \\
&= hr + 1 \pm \sqrt{(hr)^2 + 2hr + 1 - 3V^2 - ((hr)^2 - 2hr + 1)} \\
&= hr + 1 \pm \sqrt{4hr - 3V^2}
\end{array}
i.e. $4hr - 3V^2 = (p-hr-1)^2$ or $4hr = 3V^2 + (p-hr-1)^2$. In general finding such a $V$ and $(p-hr-1)$ requires solving a generalized Pell equation $N = x^2 - dy^2$ where $N = 4r$, $x = p-hr-1$, $d = -3$, and $y = V$. But methods of solving generalized Pell equations usually require $d > 0$ :-(

----
Only rough ideas below here.

$4hr = 3V^2 + (p-1-hr)^2$

Choose $p = kV$, then
$4hr = 3V^2 + k^2V^2 - 2kV(hr+1) + (hr+1)^2$
$0 = (3+k^2)V^2 - 2kV(hr+1) + (hr)^2 + 2hr + 1 - 4hr$
$0 = (3+k^2)V^2 - 2kV(hr+1) + (hr-1)^2$
$V = \frac{2(hr+1) \pm \sqrt{4(hr+1)^2 - 4(3+k^2)(hr-1)^2}}{2(3+k^2)}$