Score:1

how calculate 2g ,3g ,

ca flag

$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)$

kelalaka avatar
in flag
Are you asking how the points are added ? [like this formulas](https://crypto.stackexchange.com/q/66288/18298)? And, [scalar multiplication](https://crypto.stackexchange.com/q/68593/18298). 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.
Ramin Najafi avatar
ca flag
Yes , but I don't understand how.
kelalaka avatar
in flag
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](https://www.amazon.com/Elliptic-Tales-Curves-Counting-Number/dp/0691163502) and/or [Washingtons book](https://www.amazon.com/Elliptic-Curves-Cryptography-Mathematics-Applications/dp/1420071467/)
kelalaka avatar
in flag
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](https://crypto.stackexchange.com/a/91687/18298)
fgrieu avatar
ng flag
To get the scalar multiples $2P$, $3P$, …$9P$ : apply the point doubling and addition formulas given in [@kelalaka's answer](https://crypto.stackexchange.com/a/66296/555), 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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.