Re:(Very) Basic Intro to Elliptic Curve Cryptography
by dan-robertson on Sunday February 14, 2021 @02:15PM
(#26135222)
The number may be very large (think: much bigger than 2^64). The reason it’s possible to compute these in logarithmic time (ie linear in the number of bits of the key) is the same reason that it is possible to compute a^b (mod c) even when b is very large: there are operations in elliptic curves akin to multiplying and squaring so a^(2b_1 + b_2) = a^(b_2) (a^2)^(b_1) can have the cost of computing a^(b_1) (say b_1 is 0 or 1, so this is constant), the cost of a multiply (constant), the cost of a square (constant), and the cost of an exponentiation of a number with one less bit, hence by induction the cost is linear in the number of bits.
[ Parent
| on HN ]
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by pfortuny on Sunday February 14, 2021 @02:57PM
(#26135662)
And exponentiating is (relatively) easy beacuse
a^(xyz) = ((a^x)^y)^z
and as long as you know how to square, you can pretty much compute exponentials in log2(exponent) time.
Re:(Very) Basic Intro to Elliptic Curve Cryptography
by wagslane on Sunday February 14, 2021 @03:21PM
(#26135878)
Thanks for helping out with this explanation. I just updated the article and added an answer section briefly addressing this. Maybe check it out and let me know if you think the answer is sufficient?