# How to multiply Elliptic curve point $S = (7 + 257 \times u, \space 258 + 21845 \times u) (\bmod 257^2 )$ on curve $y^2 = x^3 + 23\times x + 11$?

First of all I'm not good at English. Hope you will understand my question. In the paper 'Lifting and Elliptic Curve Discrete Logarithms' by Professor J. H. Silverman I found this example.

Example : We let $$p = 257$$ and consider the field $$k = F_{257}$$ and the elliptic curve and point

$$e : y^2 = x^3 + 23 \times x + 11 , s = (7, 1) ∈ e(k)$$.

It is easy to check that $$e(k) = 249 = 3 \times 83$$ and that $$s$$ has order $$n = 83$$ in $$e(k)$$. We lift $$e$$ to a p-adic curve $$E$$ in the obvious way,

$$E : Y^2 = X^3 + 23 \times X + 11$$

We will lift $$s$$ to a point $$S \bmod p^2$$. We write $$S$$ in the form

$$S = (7 + p \times u,\space 1 + p \times v) \bmod p^2$$.

In order for $$S$$ to represent a point on $$E \bmod p^2$$ , we need

$$(1 + p \times v)^2 ≡ (7 + p \times u)^3 + 23 \times (7 + p \times u) + 11 (\bmod p^2)$$

Expanding this gives

$$1 + 2 \times p \times v ≡ 515 + 170 \times p \times u (\bmod p^2 )$$

so we find that $$v ≡ 85 \times u + 1 (\bmod p)$$. Thus $$S$$ has the form

$$S = (7 + p \times u, 258 + 85 \times p \times u) = (7 + 257 \times u, 258 + 21845 \times u) (\bmod 257^2)$$

My question is how do we find $$41 \times S$$. It was given here that

$$41\times S ≡ (59609 + 12336 \times u, 39178 + 44718 \times u) (\bmod 257^2)$$

When doubling a point, let's say $$2\times S$$ needed to find the tangent line of the point to the curve. $$Slope = ((3 \times a[0] \times a[0]) \times inversemod((2 \times a[1]),p)) (\bmod p)$$ $$= ((3 \times (7 + 257 \times u) \times (7 + 257 \times u)) \times inversemod((2 \times (258 + 21845 \times u)),257^2)) (\bmod 257^2)$$ $$= (10794 \times u + 147) \times inversemod((43690 \times u + 516),257^2)) (\bmod 257^2)$$

I'm stuck at here. How to get this step solved? Simple Python or Sage code would be greatly appreciated.

• In python 3.8, $a^{-1}\bmod m$ (if it is well-defined) can handily be computed using pow(a,-1,m). $a+b\bmod m$ and $a\;b\bmod m$ are (a+b)%m and a*b%m. Exactly where are you stuck? – fgrieu May 13 at 21:13
• $$pow((43690*u+516),-1,257^2)$$ gives me $$(1/2/(21845*u + 258))$$ in sagemath. – Jude Murray May 14 at 2:56