1
$\begingroup$

$y^2=x^3+9x+17$ over $\mathbb{F}_{23}$, what is the discrete logarithm $k$ of $Q=(4,5)$ to the base $P=(16,5)$?

One (naï­ve) way to find k is to compute multiples of $P$ until $Q$ is found. The first few multiples of $P$ are:

$P=(16,5)$, $2P=(20,20)$, $3P=(14,14)$, $4P=(19,20)$, $5P=(13,10)$, $6P=(7,3)$, $7P=(8,7)$, $8P=(12,17)$, $9P=(4,5)$

Since $9P=(4,5)=Q$, the discrete logarithm of $Q$ to the base $P$ is $k=9$.

How do we get to these scalar multiples?

$P=(16,5),2P=(20,20),3P=(14,14),4P=(19,20),5P=(13,10), 6P=(7,3),7P=(8,7),8P=(12,17),9P=(4,5)$

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Are you asking how the points are added ? like this formulas? And, scalar multiplication. Note that iterating is easier than using scalar multiplication. For small elliptic curve groups, this has 23, it is easy by iteration for large groups you may need the discrete log algorithms like the Pollard $\rho$ to solve up to some bound. $\endgroup$
    – kelalaka
    Commented Dec 31, 2021 at 21:08
  • $\begingroup$ Yes , but I don't understand how. $\endgroup$
    – Ramin Najafi
    Commented Jan 1, 2022 at 6:36
  • $\begingroup$ The point addition in the Elliptic curve has a geometric meaning as you may see from one of the links. It is called the tangent-and-chord rule. It is a long process that proving the tangent-and-cord rule from a group, especially associativity is long. Read the elliptic tales and/or Washingtons book $\endgroup$
    – kelalaka
    Commented Jan 1, 2022 at 9:05
  • $\begingroup$ To add two-point, draw a line and find the third intersection on reflex this point on the x-axis. One can use the curve equation and line equation to find the intersection point algebraically. You may see it simply in the pictures $\endgroup$
    – kelalaka
    Commented Jan 1, 2022 at 9:08
  • $\begingroup$ To get the scalar multiples $2P$, $3P$, …$9P$ : apply the point doubling and addition formulas given in @kelalaka's answer, section "Group Law on Affine Coordinates", case 3, with the second formula for $\lambda$ when computing $2P=P+P$, and the first formula for $\lambda$ when computing later $k\,P=(k-1)P+P$. Recall that division is in $\mathbb F_{13}$, thus $u/v$ is $u\,v^{-1}$ where $v^{-1}$ is the multiplicative inverse $w$ of $v$, such that $v\,w\equiv1\pmod{23}$. $w=v^{-1}$ can be computed using the extended Euclidean algorithm. $\endgroup$
    – fgrieu ♦
    Commented Jan 1, 2022 at 16:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.