Let $E$ be an elliptic curve defined over a prime field $\mathbb{F}_p$. We assume points on $E/\mathbb{F}_p$ form a group of prime order $n$ generated by the point $G$.

The bottleneck of ECRECOVER in-circuit is in the scalar multiplications over $E$. One needs to verify an equation of the form:
\begin{align} [u_1]G + [u_2]R = P \quad\quad(1)
\end{align}

where $R \in E$ is the public key and $P \in E$ a reconstructed point from an $x$-coordinate $r$. The scalars are $u_1=m/r \mod n$ and $u_2=s/r \mod n$ with $(r,s)$ the ECDSA signature tuple and $m$ the signed message.

In a BN254 PLONK circuit, an ECRECOVER (where $E=\texttt{secp256k1}$) costs *mainly* a variable-base scalar multiplication $[u_2]R$ ($\texttt{881041 scs}$) and a fixed-base scalar multiplication $[u_1]G$ ($\texttt{604534 scs}$).

*N.B.*: a joint scalar multiplication that scans $u_1$ and $u_2$ simultanously is not efficient in-circuit for short Weierstrass curves when one of the points is fixed, becayse $u_1$ is scanned right-to-left (to precompute doubles of $G$) and $u_2$ is scanned left-to-right.

## A silly idea [SAC:ABGL+05] ?
One can re-write the equation by multiplying it by some scalar $v$:

$$ [v\cdot u_1]G + [v\cdot u_2]R - [v]P = \mathcal{O}$$

This results in one more variable-base scalar multiplication, but if we choose $v$ to be $u\cdot r/s \mod n$ such that both $v$ and $u$ are half-size of $n$, then we get:

\begin{align} [u\cdot m/s]G + [u]R - [v]P = \mathcal{O} \quad\quad(2)
\end{align}

One can find a suitable value for $v$ by writing $x = s/r \mod n$ as $x = u/v \mod n$, where $u$ and $v$ are integers of approximately half the bit-size of $n$ or, more generally, of $1 - \epsilon$ and $\epsilon$ times the bit-size of $n$, respectively, where $0 < \epsilon < 1$.

#### Maybe not too silly
Let $n$ be a prime number. Any integer $x \in \mathbb{F}_n$ can be written as $x = u/v \mod n$, where $u$ and $v$ are integers such that $|u| < n^{1-\epsilon}$ and $1 \leq v \leq n^\epsilon$. In particular, one may have $|u| < \sqrt{n}$ and $1 \leq v \leq \sqrt{n}$ for $\epsilon = 1/2$. This looks like finding good solutions to the *simultaneous Diophantine approximation problem* which is equivalent to the problem of *finding short vectors in a particular lattice*.

**TODO**: more one that + sagecode

### In-circuit optimization
| | Total cost | constraints |
----------|------|---|
|(1) | 1 full fbSM + 1 full vbSM | |
|(2) | 1 full fbSM + 1 half-sized vbSM + 1 half-sized vbSM |

It results a priori in the same cost, but now we can implement $[u]R - [v]P$ efficiently using Strauss-Strassen trick thanks to the endomorphism [[PR 949]](https://github.com/Consensys/gnark/pull/949).