# Point Division in Elliptic Curve Cryptography?

I want to implement a crypto protocol using Elliptic Curve Cryptography. However, it requires a division which I cannot handle.

In multiplicative notation, it requires:

1. Let $\mathbb{G}=\left \langle g \right \rangle$ be a finite cyclic group of prime order $p$.
2. select $P \in_{R} \mathbb{G}$ and $a \in_{R} \mathbb{Z}_{p}$ and
3. compute $S=P^\frac{1}{a}$.

In conversion between multiplicative and additive group notation, I learned that $S=P^\frac{1}{a}$ means $S=\frac{1}{a}P$ in additive notation. I only know point addition and point multiplication. Is there a way to calculate S?

-
Is it division or modular inverse? – Amzoti Aug 19 '13 at 14:46
I know that the modular inverse for ECC is quite easy (-P). Can I solve this problem using the modular inverse? – Horst Lemke Aug 19 '13 at 14:49
Can you post the problem and an example of your issue so we can have a peek? Regards – Amzoti Aug 19 '13 at 14:51
I'm not sure, how much I'm allowed to post. But I can surly name the Paper: link.springer.com/chapter/10.1007%2F11774716_17#page-1 (Page 212, Peer Registration, Step 5) - – Horst Lemke Aug 19 '13 at 14:55
Sorry, I do not have access. Regards – Amzoti Aug 19 '13 at 14:58

As far as I can tell the operation being referred to is raising the point $P$ to the power $a^{-1} \in \mathbb{Z}_p$. Calculating this inverse is as Amzoti says just modular inversion, which should be fairly easy to do with the Euclidean algorithm. Then just raise $P$ to the calculated power, which can be done simply, or a bit quicker if you wish.
The reason it is written this way is probably to make it easier to read, compare $P^{(a+z)^{-1}}$ to $P^{1/(a+z)}$ as is written in the source.
So just for completenes, I can say: $P^{1/(a+z)}=P^{(a+z)^{-1}}=(P^{{-1}})^{(a+z)}$ which makes very much sense to me and helps me to solve the problem. – Horst Lemke Aug 20 '13 at 6:58
@HorstLemke I'm not so sure about the last equality, you should try and think of $(a+z)^{-1}$ as one object, the inverse of the element $a+z$ mod $p$, which you would first calculate (the answer can always be found in the range 1 to $p$) then apply the operation on the point this many times. – Alex J Best Aug 20 '13 at 13:01
+1 This is the only sensible interpretation. Given that in ellipctic curve crypto the prime $p$ usually has dozens (if not hundreds) of digits the point about square-and-multiply is a bit moot. I do not know of a single textbook on crypto that would not include that. No doubt you added it just to be safe :-) – Jyrki Lahtonen Aug 21 '13 at 6:20