## 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$$.

Ben Lynn blynn@cs.stanford.edu 💡