The validity of the formula ${\displaystyle A=Z^{\frac {2}{1-p^{6}}}}$ relies on Galois Theory applied to the tower of finite fields constructed by the embedding degree ${\displaystyle k=12}$ and the existence of a Sextic Twist.

Let ${\displaystyle E}$ be a BN or BLS12 curve defined over the prime field ${\displaystyle \mathbb {F} _{p}}$.

• Embedding Degree ${\displaystyle k=12}$: The pairing target group is a subgroup of the multiplicative group ${\displaystyle \mathbb {F} _{p^{12}}^{*}}$.
• Order ${\displaystyle r}$: The prime order of the subgroups ${\displaystyle G_{1}}$ and ${\displaystyle G_{2}}$.
• Groups:
  • ${\displaystyle G_{1}=E(\mathbb {F} _{p})[r]}$ (Points with coordinates in the base field).
  • ${\displaystyle G_{2}\subset E(\mathbb {F} _{p^{12}})[r]}$ is the trace-zero subgroup, which is isomorphic to ${\displaystyle E'(\mathbb {F} _{p^{2}})[r]}$ via a sextic twist.

We define the Weil Pairing ${\displaystyle e_{W}:G_{1}\times G_{2}\to \mu _{r}}$, where ${\displaystyle \mu _{r}}$ is the group of ${\displaystyle r}$-th roots of unity in ${\displaystyle \mathbb {F} _{p^{12}}}$.

${\displaystyle Z=e_{W}(P,Q)=(-1)^{r}{\frac {f_{P}(Q)}{f_{Q}(P)}}}$

Let ${\displaystyle A=f_{P}(Q)}$ and ${\displaystyle B=f_{Q}(P)}$.

Theorem: For ${\displaystyle P\in G_{1}}$ and ${\displaystyle Q\in G_{2}}$, the value ${\displaystyle B=f_{Q}(P)}$ lies in the subfield ${\displaystyle \mathbb {F} _{p^{2}}}$.

Proof:

1. Miller Loop Construction: The function ${\displaystyle f_{Q}}$ is a rational function on the curve constructed via Miller's algorithm. The coefficients of ${\displaystyle f_{Q}}$ are arithmetic combinations of the coordinates of ${\displaystyle Q}$ and the curve parameters.
2. The Twist: Since ${\displaystyle Q\in G_{2}}$, it is the image of a point ${\displaystyle Q'\in E'(\mathbb {F} _{p^{2}})}$ under the twisting isomorphism ${\displaystyle \psi :E'\to E}$. Consequently, the coordinates of ${\displaystyle Q}$ (and the line functions used to build ${\displaystyle f_{Q}}$) are defined over ${\displaystyle \mathbb {F} _{p^{2}}}$ (up to scaling factors that cancel out or remain in the subfield during the accumulation step).
3. Evaluation Point: The function ${\displaystyle f_{Q}}$ is evaluated at ${\displaystyle P}$. Since ${\displaystyle P\in E(\mathbb {F} _{p})}$, its coordinates ${\displaystyle x_{P},y_{P}}$ are in ${\displaystyle \mathbb {F} _{p}}$.
4. Closure: ${\displaystyle \mathbb {F} _{p}}$ is a subfield of ${\displaystyle \mathbb {F} _{p^{2}}}$. Therefore, evaluating a function with coefficients in ${\displaystyle \mathbb {F} _{p^{2}}}$ at a point in ${\displaystyle \mathbb {F} _{p}}$ yields a result in ${\displaystyle \mathbb {F} _{p^{2}}}$.

Conclusion: ${\displaystyle B\in \mathbb {F} _{p^{2}}}$.

In a generic scenario (or on curves without the specific Type 3 / Twist structure), having an algorithm that inverts the Miller loop (finding ${\displaystyle Y}$ from ${\displaystyle f_{X}(Y)}$) is insufficient to invert the Weil pairing.

The Problem: You are given the target ${\displaystyle Z_{Weil}}$. The equation is:

${\displaystyle Z_{Weil}={\frac {f_{X}(Y)}{f_{Y}(X)}}}$

To use your Miller Inversion algorithm, you need to isolate the numerator ${\displaystyle f_{X}(Y)}$. You would try to rearrange the equation:

${\displaystyle f_{X}(Y)=Z_{Weil}\cdot f_{Y}(X)}$

The Circular Deadlock:

• To find ${\displaystyle Y}$ using, you need the value of the Right Hand Side.
• But the Right Hand Side contains ${\displaystyle f_{Y}(X)}$.
• The value of ${\displaystyle f_{Y}(X)}$ depends on ${\displaystyle Y}$.
• Result: You cannot calculate the input for your inversion algorithm without already knowing the answer ${\displaystyle Y}$.

In standard literature, resolving this dependency (${\displaystyle Y}$ appearing in both numerator and denominator) generally requires guessing bits of ${\displaystyle Y}$ or solving a Discrete Logarithm, which drives the complexity up to exponential levels.

In your specific case (BN curves), the denominator is not an independent variable. It is algebraically coupled to the numerator via the Frobenius automorphism.

Because ${\displaystyle G_{2}}$ comes from a twist over a subfield, we proved that:

${\displaystyle f_{Y}(X)=(f_{X}(Y))^{p^{6}}}$

This substitution breaks the circular dependency by turning the equation into a single variable problem.

On a BN curve (Type 3), the points are separated:

• ${\displaystyle X\in G_{1}}$ is defined over the base field ${\displaystyle \mathbb {F} _{p}}$.
• ${\displaystyle Y\in G_{2}}$ is defined over the twist ${\displaystyle \mathbb {F} _{p^{2}}}$.

Let's look at the two Miller loops composing your Weil target:

1. Numerator ${\displaystyle A=f_{X}(Y)}$: This is a function derived from ${\displaystyle X}$ (${\displaystyle \mathbb {F} _{p}}$) evaluated at ${\displaystyle Y}$ (${\displaystyle \mathbb {F} _{p^{12}}}$). The result lives in the full extension ${\displaystyle \mathbb {F} _{p^{12}}}$.
2. Denominator ${\displaystyle B=f_{Y}(X)}$: This is a function derived from ${\displaystyle Y}$ (coefficients in ${\displaystyle \mathbb {F} _{p^{2}}}$) evaluated at ${\displaystyle X}$ (${\displaystyle \mathbb {F} _{p}}$).
   • Crucial Consequence: The result ${\displaystyle B}$ belongs to the subfield ${\displaystyle \mathbb {F} _{p^{2}}}$ (embedded in ${\displaystyle \mathbb {F} _{p^{12}}}$).

For the inversion algorithm (which works on the full ${\displaystyle \mathbb {F} _{p^{12}}}$ structure), the denominator is a "small" structural element compared to the complexity of the numerator.

On BN curves, the Weil Pairing ${\displaystyle e_{W}(X,Y)}$ and the Tate Pairing/Miller Loop ${\displaystyle f_{X}(Y)}$ are linked by a fixed and known power relation for all points in the group.

${\displaystyle e_{W}(X,Y)=(f_{X}(Y))^{\lambda }}$

• Why? Because the denominator ${\displaystyle f_{Y}(X)}$ is linked to the numerator via the Frobenius endomorphism (anti-trace).
• The value of ${\displaystyle \lambda }$: This is not a secret. It is an integer that depends solely on the curve parameters. On many BN curves, this is linked to ${\displaystyle (1-p^{6})}$.

The Polynomial Reduction: Instead of: :${\displaystyle Z_{Weil}={\frac {{\text{Unknown}}_{1}(Y)}{{\text{Unknown}}_{2}(Y)}}}$ You have: :${\displaystyle Z_{Weil}={\frac {{\text{Unknown}}_{1}(Y)}{({\text{Unknown}}_{1}(Y))^{p^{6}}}}={\text{Unknown}}_{1}(Y)^{1-p^{6}}}$ The Solution Path: Since ${\displaystyle (1-p^{6})}$ is a known constant integer, you can simply invert this exponent modulo ${\displaystyle r}$: :${\displaystyle f_{X}(Y)=(Z_{Weil})^{(1-p^{6})^{-1}{\pmod {r}}}}$ ==== The ${\displaystyle p^{6}}$ Frobenius Trick (Conjugation) ==== In the field ${\displaystyle \mathbb {F} _{p^{12}}}$, the operation ${\displaystyle x\mapsto x^{p^{6}}}$ acts as a complex conjugation relative to the quadratic extension. * Property of the Result ${\displaystyle Z}$ (Pairing): : ${\displaystyle Z}$ is an ${\displaystyle r}$-th root of unity. On BN curves, modulo the order ${\displaystyle r}$, we have ${\displaystyle p^{6}\equiv -1}$. : Therefore, for any valid pairing result ${\displaystyle Z}$: :${\displaystyle Z^{p^{6}}=Z^{-1}}$ * Property of the Denominator ${\displaystyle B}$: : Since ${\displaystyle B\in \mathbb {F} _{p^{2}}}$, it is invariant under ${\displaystyle x\mapsto x^{p^{2}}}$. A fortiori, it is invariant under ${\displaystyle x\mapsto x^{p^{6}}}$ (since ${\displaystyle p^{6}}$ is a multiple of ${\displaystyle p^{2}}$). :${\displaystyle B^{p^{6}}=B}$

We have the following system: # ${\displaystyle Z=A/B}$ # ${\displaystyle Z^{-1}=Z^{p^{6}}}$ (Target group property) # ${\displaystyle B^{p^{6}}=B}$ (Subfield property) Apply the Frobenius ${\displaystyle p^{6}}$ to equation (1): :${\displaystyle Z^{p^{6}}={\frac {A^{p^{6}}}{B^{p^{6}}}}}$ Substitute using properties (2) and (3): :${\displaystyle Z^{-1}={\frac {A^{p^{6}}}{B}}}$ We now have two expressions involving ${\displaystyle B}$: * From (1): ${\displaystyle B=A/Z}$ * From derived equation: ${\displaystyle B=Z\cdot A^{p^{6}}}$ Equating the two expressions for ${\displaystyle B}$: :${\displaystyle A/Z=Z\cdot A^{p^{6}}}$ :${\displaystyle Z^{2}=A/A^{p^{6}}=A^{1-p^{6}}}$

You are looking for ${\displaystyle A=f_{P}(Q)}$ (the input for inversion) given ${\displaystyle Z}$ (your Weil target). The final equation is: :${\displaystyle A=Z^{\frac {2}{1-p^{6}}}}$ *((The exponent is calculated modulo the group order ${\displaystyle r}$. Division by ${\displaystyle 1-p^{6}}$ is multiplication by the modular inverse).)* Why does this work without knowing the denominator? Because the denominator ${\displaystyle B}$ is "eaten" by the operation. By squaring and playing with the conjugate, we exploit the fact that ${\displaystyle B}$ is "real" (invariant under ${\displaystyle p^{6}}$) while ${\displaystyle A}$ is "complex". This eliminates ${\displaystyle B}$ from the equation.

You have effectively reduced the "Weil Inversion Problem" to the "Miller Inversion Problem" using simple arithmetic. If your algorithm solves Miller Inversion in polynomial time, the entire Weil inversion becomes polynomial.