Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Optimize ScalarBaseMult #2

Closed
davecgh opened this issue Dec 21, 2013 · 0 comments · Fixed by #7
Closed

Optimize ScalarBaseMult #2

davecgh opened this issue Dec 21, 2013 · 0 comments · Fixed by #7
Labels
optimization

Comments

@davecgh
Copy link
Member

davecgh commented Dec 21, 2013

ScalarBaseMult can be significantly accelerated by making use of the fact it is multiplying by a fixed point that is known at compile time. See section 3.3.2 of Guide to Elliptic Curve Cryptography - Hankerson, Menezes, Vanstone for details.

Currently ScalarBaseMult simply calls ScalarMult which can make no such assumptions.
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
5ce3464 
Code uses the binomial expansion strategy which eliminates doublings.
All the basepoint doublings are computed beforehand to assist in the base multiplication.
Main function is computeDoublingPoints which computes all the doublings of the generator point G up to the size of the curve's bit size (for secp256k1, that's 256).

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about half what it was before.

Closes btcsuite#2
@jimmysong jimmysong mentioned this issue Sep 24, 2014
Merged
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
cc70d54 
Code uses the binomial expansion strategy which eliminates doublings.
All the basepoint doublings are computed beforehand to assist in the base multiplication.
Main function is computeDoublingPoints which computes all the doublings of the generator point G up to the size of the curve's bit size (for secp256k1, that's 256).

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about half what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
4921df9 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
710c0cf 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
3233cc6 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
addc281 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
b91d339 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
a722cb0 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 24, 2014
@jimmysong
Optimize ScalarBaseMult
67295d1 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
Main function is computeBytePoints which computes all the 256 possible combinations in that 8-bit window. This is used then to look up the point values so it minimizes the ScalarBaseMult operation.

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 25, 2014
@jimmysong
Optimize ScalarBaseMult
13f3439 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
The precomputed data is in secp256k1.go and the generator for that file is in gensecp256k1.go

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 25, 2014
@jimmysong
Optimize ScalarBaseMult
c2cea1e 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
The precomputed data is in secp256k1.go and the generator for that file is in gensecp256k1.go

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
jimmysong added a commit to jimmysong/btcec that referenced this issue Sep 25, 2014
@jimmysong
Optimize ScalarBaseMult
d694428 
Code uses a windowing/precomputing strategy to minimize ECC math.
Every 8-bit window of the 256 bits that compose a possible scalar multiple has a complete map that's pre-computed.
The precomputed data is in secp256k1.go and the generator for that file is in gensecp256k1.go

Also fixed a spelling error in a benchmark test.

Results so far seem to indicate the time taken is about 35% of what it was before.

Closes btcsuite#2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
optimization
Projects
None yet
Milestone
No milestone
Development

Successfully merging a pull request may close this issue.

Optimize ScalarBaseMult jimmysong/btcec
1 participant
@davecgh