The fact that each element of \(\mathbb{F}_q\) has order \(q-1\) can be used to shave time off the final exponentiation of a Tate pairing computation. Suppose we wish to raise \(a \in \mathbb{F}_{q^k}\) to the power of

Since \(k\) is the embedding degree, we have \(r | \Phi_k(q)\) (and no smaller cyclotomic polynomial, otherwise the embedding degree would be smaller). Then compute \(a^n\) by first computing \(a^{(q^k - 1)/\Phi_k(q)}\) using a few multiplications and inversions by exploiting the fact that \(x^q = x\) for all \(x\in\mathbb{F}_q\), and then exponentiating by \(\Phi_k(q)/r\) in the usual way.

For example, suppose \(k = 2\), and that we have implemented \(\mathbb{F}_{q^2}\) as \(\mathbb{F}_q [\alpha]\). (A common choice is \(\alpha = i = \sqrt{-1}\).) We have \(r | \Phi_2(q) = q + 1\). Write \(a = u + \alpha v\) where \(u, v \in \mathbb{F}_q\). Then

where \(\alpha^q\) is some constant that can be precomputed. [In particular, if \(\alpha^2 = b \in \mathbb{F}_q\) for some quadratic nonresidue \(b\) then \(\alpha^q = \alpha b^{(q-1)/2} = -\alpha\).] Then exponentiate by \((q+1)/r\) to obtain \((a^{q-1})^{(q+1)/r} = a^n\).

Another example. Suppose \(k = 6\) and \(\mathbb{F}_{q^6} = \mathbb{F}_q[\alpha]\), and we wish to find \(a^{(q^6 - 1)/r}\) for some \(a \in \mathbb{F}_{q^6}\). We have \(q^6 - 1 = \Phi_6(q) (q^4 + q^3 - q - 1)\) where \(\Phi_6(q) = q^2 - q + 1\). Write \(a = u_0 + u_1 \alpha + ... + u_5 \alpha^5\). Then compute

Each power of \(\alpha^q\) can be precomputed. Finally exponentiate by \((q^2 - q + 1) / r\).