Skip to content

perf: use NAF decomposition in mulWindow#787

Merged
yelhousni merged 5 commits intomasterfrom
perf/mulWindowed
Jan 26, 2026
Merged

perf: use NAF decomposition in mulWindow#787
yelhousni merged 5 commits intomasterfrom
perf/mulWindowed

Conversation

@yelhousni
Copy link
Copy Markdown
Collaborator

@yelhousni yelhousni commented Jan 6, 2026

Description

Use ecc.NafDecomposition in utils.go in mulWindowed.

Fixes #132

Type of change

  • New feature (non-breaking change which adds functionality)

How has this been tested?

Same tests pass.

How has this been benchmarked?

e.g. BLS12-377:

cpu: AMD EPYC 9R14
BenchmarkG1AffineScalarMultiplication/method=GLV-wNAF/w=5-32     129970        115066        -11.47%
BenchmarkG2AffineScalarMultiplication/method=GLV-wNAF/w=5-32     405302        333270        -17.77%

Checklist:

  • I have performed a self-review of my code
  • I have commented my code, particularly in hard-to-understand areas
  • I have made corresponding changes to the documentation
  • I have added tests that prove my fix is effective or that my feature works
  • I did not modify files generated from templates
  • golangci-lint does not output errors locally
  • New and existing unit tests pass locally with my changes
  • Any dependent changes have been merged and published in downstream modules

Note

Implements NAF-based scalar multiplication across all curves and updates codegen.

  • Replaces old 2-bit windowed double-and-add with NAF-based mulWindowed, adding mulWindowedMixed (affine input) and an affine wrapper; handles zero/negative scalars and reduces scalars mod fr where needed
  • Adjusts ScalarMultiplication/ScalarMultiplicationBase to use new paths and return early, using affine generators (*GenAff) in non-GLV cases
  • Minor flow tweaks (e.g., moving FromAffine only when needed) and identical changes applied to G1/G2 for bls12-377, bls12-381, bls24-315/317, bn254, bw6-633/761, grumpkin, secp256k1
  • Updates internal/generator/ecc/template/point.go.tmpl to generate the new logic

Written by Cursor Bugbot for commit 833801b. This will update automatically on new commits. Configure here.

@yelhousni yelhousni added this to the v0.19.N milestone Jan 6, 2026
@yelhousni yelhousni self-assigned this Jan 6, 2026
@gbotrel
Copy link
Copy Markdown
Collaborator

gbotrel commented Jan 6, 2026

nice would be nice if we could have a version with no big int for the naf decomposition to avoid allocs (i.e. if scalar < modulus, use the non-big-int version) ?

@yelhousni
Copy link
Copy Markdown
Collaborator Author

nice would be nice if we could have a version with no big int for the naf decomposition to avoid allocs (i.e. if scalar < modulus, use the non-big-int version) ?

The scalar decomposition can output negative integers which would be mod-reduced and the bit-length would increase beyond the |mod|/2 bound.

YaoJGalteland
YaoJGalteland previously approved these changes Jan 20, 2026
@yelhousni yelhousni merged commit bb096ef into master Jan 26, 2026
14 checks passed
@yelhousni yelhousni deleted the perf/mulWindowed branch January 26, 2026 14:51
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2-NAF in G1/G2 scalar multiplication

3 participants