The Tate Exponentiation

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

\[ n = \frac{q^k - 1}{r} = r^{-1} \prod_{d | k} \Phi_d(q) \]

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

\[ a^{q-1} = (u + \alpha v)^q a^{-1} = (u + \alpha^q v)/a \]

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

\[ a^{q^4 + q^3 - q - 1} =\frac{(u_0 + u_1 \alpha^{q^4} + ... + u_5 \alpha^{5q^4}) (u_0 + u_1 \alpha^{q^3} + ... + u_5 \alpha^{5q^3})} { (u_0 + u_1 \alpha^q + ... + u_5 \alpha^{5q})a } \]

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