Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Are you familiar at all with modular arithmetic? $77=9$ in $\mathbb{Z}_{17}$. –  fretty Jun 27 '13 at 14:21
1  
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
1  
$9\cdot 9 = 81 = 13 + 68 = 13 + 4\cdot 17 \equiv 13 \bmod 17$. –  Álvaro Lozano-Robledo Jun 27 '13 at 14:39
    
@ÁlvaroLozano-Robledo I'm an idiot. Had it in my head $9\cdot9$ was 89 otherwise I'd have got that bit. Thanks. Post those two comments or a similar explanation as an answer and I'll accept. Thanks again. –  Peanut Jun 27 '13 at 14:41

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.