From 26d74e8b65afeb856967cc264269cea9e1e7d2eb Mon Sep 17 00:00:00 2001 From: Vlad Krasnov Date: Fri, 9 Mar 2018 17:14:49 +0000 Subject: [PATCH] math/big: reduce amount of copying in Montgomery multiplication MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Instead shifting the accumulator every iteration of the loop, shift once in the end. This significantly improves performance on arm64. On arm64: name old time/op new time/op delta RSA2048Decrypt 3.33ms ± 0% 2.63ms ± 0% -20.94% (p=0.000 n=11+11) RSA2048Sign 4.22ms ± 0% 3.55ms ± 0% -15.89% (p=0.000 n=11+11) 3PrimeRSA2048Decrypt 1.95ms ± 0% 1.59ms ± 0% -18.59% (p=0.000 n=11+11) On Skylake: name old time/op new time/op delta RSA2048Decrypt-8 1.73ms ± 2% 1.55ms ± 2% -10.19% (p=0.000 n=10+10) RSA2048Sign-8 2.17ms ± 2% 2.00ms ± 2% -7.93% (p=0.000 n=10+10) 3PrimeRSA2048Decrypt-8 1.10ms ± 2% 0.96ms ± 2% -13.03% (p=0.000 n=10+9) Change-Id: I5786191a1a09e4217fdb1acfd90880d35c5855f7 Reviewed-on: https://go-review.googlesource.com/99838 Run-TryBot: Vlad Krasnov TryBot-Result: Gobot Gobot Reviewed-by: Adam Langley Reviewed-by: Robert Griesemer --- src/math/big/nat.go | 17 +++++++++-------- 1 file changed, 9 insertions(+), 8 deletions(-) diff --git a/src/math/big/nat.go b/src/math/big/nat.go index 3de32d27e9..1f259410c4 100644 --- a/src/math/big/nat.go +++ b/src/math/big/nat.go @@ -213,18 +213,17 @@ func (z nat) montgomery(x, y, m nat, k Word, n int) nat { if len(x) != n || len(y) != n || len(m) != n { panic("math/big: mismatched montgomery number lengths") } - z = z.make(n) + z = z.make(n * 2) z.clear() var c Word for i := 0; i < n; i++ { d := y[i] - c2 := addMulVVW(z, x, d) - t := z[0] * k - c3 := addMulVVW(z, m, t) - copy(z, z[1:]) + c2 := addMulVVW(z[i:n+i], x, d) + t := z[i] * k + c3 := addMulVVW(z[i:n+i], m, t) cx := c + c2 cy := cx + c3 - z[n-1] = cy + z[n+i] = cy if cx < c2 || cy < c3 { c = 1 } else { @@ -232,9 +231,11 @@ func (z nat) montgomery(x, y, m nat, k Word, n int) nat { } } if c != 0 { - subVV(z, z, m) + subVV(z[:n], z[n:], m) + } else { + copy(z[:n], z[n:]) } - return z + return z[:n] } // Fast version of z[0:n+n>>1].add(z[0:n+n>>1], x[0:n]) w/o bounds checks. -- 2.50.0