Examples

For simplicity, we use an elliptic curve of the form

$$y^2 = x^3 + ax + 1,$$

which has the point $P=(0,1)$ already on it.

We factor $N=5959$ using the elliptic curve method. Let

$$m=\lcm (1,2,\ldots,20) = 232792560 = 1101111000000010000111110000_2,$$

where $x_2$ means $x$ is written in binary. First we choose $a=1201$ at random and consider $y^2 = x^3 + 1201x + 1$ over $\mathbb{Z}/5959\mathbb{Z}{}$ . Using the formula for $P+P$ from Algorithm 6.2.1 we compute $2^i\cdot P = 2^i\cdot (0,1)$ for $i\in B=\{4, 5, 6, 7, 8, 13, 21, 22, 23, 24, 26, 27 \}$ . Then $\sum_{i\in B} 2^i P = m P$ . It turns out that during no step of this computation does a number not coprime to $5959$ appear in any denominator, so we do not split $N$ using $a=1201$ . Next we try $a=389$ and at some stage in the computation we add $P=(2051,5273)$ and $Q=(637,1292)$ . When computing the group law explicitly we try to compute $\lambda = (y_1-y_2)/(x_1-x_2)$ in $(\mathbb{Z}/5959\mathbb{Z})^*$ , but fail since $x_1-x_2 = 1414$ and $\gcd(1414,5959)=101$ . We thus find a nontrivial factor $101$ of $5959$ .