# Elliptic curves

An elliptic curve is, in essence, simply the set of solutions (or points

*(x, y*)) to an equation that can be represented in the form*y*^2*= x*^*3 + ax + b*, where*a*and*b*, as well as points (*x, y*) that lie on the curve (that is, are solutions to the equation), belong to a finite field*F_p*defined by a prime*p*. That is,*F_p*is the set*{0, 1, . . . , p − 1}*, with addition and multiplication being*modulo p*.Elliptic curves are of interest in cryptography because points can be added together, with the result also being a point on the curve. Furthermore, the set of points obtained by taking a point

*G*(a generator) and adding it to itself repeatedly until reaching (or returning to) the starting point*G*, forms a group whose order (denoted here as*q*) is the number of points in the set. The relevance of this is that there is a class of asymmetric (or public key) cryptographic protocols known as the discrete log-based systems, and which include DSA and the Diffie-Hellman protocol, which are defined to work in a group. There are many different types of groups, but for cryptographic security, the so-called*discrete log problem*must be a complex problem to solve (for sufficiently large parameters). Two groups for which this problem is considered difficult are the group defined by the set of integers modulo a large prime*p*, and the group of points on an elliptic curve.When used for cryptographic purposes, the order

*q*is typically a large prime number and defines the scalar field of the curve.Examples of elliptic curve groups include BN254 (the curve currently used by Panther), BLS12-377, and BLS12-381.

Note that in addition to size, the structure of the group of points on an elliptic curve is also important. The factorization of q − 1 defines the subgroups of

*Z_q*. The inclusion in this factorization of*2*^*s*for some sufficiently large*s*is required for using*FFTs*(for example, for multiplying polynomials), and is consequently crucial for the speed (or efficiency) of the proving process.BN254 has 2-adicity 28 (that is, there exists a multiplicative subgroup of size 2^28).