Type E Internals

The CM (Complex Multiplication) method of constructing elliptic curves starts with the Diophantine equation

DV^2 = 4q - t^2

If t = 2 and q = D r2 h2 + 1 for some prime r (which we choose to be a Solinas prime) and some integer h, we find that this equation is easily solved with V = 2rh.

Thus it is easy to find a curve (over the field F_q) with order q - 1. Note r2 divides q - 1, thus we have an embedding degree of 1.

Hence all computations necessary for the pairing can be done in F_q alone. There is never any need to extend F_q.

As q is typically 1024 bits, group elements take a lot of space to represent. Moreover, many optimizations do not apply to this type, resulting in a slower pairing.

e_param struct fields:

exp2, exp1, sign1, sign0, r:
  r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime)
q, h
  q = h r^2 + 1 where r is prime, and h is 28 times a perfect square
a, b
  E: y^2 = x^3 + ax + b