FAQ
Reviewers: gri,

Message:
Hello gri@golang.org (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/


Description:
math/big: add 4-bit, fixed window exponentiation.

A 4-bit window is convenient because 4 divides both 32 and 64,
therefore we never have a window spanning words of the exponent.
Additionaly, the benefit of a 5-bit window is only 2.6% at 1024-bits
and 3.3% at 2048-bits.

This code is still not constant time, however.

benchmark old ns/op new ns/op delta
BenchmarkRSA2048Decrypt 17108590 11180370 -34.65%
Benchmark3PrimeRSA2048Decrypt 13003720 7680390 -40.94%

Please review this at http://codereview.appspot.com/6716048/

Affected files:
M src/pkg/math/big/nat.go


Index: src/pkg/math/big/nat.go
===================================================================
--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -1246,6 +1246,16 @@
z = z.make(len(m))
}
z = z.set(x)
+
+ // If the exponent is large and the base is non-trivial, we use a
+ // 4-bit, windowed exponentiation. This involves precomputing 14 values
+ // (x^2...x^15) but then reduces the number of multiply-reduces by a
+ // third. Even for a 32-bit exponent, this reduces the number of
+ // operations.
+ if len(y) > 1 && len(x) > 1 && m != nil {
+ return z.expNNWindowed(x, y, m)
+ }
+
v := y[len(y)-1]
// It's invalid for the most significant word to be zero, therefore we
// will find a one bit.
@@ -1304,6 +1314,67 @@
return z.norm()
}

+// expNNWindowed calculates x**y mod m using a fixed, 4-bit window.
+func (z nat) expNNWindowed(x, y, m nat) nat {
+ // zz and r are used to avoid allocating in mul and div as otherwise
+ // the arguments would alias.
+ var zz, r nat
+
+ // powers[i] contains x^i.
+ var powers [16]nat
+ powers[0] = powers[0].make(1)
+ powers[0][0] = 1
+ powers[1] = x
+ for i := 2; i < 16; i += 2 {
+ powers[i] = powers[i].mul(powers[i/2], powers[i/2])
+ zz, r = zz.div(r, powers[i], m)
+ powers[i], r = r, powers[i]
+ powers[i+1] = powers[i+1].mul(powers[i], x)
+ zz, r = zz.div(r, powers[i+1], m)
+ powers[i+1], r = r, powers[i+1]
+ }
+
+ z = z.make(1)
+ z[0] = 1
+
+ for i := len(y) - 1; i >= 0; i-- {
+ word := y[i]
+ for j := 0; j < _W; j += 4 {
+ if i != len(y)-1 || j != 0 {
+ // Manually unrolling this speeds the code up by ~15%.
+ zz = zz.mul(z, z)
+ zz, z = z, zz
+ zz, r = zz.div(r, z, m)
+ z, r = r, z
+
+ zz = zz.mul(z, z)
+ zz, z = z, zz
+ zz, r = zz.div(r, z, m)
+ z, r = r, z
+
+ zz = zz.mul(z, z)
+ zz, z = z, zz
+ zz, r = zz.div(r, z, m)
+ z, r = r, z
+
+ zz = zz.mul(z, z)
+ zz, z = z, zz
+ zz, r = zz.div(r, z, m)
+ z, r = r, z
+ }
+
+ zz = zz.mul(z, powers[word>>(_W-4)])
+ zz, z = z, zz
+ zz, r = zz.div(r, z, m)
+ z, r = r, z
+
+ word <<= 4
+ }
+ }
+
+ return z.norm()
+}
+
// probablyPrime performs reps Miller-Rabin tests to check whether n is
prime.
// If it returns true, n is prime with probability 1 - 1/4^reps.
// If it returns false, n is not prime.

Search Discussions

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-dev @
categoriesgo
postedOct 16, '12 at 8:34p
activeOct 17, '12 at 3:19p
posts5
users2
websitegolang.org

2 users in discussion

Agl: 3 posts Gri: 2 posts

People

Translate

site design / logo © 2022 Grokbase