Paper 2026/1049

Decomposition of the Ate Pairing and its Relation to Generalized Pairing Inversion

Abstract

In this note, we study decomposition of the Ate pairing on certain elliptic curves defined over finite fields. As an application, we reduce a generalized pairing inversion to root findings of an element of the affine coordinate ring appearing in the decomposition. For a supersingular curve $E / {\bf F}_q$ satisfying $\sharp E( {\bf F}_q ) = q+1$, heuristic observation suggests that a number of calls to a root finding algorithm seems to $O( N )$ where $N$ is the maximal power of $2$ dividing $q+1$. It is remarkable that the resulting algorithm does not utilize fixed argument pairing inversions. An underlying key observation is that the Miller function forms a factor system.