A couple days ago I wrote about two pair of closely related elliptic curves: Tweedledum and Tweedledee, and Pallas and Vesta.
In each pair, the order of one curve is the order of the base field of the other curve. The curves in each pair are used together in cryptography, but they don’t form a “pairing” in the technical sense of a bilinear pairing, and in fact none of the curves are “pairing-friendly” as descried below.
An elliptic curve E/Fq is said to be pairing-friendly if r divides qk − 1 for some small k. Here r is the size of the largest prime-order subgroup of the curve, but since our curves have prime order p, r = p.
As for what constitutes a small value of k, something on the order of 10 would be considered small. The larger k is, the less pairing-friendly the curve is. We will show that our curves are extremely pairing-unfriendly.
Since q is not a multiple of p in our examples, there must be some power of q such at
qk = 1 mod p.
The question is whether k is large, i.e. whether the order of q mod p is large. We could try successive values of k, but that won’t get us very far. To be more clever, we use Lagrange’s theorem that says the order of an element divides the order of the group. So k must be one of the factors of p − 1. (We subtract 1 because we’re looking at the multiplicative group mod p, which removes 0.)
Finding the divisors of n − 1 requires factoring n − 1, which isn’t easy, but isn’t insurmountable either. The previous post reports the time required to do this in Python and in Mathematica for each of the following values of n.
p = 2254 + 4707489544292117082687961190295928833
q = 2254 + 4707489545178046908921067385359695873
r = 2254 + 45560315531419706090280762371685220353
s = 2254 + 45560315531506369815346746415080538113
Tweedledum has order p and its base field has order q.
k = 28948022309329048855892746252171976963322203655954433126947083963168578338816
Tweedledee has order q and its base field has order p.
k = 28948022309329048855892746252171976963322203655955319056773317069363642105856
Vesta has order r and its base field has order s.
k = 14474011154664524427946373126085988481681528240970780357977338382174983815168
Pallas has order s and its base field has order r.
k = 14474011154664524427946373126085988481681528240970823689839871374196681474048
It’s safe to say in each case k is not a small number.