1
$\begingroup$

Walkthrough the textbook content, understand that we need to compute the slope of 2 points before can compute the new point as the result of addition.

Multiplicative inverse is part of the operation in a process to find the slope, where we know Extended Euclidean Algorithm is one of the best method to be used.

However, in order to realize the Extended Euclidean Algorithm in hardware RTL, we need to consider about when the integer go very large. Initially when I model the algorithm out in RTL, everything works fine if I simply using "/" and "%" to find the quotient and remainder.

But I don't think this is practical when we dealing with large number. Could I get a hint that any techniques we can leverage to achieve more efficient Extended Euclidean Algorithm? Does Montgomery Reduction can be leveraged here? Need some enlightenment after days of stuck.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Have you studied the Binary Extended GCD (see also note 14.64) and it's improvements (link fixed)? Independent note: With a proper coordinate system, computing the multiplicative inverse needs to be performed only on the final result needed for signature generation or verification, thus is not the bottleneck as it is if performed at each point addition. $\endgroup$
    – fgrieu ♦
    Commented Apr 18, 2023 at 11:17
  • $\begingroup$ @fgrieu, regarding the independent note "the proper coordinate system" is only refer to certain EC? means that we only can avoid for doing multiplicative inverse at every addition point with selected EC, or more refer to certain design technique? $\endgroup$
    – Pi-Turn
    Commented Apr 18, 2023 at 13:25
  • $\begingroup$ Two popular coordinate systems that work for any curve in Weierstrass form are Projective coordinates and Jacobian coordinates. The speed gain can be spectacular. $\endgroup$
    – fgrieu ♦
    Commented Apr 18, 2023 at 13:28
  • $\begingroup$ @fgrieu, based on your earlier hint. I manage to implement formula published in the explicit formula database in hardware. However, the formula is only works for the first addition and I'm not sure how to perform the subsequent in jacobian domain without converting back and forth. Would you mind to hint me a bit on this. X3 and Y3 I got is in jacobian form now but the subsequent add is to deal with the affine coordinate, so I think i must be doing something with X3 and Y3 before can reuse the same formula i used initially? $\endgroup$
    – Pi-Turn
    Commented Apr 23, 2023 at 14:38
  • $\begingroup$ Basic idea: starting from Cartesian coordinates $x,y$ convert to Jacobian $(X,Y,Z)←(x,y,1)$. Then perform scalar multiplication by double and add using formulas there following "2007 Bernstein/Lange, 11M + 5S + 9add + 4times2:" for add and "2007 Bernstein/Lange, 1M + 8S + 1D + 10add + 2times2 + 1times3 + 1times8:" for doubling. Then convert outcome $(X',Y',Z')$ to Cartesian per $u←Z'^{-1}\bmod p$ [using EEA, BEEA, or $u←Z'^{p-2}\bmod p$ ] then $v\gets u^2$ then $(x,y)←(v\,X',u\,v\,Y')$. A few further savings are possible. $\endgroup$
    – fgrieu ♦
    Commented Apr 23, 2023 at 16:17

1 Answer 1

Reset to default
2
$\begingroup$

The Extended Euclidean Algorithm is not the only way to compute inverses.

Another way (if $p$ is prime) is to take advantage of this identity:

$$x^{-1} = x^{p-2} \pmod p$$

(this identity also assumes $x \ne 0$, not an issue in this case).

That is, you can also compute the inverse by performing $O(\log p)$ multiplications; if you already implement multiplication modulo $p$, this may be easier for you to implement.

Improve this answer
$\endgroup$

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.