0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You talked about naive multiplication, is the double-and-add algorithm from wikipedia a naive multiplication ? $\endgroup$ – user1990088 Aug 28 '18 at 10:41
  • $\begingroup$ @user1990088 these are different things: double-and-add is a point multiplication algorithm (which is also part of Miller's loop), and each double and add is compose of a bunch of field multiplications and squarings. The "naive" and Karatsuba algorithms are used to implement the field multiplications/squarings. $\endgroup$ – Conrado Aug 29 '18 at 1:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.