Programming ECC

The fact that each element of ${𝔽}_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 {𝔽}_{q^k}$ to the power of

$$n=\frac{q^k-1}{r}=r^{-1}\prod _{d\mid k}{\Phi }_d(q)$$

Since $k$ is the embedding degree, we have $r\mid {\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 {𝔽}_q$, and then exponentiating by ${\Phi }_k(q)/r$ in the usual way.

For example, suppose $k=2$, and that we have implemented ${𝔽}_{q^2}$ as ${𝔽}_q[\alpha ]$. (A common choice is $\alpha =i=\sqrt{-1}$.) We have $r\mid {\Phi }_2(q)=q+1$. Write $a=u+\alpha v$ where $u,v\in {𝔽}_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 {𝔽}_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 ${𝔽}_{q^6}={𝔽}_q[\alpha ]$, and we wish to find $a^{(q^6-1)/r}$ for some $a\in {𝔽}_{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$.