# 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).

Last updated