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$
5
  • 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
    Commented Jun 26, 2015 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
    Commented Jun 26, 2015 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$ Commented Jun 26, 2015 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$ Commented Jun 26, 2015 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
    Commented Jun 26, 2015 at 19:52

1 Answer 1

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$
8
  • $\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
    Commented Jun 26, 2015 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$ Commented Jun 26, 2015 at 20:08
  • $\begingroup$ How would you write the calculation I did in the above post? $\endgroup$
    – Raylan
    Commented Jun 26, 2015 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$ Commented Jun 26, 2015 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$ Commented Jun 26, 2015 at 22:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .