3
$\begingroup$

I'm implementing point addition and point doubling of elliptic curve cryptography. The formula that I'm using for slope is

Point addition: $S = \frac{(P_y-Q_y)}{(P_x-Q_x)}$ where $P$ and $Q$ are the two points.

Point doubling: $S = \frac{(3P_x)^2+a}{2P_y}$ where $P$ and $Q$ are the two points and $a$ is one of the parameters of the curve.

The divisions involved here are modular divisions. I use extended euclidean algorithm.

My question is what if the numerator is smaller than the denominator? In that case can i still use this algorithm? Or is there any other algorithm to perform such modular divisions? Or there is no possibility at all for the numerator to end up smaller than denominator in elliptic curves??

$\endgroup$
3
$\begingroup$

I'll assume we are working modulo $p$, which most likely is some large prime. When evaluating $S={P_y-Q_y\over P_x-Q_x}$, one really is finding a representative integer of the residue class of the equivalence relation modulo $p$; that is, the result is defined within addition or subtraction of $p$ any number of times.

The same holds for numerator $P_y-Q_y$ and denominator $P_x-Q_x$: addition or subtraction of $p$ to these quantities, any number of times, is immaterial. That makes comparing numerator and denominator moot; and even ambiguously defined: when working modulo 7, we can't tell which is the smaller of 2 or 6; that's because we could as well be comparing 2 to -1, or 9 to 6.

As long as $P_x-Q_x$ is not a multiple of $p$, one evaluates $S={P_y-Q_y\over P_x-Q_x}$ without considering a comparison of numerator and denominator. The result is, depending on definition

  • any integer $S$ such that $S\cdot(P_x-Q_x)-(P_y-Q_y)$ is a multiple of $p$;
  • or perhaps the single non-negative integer $S$ less than $p$ with this property; this would be obtained by "reducing modulo $p$" some $S$ with this property; that is:
    • if $S$ is negative, change $S$ to $S+p\cdot\lfloor{p-1-S\over p}\rfloor$, where $\lfloor{p-1-S\over p}\rfloor$ is the quotient of the Euclidian division of the positive integer $p-1-S$ by the positive integer $p$, and $\cdot$ stands for ordinary multiplication;
    • otherwise, change $S$ to $S-p\cdot\lfloor{S\over p}\rfloor$ (or equivalently, change $S$ to the remainder of the Euclidian division of $S$ by $p$).

If we stick to the convention that $S$ and intermediary results are kept as non-negative integers less than $p$ (or, equivalently, as kept reduced modulo $p$), the evaluation of $S={P_y-Q_y\over P_x-Q_x}$ could go:

  • evaluate the denominator $U=P_x-Q_x$, reducing the result modulo $p$;
  • abort if that's zero;
  • compute the modular inverse $I$ of $U$ modulo $p$ using the extended Euclidian algorithm, reducing the result modulo $p$ ($I$ is well defined if $p$ is a prime);
  • evaluate the numerator $V=P_y-Q_y$, reducing the result modulo $p$;
  • evaluate $S=I\cdot V$, and reduce the result modulo $p$.

The same applies for $S$ as used in point doubling, except for what numerator and denominator are (the formula to be used will depend on the curve).

| improve this answer | |
$\endgroup$
  • $\begingroup$ The procedure that u have mentioned at the last is what i'm following. But I couldnt understand the explanation given above that. Can u explain me in Layman's terms?? For example I take 140/14 (mod 101)..Now mulinverse(14,101) =65.... 140*65 (mod 101) =10 which is obviously the result for 140/14...Now If i'm gonna take 13/14=0.93 but 13*65 (mod 101) = 37. Hence if the numerator is less than denominator then the results vary...If you are actually telling that the numerator will always be greater than denominator, explain me in simple terms why? $\endgroup$ – abejoe Dec 10 '15 at 6:16
  • $\begingroup$ Even the subtractions Py-Qy and Px-Qx are also done with respect to mod p $\endgroup$ – abejoe Dec 10 '15 at 6:44
  • $\begingroup$ @abejoe: $140/14\bmod101$ is indeed $10$. That's also true if you change $101$ to any integer at least $11$. The method you are using, and that I describe, does work. The coincidence with the result over the integers is because 14 happens to divide 140. $\;$ My explanation is in layman's terms, except for "a representative integer of the residue class of the equivalence relation modulo $p$", which you can skip and replace with the alternative that I give following "that is". Just take care of reading my text carefully, and grasping the definition of "reducing modulo $p$". $\endgroup$ – fgrieu Dec 10 '15 at 7:32
  • $\begingroup$ @abejoe: notice that $140/14\pmod{101}$ [written $140/14\pmod{101}$ ] is not, strictly speaking, an integer; that's the class of integers $x$ such that $14x-140$ is a multiple of $101$. On the other hand, $140/14\bmod 101$ [written $140/14\bmod{101}$ or $140/14\bmod101$ ] is the non-negative integer less than $101$ with this property, that is $10$. $\endgroup$ – fgrieu Dec 10 '15 at 7:39
  • $\begingroup$ Okay lets go step by step for my understanding....First in elliptic curves, while computing slope, will the numerator end up being smaller than denominator? $\endgroup$ – abejoe Dec 10 '15 at 7:46

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.