Use a 4-bit wide window for point multiplication

1 files changed, 21 insertions, 14 deletions

diff --git a/src/math/numbertheory/point_gfp.cpp b/src/math/numbertheory/point_gfp.cpp
index c5a4abf91..4761495f4 100644
--- a/src/math/numbertheory/point_gfp.cpp
+++ b/src/math/numbertheory/point_gfp.cpp
@@ -215,18 +215,26 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
       return *this;
       }
 
-   PointGFp H(this->curve); // create as zero
-   PointGFp P(*this);
+   const u32bit scalar_bits = scalar.bits();
+
+   const u32bit window_size = 4;
 
+   std::vector<PointGFp> Ps((1 << window_size) - 1);
+   Ps[0] = *this;
    if(scalar.is_negative())
-      P.negate();
+      Ps[0].negate();
 
-   const u32bit scalar_bits = scalar.bits();
+   for(u32bit i = 1; i != Ps.size(); ++i)
+      {
+      Ps[i] = Ps[i-1];
 
-   PointGFp P2 = P * 2;
-   PointGFp P3 = P2 + P;
+      if(i % 1 == 1)
+         Ps[i].mult2(ws);
+      else
+         Ps[i].add(Ps[0], ws);
+      }
 
-   u32bit window_size = 2;
+   PointGFp H(this->curve); // create as zero
    u32bit bits_left = scalar_bits;
 
    while(bits_left >= window_size)
@@ -236,12 +244,8 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
       for(u32bit i = 0; i != window_size; ++i)
          H.mult2(ws);
 
-      if(nibble == 3)
-         H.add(P3, ws);
-      else if(nibble == 2)
-         H.add(P2, ws);
-      else if(nibble == 1)
-         H.add(P, ws);
+      if(nibble)
+         H.add(Ps[nibble-1], ws);
 
       bits_left -= window_size;
       }
@@ -250,11 +254,14 @@ PointGFp& PointGFp::operator*=(const BigInt& scalar)
       {
       H.mult2(ws);
       if(scalar.get_bit(bits_left-1))
-         H.add(P, ws);
+         H.add(Ps[0], ws);
 
       --bits_left;
       }
 
+   if(scalar.is_negative())
+      H.negate();
+
    *this = H;
    return *this;
    }