Rietveld Code Review Tool
Help | Bug tracker | Discussion group | Source code | Sign in
(8315)

Issue 6716048: code review 6716048: math/big: add 4-bit, fixed window exponentiation. (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
10 years, 1 month ago by agl1
Modified:
10 years, 1 month ago
Reviewers:
CC:
gri, golang-dev
Visibility:
Public.

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%

Patch Set 1 #

Patch Set 2 : diff -r e64d4ee19fff https://go.googlecode.com/hg/ #

Patch Set 3 : diff -r e64d4ee19fff https://go.googlecode.com/hg/ #

Patch Set 4 : diff -r e64d4ee19fff https://go.googlecode.com/hg/ #

Patch Set 5 : diff -r 24401c14a1a9 https://go.googlecode.com/hg/ #

Total comments: 27

Patch Set 6 : diff -r 24401c14a1a9 https://go.googlecode.com/hg/ #

Total comments: 2

Patch Set 7 : diff -r 32c1ce44286f https://go.googlecode.com/hg/ #

Unified diffs Side-by-side diffs Delta from patch set Stats (+72 lines, -0 lines) Patch
M src/pkg/math/big/nat.go View 1 2 3 4 5 6 2 chunks +72 lines, -0 lines 0 comments Download

Messages

Total messages: 5
agl1
Hello gri@golang.org (cc: golang-dev@googlegroups.com), I'd like you to review this change to https://go.googlecode.com/hg/
10 years, 1 month ago (2012-10-16 20:34:35 UTC) #1
gri
Some suggestions. https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go File src/pkg/math/big/nat.go (right): https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1251 src/pkg/math/big/nat.go:1251: // If the exponent is large and ...
10 years, 1 month ago (2012-10-16 21:24:30 UTC) #2
agl1
https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go File src/pkg/math/big/nat.go (right): https://codereview.appspot.com/6716048/diff/7001/src/pkg/math/big/nat.go#newcode1251 src/pkg/math/big/nat.go:1251: // If the exponent is large and the base ...
10 years, 1 month ago (2012-10-16 22:22:56 UTC) #3
gri
LGTM https://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go File src/pkg/math/big/nat.go (right): https://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go#newcode1343 src/pkg/math/big/nat.go:1343: zz = zz.mul(z, z) I'd leave a comment ...
10 years, 1 month ago (2012-10-16 23:56:06 UTC) #4
agl1
10 years, 1 month ago (2012-10-17 15:19:36 UTC) #5
*** Submitted as http://code.google.com/p/go/source/detail?r=95b8a6011b40 ***

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%

R=gri
CC=golang-dev
http://codereview.appspot.com/6716048

http://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go
File src/pkg/math/big/nat.go (right):

http://codereview.appspot.com/6716048/diff/10001/src/pkg/math/big/nat.go#newc...
src/pkg/math/big/nat.go:1343: zz = zz.mul(z, z)
On 2012/10/16 23:56:06, gri wrote:
> I'd leave a comment here, something along the lines:
> 
> // Unrolled loop for significant performance gain.
> // Use go test -bench=XXX to check performance before making changes.
> 
> (fill in XXX)

Done.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld f62528b