Elliptic Curve Cryptography: finite fields and discrete logarithms

Andrea Corbellini

This post is the second in the series ECC: a gentle introduction.

In the previous post, we have seen how elliptic curves over the real numbers can be used to define a group. Specifically, we have defined a rule for point addition: given three aligned points, their sum is zero (P + Q + R =…). We have derived a geometric method and an algebraic method for computing point additions.

We then introduced scalar multiplication (nP = P + P + + P) and we found out an “easy” algorithm for computing scalar multiplication: double and add.

Now we will restrict our elliptic curves to finite fields, rather than the set of real numbers, and see how things change.

The field of integers modulo p

A finite field is, first of all, a set with a finite number of elements. An…

View original post 3,055 more words