# Is there any alternative for extended euclidean algorithm to perform modulo division?

I'm implementing point addition and point doubling operations for elliptic curve cryptography. I have implemented extended euclidean algorithm to perform modulo division.

It appears the that extended euclidean algorithm takes almost 90% of the computation time for the whole operation. It is slowing down the entire operation.

Can anybody suggest me an alternative approach?.. Or if someone have already implemented it, tell me how did you manage to reduce the time taken??

• Perhaps your implementation would benefit from using projective coordinates to represent curve points. That way, the denominators are "accumulated" in each intermediate step and you only perform one inversion in the end (to obtain the corresponding affine coordinates). – yyyyyyy Dec 10 '15 at 12:04
• I assume you are working modulo some prime $p$. While your 90% is a lot, and perhaps could be reduced somewhat, what you describe is to be expected. Indeed, that overhead can be avoided. A simple and instructive method is to work with quantities kept as a fraction of two integers, without modular inversion. Usual algebraic rules for fractions apply unchanged for modular fractions. Both numerator and denominator should be reduced modulo $p$, at least regularly in the ongoing computation or/and when their absolute value exceeds some threshold. It does not pay to further reduce the fraction. – fgrieu Dec 10 '15 at 13:41

For increasing speed, you should use of "Barrett reduction" and "Montgomery multiplication". For more detail you can see "Guide to Elliptic Curve Cryptography". Also you can use "MAGMA". This program is one of the best and fastest program for elliptic curve.

I am aware that this question was posted and answered a while ago but I would like to solve the confusion introduced in the last 2 comments. What the author of the question would like to optimize is the inversion in a field (not an elliptic curve group) which can be implemented in different ways and which is typically avoided in elliptic curve implementations by using a projective coordinate representation as suggested by @yyyyyyy.

The last two comments are related to the inversion of an elliptic curve point P = (x,y), which in this case is actually the opposite and is very easily computed as -P = (x, -y). And this is completely different than inverting a field element during the calculation of the scalar multiplication.

Due to the multi-layered structure of ECC (single precision elements, field and then elliptic curve group) it is easy to confuse the different operations involved in the different layers.

If I understand you correctly, you wish to compute $P-Q$ where $P$ and $Q$ are elliptic curve points. If you were working in a subgroup of $\mathbb Z_p^*$, then in order to compute $\frac{h_1}{h_2}$ then you indeed need extended Euclidean in order to find the inverse of $h_2$ and then multiply that with $h_1$. However, in elliptic curve groups, it is trivial to find $-Q$. Specifically, let $Q=(x,y)$ where $x$ and $y$ are in the underlying field. Then, $-Q=(x,-y)$. Thus, all you need to do is to take the negative of $y$ in the underlying field, and then add the result with $P$. This is therefore very fast.

• Yeah you are right in understanding me. But I somewhere lag in understanding you. Your suggestion of taking the negative of Q and adding with P eliminates P-Q or it eliminates the process of using extended euclidean to compute modulo division??.....I just didn't understand that part! – abejoe Dec 10 '15 at 8:22
• Extended Euclidean is used in modulo division since you need to find the multiplicative inverse of $h_2$ in order to compute $\frac{h_1}{h_2}$. In Elliptic curves, the inverse is additive and is found by just taking $-y$. – Yehuda Lindell Dec 10 '15 at 9:00
• Can you please explain me with an example – abejoe Dec 10 '15 at 9:37

For two points P= (x1,y1) and Q = (x2,y2) The point R = P-Q is just P plus the additive inverse of Q, this inverse is just -Q = (x2,-y2) as Yehuda said. I will just give you an intuition for that: Imagine the classical curve over the reals that is used for illustration purposes. If you draw a line between the point D = (x2,y2) and the point (x2, -y2), you will get a vertical line. This line will not intercept the curve in any other point but at infinity (which happens to be the identity element since P + 'infinite' = P) therefore (x2,-y2) is the inverse of (x2,y2).

Hope it helps!

• I appreciate your effort to help me. But i just wanted to know whether can be a less expensive alternative to extended euclidean algorithm. – abejoe Dec 11 '15 at 6:55
• Try with projective coordinates. The equations will change a bit but you don't need to do inversions. There is a very good tutorial by Craig Costello, it is called "pairings for beginners". Look at section 2.1.4. – Jhordany Dec 11 '15 at 13:23
• Is it possible to implement NISTP256 curve in projective coordinates formulae given in that section 2.1.4? – abejoe Dec 11 '15 at 19:31