RustCrypto / RustCrypto/crypto-bigint
Optimize Bernstein-Yang for 32-bit targets
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 309
- Forks
- 95
- Avg merge
- 1d 14h
- Merged PRs (30d)
- 3
Description
Bernstein-Yang as described in the original paper uses 62-bit limbs and is optimized for 64-bit targets: https://eprint.iacr.org/2019/266
Section 12.3 of the paper suggests it can be better optimized for 32-bit targets:
12.3. Other CPUs. Our advantage is larger on platforms with smaller multipliers. For
example, we have written software to invert modulo 2^255 − 19 on an ARM Cortex-A7,
obtaining a median cycle count of 35277 cycles. The best previous Cortex-A7 result we
have found in the literature is 62648 cycles reported by Fujii and Aranha [34], using
Fermat’s method. Internally, our software does repeated calls tojump32divsteps2, units
of 30 iterations with the resulting transition matrix fitting inside 32-bit general-purpose
registers.
However, I wasn't able to find more information about adapting the algorithm to 32-bit targets beyond this, nor was I able to find any more information about jump32divsteps2.
I attempted to naively translate the implementation to using 30-bit limbs as suggested by the "units of 30 iterations" in #372 but was unable to get it to work.
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start with the existing Bernstein–Yang implementation and Section 12.3 of the cited paper, then compare the attempted 30-bit-limb approach from #372 with the paper’s jump32divsteps2 reference. The issue is done when a correct, optimized implementation for 32-bit targets is available.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cryptography
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100