]> Cypherpunks repositories - gostls13.git/commit
math/big: test and optimize Exp(2, y, n) for large y, odd n
authorRuss Cox <rsc@golang.org>
Mon, 10 Oct 2016 20:45:30 +0000 (16:45 -0400)
committerRuss Cox <rsc@golang.org>
Tue, 11 Oct 2016 16:15:51 +0000 (16:15 +0000)
commit9927f25d711ec7aa0876e33e3bd174e09cc032bd
treea245834be56ebff7a031c48873095fd6f55e255b
parent9a8832f1422f7fa72e4855757e4a951957cc62ae
math/big: test and optimize Exp(2, y, n) for large y, odd n

The Montgomery multiply code is applicable to this case
but was being bypassed. Don't do that.

The old test len(x) > 1 was really just a bad approximation to x > 1.

name    old time/op  new time/op  delta
Exp-8   5.56ms ± 4%  5.73ms ± 3%     ~     (p=0.095 n=5+5)
Exp2-8  7.59ms ± 1%  5.66ms ± 1%  -25.40%  (p=0.008 n=5+5)

This comes up especially when doing Fermat (Miller-Rabin)
primality tests with base 2.

Change-Id: I4cc02978db6dfa93f7f3c8f32718e25eedb4f5ed
Reviewed-on: https://go-review.googlesource.com/30708
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
src/math/big/int_test.go
src/math/big/nat.go