HomePhabricator

[SECP256K1] Optimization: track f,g limb count and pass to new variable-time…

Description

[SECP256K1] Optimization: track f,g limb count and pass to new variable-time update_fg_var

Summary:

The magnitude of the f and g variables generally goes down as the
algorithm progresses. Make use of this by keeping tracking how many
limbs are used, and when the number becomes small enough, make use of
this to reduce the complexity of arithmetic on them.

Partial backport of secp256k1#831:
https://github.com/bitcoin-core/secp256k1/pull/831/commits/ebc1af700f9ec6e96586152b7090a2a6494308c3#diff-91cfb587705679268ee32d45895a62884faf262add85ba385cf55f74fcd51471R32-R575

Depends on D9410.

Test Plan:

ninja check-secp256k1

Reviewers: #bitcoin_abc, majcosta

Reviewed By: #bitcoin_abc, majcosta

Differential Revision: https://reviews.bitcoinabc.org/D9411

Details

Provenance
Peter Dettman <peter.dettman@gmail.com>Authored on Dec 16 2020, 02:17
FabienCommitted on Apr 14 2021, 09:19
FabienPushed on Apr 14 2021, 09:19
Reviewer
Restricted Project
Differential Revision
D9411: [SECP256K1] Optimization: track f,g limb count and pass to new variable-time update_fg_var
Parents
rABCfcf9750a5685: [SECP256K1] Optimization: use formulas instead of lookup tables for cancelling…
Branches
Unknown
Tags
Unknown