# Doubling a point on an elliptic curve

I've a programming background and am just about to get into a project where Elliptic Curve Cryptography (ECC) is used. Although our libraries deal with the details I still like to do background reading so started with the ECC chapter of Understanding Cryptography. Everything was fine until I came upon this example of point doubling over $Z_{17}$:

I can't figure out how he gets $s$. For example the $(2\cdot1)^{-1}(3\cdot5^2+2)$ why does that evaluate to $2^{-1} \cdot 9$? From looking at it I would have thought $(3\cdot5^2+2)$ evaluates to $77$ so giving $2^{-1}\cdot77$ or $77\div2$ for the whole expression. Obviously the math doesn't work in the way I expect, is it something to do with the dot product not being normal multiplication? Or something else?

p.s. Sorry about formatting, I'm looking up how to do the Tex for the site now.

• Are you familiar at all with modular arithmetic? $77=9$ in $\mathbb{Z}_{17}$. – fretty Jun 27 '13 at 14:21
• Yes, to be precise, the author should have written $(2\cdot 1)^{-1}(3\cdot 5^2+2)\equiv 2^{-1}\cdot 9 \bmod 17$, and not just $=$. – Álvaro Lozano-Robledo Jun 27 '13 at 14:23
• @ÁlvaroLozano-Robledo Thanks, can't believe it's that simple for that bit... So you have to apply the modulus operator the whole way through? So that bit is equivalent to $9\cdot9$ because $9/2$ is 4.5 and $89\mod17$ is 4 and you truncate in $Z$? Just not seeing how $9\cdot9 = 13\mod17$ – Peanut Jun 27 '13 at 14:35
• $9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17$. – Álvaro Lozano-Robledo Jun 27 '13 at 14:39
• I asked nearly this identical question on Crypto crypto.stackexchange.com/questions/64456, and the answer there may also be worth looking at. – Brian M. Hunt Dec 1 '18 at 13:44

## 1 Answer

All arithmetic is done modulo $17$, so $$(2\cdot 1)^{-1}(3\cdot 5^2+2)\equiv 2^{-1}\cdot 9\bmod 17$$ is a congruence, not an equality in $\mathbb{Q}$.

Moreover, $9\cdot 9\equiv 13 \bmod 17$ because $$9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17,$$ or, equivalently, $$9\cdot 9\equiv (-8)\cdot (-8)\equiv 64\equiv 16\cdot 4\equiv -4\equiv 13\bmod 17.$$