Type A internals

Type A pairings are constructed on the curve y2 = x3 + x over the field F_q for some prime q = 3 mod 4. Both G1 and G2 are the group of points E(F_q), so this pairing is symmetric. It turns out #E(F_q) = q + 1 and #E(F_q2) = (q + 1)2. Thus the embedding degree k is 2, and hence GT is a subgroup of F_q^2. The order r is some prime factor of q + 1.

Write q + 1 = r * h. For efficiency, r is picked to be a Solinas prime, that is, r has the form 2a +- 2b +- 1 for some integers 0 < b < a.

Also, we choose q = -1 mod 12 so F_q2 can be implemented as F_q[i] (where i = sqrt(-1)) and since q = -1 mod 3, cube roots in F_q are easy to compute. This latter feature may be removed because I have not found a use for it yet (in which case we only need q = -1 mod 4).

a_param struct fields:

exp2, exp1, sign1, sign0, r:
  r = 2^exp2 + sign1 * 2^exp1 + sign0 * 1 (Solinas prime)
q, h:
  r * h = q + 1
  q is a prime, h is a multiple of 12 (thus q = -1 mod 12)

Type A1 uses the same equation, but have different fields since the library is given r and cannot choose it.

a1_param struct fields:

p, n, l:
  p + 1 = n * l
  p is prime, same as the q in a_param, n is the order of the group.