2
$\begingroup$

I have found the following formulas for the coordinates of $P+Q$ given that $P = (x_{1}, y_{1})$ and $Q = (x_{2}, y_{2})$ are points on a general curve $y^2 = x^3 + ax + b$ over $\mathbb{R}$:

$$P + Q = (x_3, y_3) = \left(\left[\frac{y_2-y_1}{x_2-x_1}\right]^2-x_1-x_2, -\left[\frac{y_2-y_1}{x_2-x_1}\right] \cdot \left[x_3-x_1\right]-y_1\right)$$

For point doubling, the case where $P = Q$, I have found:

$$2P = \left(\left[\frac{3x^2_1+a}{2y_1}\right]^2-2x_1, -\left[\frac{3x^2_1+a}{2y_1}\right] \cdot [x_3-x_1]-y_1\right)$$

(See this page for a cleaner representation)

These formulas work for elliptic curves over $\mathbb{R}$, but not for finite fields $\mathbb{F}_{p}$ of prime order $p$. I know I will have do some calculations modulo $p$, but I do not know where. How do I modify the above formulas so they will work for $\mathbb{F}_{p}$ instead of $\mathbb{R}$?

$\endgroup$
  • 1
    $\begingroup$ Those addition formulae work fine over finite fields. The only exception is fields of characteristic $2$, because then you can't divide by $2$. $\endgroup$ – TonyK Jun 26 '15 at 19:19
  • $\begingroup$ @TonyK If I take $y^{2} = x^{3} + x + 1$ over $\mathbb{F}_{5}$ and $P = (2,1), Q = (4,2)$, Id find $P+Q = (\frac{-23}{4}, \frac{-47}{16})$. What am I overlooking? $\endgroup$ – Raylan Jun 26 '15 at 19:42
  • $\begingroup$ @Raylan : How do you evaluate $-23/4$ in mod $5$? You multiply $-23$ (which in mod $5$ is the same as $2$) by the mod $5$ multiplicative inverse of $4$. So what is the mod $5$ multiplicative inverse of $4$? ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 26 '15 at 19:46
  • $\begingroup$ $\ldots$ and as for finding multiplicative inverses modulo a prime, I wrote this answer on how to do it: math.stackexchange.com/questions/67171/… $\endgroup$ – Michael Hardy Jun 26 '15 at 19:49
  • 2
    $\begingroup$ Think about it, Raylan: If it's a field, finite or not, then you can add, subtract, multiply, and divide in it. That's what it means to be a field. $\endgroup$ – TonyK Jun 26 '15 at 19:52
1
$\begingroup$

Comments under the question suggest that possibly the difficulty was in doing arithmetic modulo a prime. How does one find $-23/4$ in $\mathbb F_5$? $-23$ reduces to $2$, and to divide by $4$ you multiply by the mod $5$ multiplicative inverse of $4$, which you need to find.

Trial and error will find the multiplicative inverse when the modulus is $5$, but what if it's a large prime? I answer that question here.

$\endgroup$
  • $\begingroup$ Am I correct in assuming $\frac{-23}{4} \mod 5 = (-23 \mod 5) \cdot (4^{-1} \mod 5) = (2 \cdot 4) \mod 5 = 8 \mod 5 = 3$? $\endgroup$ – Raylan Jun 26 '15 at 19:58
  • 1
    $\begingroup$ Your notation is not standard and I initially didn't understand it. Often one writes things like $\displaystyle (a\equiv b)\mod c$ to mean $a$ and $b$ are congruent to each other modulo $c$. It is often written as $a\equiv b\mod c$, but I've added parentheses so that it won't be misunderstood as meaning $a\equiv (b\bmod c)$. I've seen that misunderstanding arise many times and lead to the person who reads $a\equiv b\mod c$ being puzzled. However, it is correct that $4$ is its own multiplicative inverse in mod $5$, so dividing by $4$ is the same as multiplying by $4$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 26 '15 at 20:08
  • $\begingroup$ How would you write the calculation I did in the above post? $\endgroup$ – Raylan Jun 26 '15 at 20:18
  • 1
    $\begingroup$ Perhaps I would write \begin{align} -23 \div 4 & \equiv 2\cdot 4^{-1} \pmod 5 \vphantom{\frac11} \\ & \equiv 2\cdot 4 \vphantom{\frac11} \\ & \equiv 3. \vphantom{\frac11} \end{align} If you use $\bmod$ as a binary operator, so that $a\bmod b$ means the remainder on division of $a$ by $b$, then it should be coded as \bmod, since that results in only the amount of space on the left and right that is standard with binary operators, as in $2+3$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 26 '15 at 20:28
  • 1
    $\begingroup$ Notice that with \pmod rather than \bmod you get $-3\cdot2^{-1}\pmod 5$. That would be appropriate in this instance because that space to the left of "mod" shouldn't be there. I coded this as -3\cdot2^{-1}\pmod 5, but if I'd had a two-digit number rather than $5$ then I'd need braces: -3\cdot2^{-1}\pmod 53 yields $-3\cdot2^{-1}\pmod 53$ and -3\cdot2^{-1}\pmod{53} yields $-3\cdot2^{-1}\pmod{53}$. ${}\qquad{}$ $\endgroup$ – Michael Hardy Jun 26 '15 at 22:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.