Miller's algorithm iteratively computes the rational function f_P(R) needed for elliptic-curve pairings. It takes two curve points, including a reference point R, and returns a field element. The procedure mirrors double-and-add multiplication by the point order m: each processed bit doubles the running point, and each set bit adds P. section 15.2 section 15.2.2
The computation follows this execution flow:
- Initialize T with P and f with the multiplicative identity 1; scan the remaining bits of m from the most significant side. section 15.4
- For every bit, evaluate h_{T,T}(R) using the tangent slope, square f, multiply by h, and replace T with 2T. section 15.2.2 section 15.4
- When the bit is set, evaluate h_{T,P}(R), multiply f by it, and replace T with T+P. section 15.2.2 section 15.4
- Perform the arithmetic over the curve's field extension, where values are polynomials reduced modulo the defining prime polynomial. section 15.2.2
C-style implementation
The miller() routine keeps T, a temporary h, and f. It derives the loop mask from m, calls hpq() for doubling and addition, uses poly_mul() for function updates, and uses poly_elptic_sum() for point updates. It clears temporary points and polynomials afterward. Weil pairing calls Miller four times and combines the results; Tate pairing calls it twice, divides the results, and raises the quotient to (p^k−1)/m. section 15.4 section 16.2 section 17.2
Figure 15.5 Miller’s algorithm flow chart
Follow the flow chart while mapping each doubling and set-bit branch to the running point T and field element f. section 15.2.2
Listing 15.4 Miller’s algorithm routine
void miller(POLY *f, POLY_POINT P, POLY_POINT R, mpz_t m, POLY_CURVE E)
{
POLY_POINT T;
POLY h;
long mask;
mask = mpz_sizeinbase(m, 2) - 2; #1
poly_point_init(&T);
poly_point_copy(&T, P); #2
f->deg = 0; #2
mpz_set_ui(f->coef[0], 1); #2
poly_init(&h);
while(mask >= 0) #3
{
hpq(&h, T, T, R, E); #4
poly_mul(f, *f, *f); #4
poly_mul(f, *f, h); #4
poly_elptic_sum(&T, T, T, E); #5
if(mpz_tstbit(m, mask)) #6
{
hpq(&h, T, P, R, E); #7
poly_mul(f, *f, h); #7
poly_elptic_sum(&T, T, P, E); #8
}
mask--; #9
}
poly_point_clear(&T); #10
poly_clear(&h); #10
}
Inspect the complete routine beside the flow: initialization, masked-bit loop, polynomial updates, point additions, and cleanup. section 15.4
