finalexponentiation

Final exponentiation is the final step in evaluating a bilinear pairing in pairing-based cryptography. After the Miller loop, the intermediate value f lies in the multiplicative group of the extension field F_{p^k}, where p is a prime and k is the embedding degree. The final exponentiation computes f^{(p^k−1)/r}, with r the order of the source groups. The resulting value lies in the unique subgroup of F_{p^k}^* of order r, ensuring the pairing output is well-defined and non-degenerate.

Rationale for this step is to project the Miller loop result into the correct target subgroup and to remove ambiguities arising from choices of representatives. This makes the pairing bilinear and non-degenerate with respect to the groups G1 and G2 mapped into GT.

Computation and optimization: The exponent (p^k−1)/r is typically very large, so the exponentiation is performed via a two-stage process. The easy part exploits the Frobenius endomorphism to raise to powers such as p^i with relatively few multiplications in the extension field. The hard part is a smaller, structured multi-exponentiation using a precomputed sparse representation of the exponent. In practice, the split between easy and hard parts depends on the specific curve and embedding degree; common instances include BN and BLS curves with embedding degree k equal to 12, where tailored final exponentiation routines are widely used.

Notes: The concept is standard in Tate and Ate pairings. Efficient final exponentiation is a core component of the practical performance of pairing-based protocols, affecting operations such as identity-based encryption, short signatures, and other cryptographic schemes that rely on pairings.