3
$\begingroup$

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}$:

enter image description here

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.

$\endgroup$
  • $\begingroup$ Are you familiar at all with modular arithmetic? $77=9$ in $\mathbb{Z}_{17}$. $\endgroup$ – fretty Jun 27 '13 at 14:21
  • 1
    $\begingroup$ 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 $=$. $\endgroup$ – Álvaro Lozano-Robledo Jun 27 '13 at 14:23
  • $\begingroup$ @Á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$ $\endgroup$ – Peanut Jun 27 '13 at 14:35
  • 1
    $\begingroup$ $9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17$. $\endgroup$ – Álvaro Lozano-Robledo Jun 27 '13 at 14:39
  • 1
    $\begingroup$ I asked nearly this identical question on Crypto crypto.stackexchange.com/questions/64456, and the answer there may also be worth looking at. $\endgroup$ – Brian M. Hunt Dec 1 '18 at 13:44
6
$\begingroup$

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.$$

$\endgroup$

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.