Time complexity of Weil pairing

Question

I ran and timed an implementation of the Weil pairing on three set of parameters. One with an order of 512 bits, one with 256 bits and the last with 161 bits.

I took the Miller's algorithm to compute the Weil pairing. The algorithm that I used for the multiplication of 2 points is the double-and-add. Both algorithms have a time complexity of $O(log (n))$ if I understood correctly.

The time I got was 10 seconds for 512 bits, 2,5 seconds for 256 bits and 1,1 seconds for 161 bits. When I see the time I got it seems more like a complexity of $O(n^2)$ or $O(n \cdot log (n))$.

Can someone tell me what the time complexity is based on my results?

Answer 1

Miller's algorithm is a loop over the group size; let's say it has $n$ bits. (The group size is usually near the prime $p$ of the underlying field)

Each iteration of the loop computes a point doubling and maybe a point addition, and a bunch of field multiplications (or squarings). That sets a upper limit of a constant number of field multiplications in each iteration. The complexity of naive multiplication is $O(n^2)$; with Karatsuba it is $O(n^{\log_2{3}}) = O(n^{1.585})$. Therefore that's the complexity of each iteration.

Thus, since there are $n$ iterations, the complexity of Miller's algorithm is $O(n^3)$ with naive multiplication and $O(n^{2.585})$ with Karatsuba.