0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – fgrieu May 13 at 21:13
  • $\begingroup$ $$pow((43690*u+516),-1,257^2)$$ gives me $$(1/2/(21845*u + 258))$$ in sagemath. $\endgroup$ – Jude Murray May 14 at 2:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.