Replace k/2-th Frobenius powers by conjugations

[yelhousni]

This PR replaces k/2-th Frobenius powers by conjugations in the final exponentiation of the pairing implementation for the curves BN, BLS12, BW6, MNT6, MNT4. Type: Enhancement Label: Ready to review Priority: Medium

Motivation

In Tate-based pairings, the target group GT is the r-th root of unity in Fq^k where q is the finite field prime, r the curve subgroup order and k the embedding degree. The pairing requires also a final exponentiation to (q^k-1)/r to reduce the output to a unique value. Using k-th cyclotomic polynomial, the exponent can be simplified into an easy part (q^k-1)/phi_k(q) and a hard part phi_k(q)/r. The easy part can be computed cheaply using Frobenius powers. However, if there is a power to k/2 it should be replaced by a simple conjugation. An element f in Fq^k satisfies f^(q^k-1)=1 which means f^(q^(k/2)+1)=1 (otherwise the order isn't q^k-1). So an inverse is a power to q^(k/2) but since there is a q^(k/2)-1 component in that exponent, the element f becomes unitary (i.e. norm 1) and the inversion becomes a simple conjugation.

Description

This PR replaces frobenius_map(6) by conjugate() in BN and BLS12 pairing implementation frobenius_map(3) by conjugate() in MNT6 and BW6 and frobenius_map(2) by conjugate() in MNT4.

[Pratyush]

This looks great, I'll merge once CI passes.