-1
$\begingroup$

How do I do this in Mathematica?

The curve given by the equation $y^2 = x^3 + 29x + 7$ defined over the integers modulo $10007$

Adding the first pair of points $P = (3737, 4549)$ and $Q = (8286, 6097)$.

Given two points $P = (x_1, y_1)$ and $Q = (x_2, y_2)$ on the elliptic curve, the sum of the two points is a point $R = (x_3, y_3)$ also on the curve.

The formulas for adding two distinct points are as follows:

If $P \neq Q$ and $x_1 \neq x_2$, then the slope of the line between $P$ and $Q$ is calculated by: $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$ Note that since we are working in a finite field, the division by $(x_2 - x_1)$ means multiplying by the modular inverse of $(x_2 - x_1)\ \text{mod}\ 10007$.

The coordinates of the point $R$ are then given by: $x_3 = \lambda^2 - x_1 - x_2$ $y_3 = \lambda(x_1 - x_3) - y_1$ All operations (additions, subtractions, and multiplications) are performed modulo $10007$.

For our first given pair of points $P$ and $Q$, here are the calculations:

Calculate the slope $\lambda$:

$\lambda = \frac{6097 - 4549}{8286 - 3737}\ \text{mod}\ 10007$

$\lambda = \frac{1548}{4549}\ \text{mod}\ 10007$

Compute the modular inverse of $4549\ \text{mod}\ 10007$ and then compute $\lambda$. (The modular inverse of $a$ is the number $b$ such that $ab \equiv 1\ \text{mod}\ 10007$.

Calculate $x_3$ and $y_3$:

$x_3 = (\lambda^2 - 3737 - 8286)\ \text{mod}\ 10007$

$y_3 = [\lambda(3737 - x_3) - 4549]\ \text{mod}\ 10007$

$\endgroup$
2
  • 1
    $\begingroup$ Hello and welcome to the Mathematica StackExchange. I reformatted your question to try and make it more approachable for other users, but it would also be great if you could add some of what you have already tried. Also you may want to look at the documentation for the PowerMod function. $\endgroup$
    – eyorble
    Nov 17, 2023 at 23:59
  • 1
    $\begingroup$ @Bob: See: mathematica.stackexchange.com/questions/276232/… $\endgroup$
    – Moo
    Nov 18, 2023 at 1:47

1 Answer 1

2
$\begingroup$

You can code this as follows (for distinct p1,p2):

np[p1_, p2_, m_] := Module[{lambda, px, py},
  lambda = x /. Solve[#1 x == #2, x, Modulus -> m][[1]] & @@ (p2 - p1);
  px = Mod[lambda^2 - p1[[1]] - p2[[1]], m];
  py = Mod[lambda (p1[[1]] - px) - p1[[2]], m];
  {px, py}]

For points and modulus 10007:

p1 = {3737, 4549};
p2 = {8286, 6097};
np[p1, p2, 10007]

yields: {7363, 370}

Confirming new point on the elliptic curve:

ec[x_, y_] := y^2 - x^3 - 29 x - 7
Mod[ec @@ np[p1, p2, 10007], 10007]

yields 0.

$\endgroup$
1
  • $\begingroup$ Is there an easy way to extend this to also cover point multiplication? $\endgroup$
    – Moo
    Nov 29, 2023 at 12:16

Your Answer

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

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