Introduction to Cryptography with Coding Theory, 3rd Edition

21.3 Factoring with Elliptic Curves

Suppose $n=pq$ is a number we wish to factor. Choose a random elliptic curve mod $n$ and a point on the curve. In practice, one chooses several (around 14 for numbers around 50 digits; more for larger integers) curves with points and runs the algorithm in parallel.

How do we choose the curve? First, choose a point $P$ and a coefficient $b\text{.}$ Then choose $c$ so that $P$ lies on the curve $y^2=x^3+bx+c\text{.}$ This is much more efficient than choosing $b$ and $c$ and then trying to find a point.

For example, let $n=2773\text{.}$ Take $P=(1\text{,}3)$ and $b=4\text{.}$ Since we want $3^2\equiv 1^3+4\cdot 1+c\text{,}$ we take $c=4\text{.}$ Therefore, our curve is

$$\begin{array}{ccc}E:& y^2\equiv x^3+4x+4& \left(\mathrm{mod}2773\right)\text{.}\end{array}$$

We calculated $2P=(1771\text{,}705)$ in a previous example. Note that during the calculation, we needed to find $6^{}$