Optimizing scalar multiplication and exponentiation like algorithms

[hecmas]

Description

Say that we are in a group $(\mathbb{G}, +)$ or prime order $r$. We are given an element $Q \in_R \mathbb{G}$ and we are asked to compute $k\cdot Q$ for some $k_R \in [1, r-1]$.

There are many methods we can use to optimize this operation:

• Generic methods:

  • Precompute tables that depend on $Q$, when $Q$ is known a priori.
  • Addition chains which are useful when $k$ is fixed.
  • Windowing techniques.
  • Exponent recoding, which replace the binary representation of $k$ with a representation that has fewer non-zero terms. The most optimal of such representations being NAF.
  • Combining the last two, obtaining the optimal wNAF method.

• Methods particular to elliptic curves:

  • The GLV method, explained in this post.
  • The GLS method.
  • Techniques related to choosing a better underlying field or the elliptic curve, change the point coordinates...

Numbers

Test 1/3:
    Double-and-add style: total time is 14m11.334s
    wNAF method for scalar multiplication with w = 3: total time is 11m59.115s
    GLV method with wNAF double scalar multiplication with w = 3: total time is 13m13.886s

Test 2/3:
    Double-and-add style: total time is 14m10.720s
    wNAF method for scalar multiplication with w = 4: total time is 11m33.297s
    GLV method with wNAF double scalar multiplication with w = 4: total time is 12m35.619s

Test 3/3:
    Double-and-add style: total time is 14m8.215s
    wNAF method for scalar multiplication with w = 5: total time is 11m21.073s
    GLV method with wNAF double scalar multiplication with w = 5: total time is 12m31.586s

[ignasirv]

The post access is restricted :)

[hecmas]

The post access is restricted :)

Fixed :)

Warning: Math Heavy