RustCrypto / RustCrypto/elliptic-curves

256 bit Field Operation: 64 bit * 4 vs 52 bit * 5

Open
#960 4 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
874
Forks
299
Avg merge
1d 4h
Merged PRs (30d)
12

Description

Thank you @tarcieri for the conversation (tag: @fjarri )

I would like to know the pros and cons of field arithmetic by 64 bit * 4 and 52 bit * 5.

In bitcoin-core and rust crypto implementations, these use 52 bit 5 limbs for 256 bit field operation.
We can also perform 256 bit field operation by 64 bit 4 limbs.

The main issue is how we deal with the mod operation.
In 52 bit * 5, it manages the number of arithmetic by magnitude and performs naive modulus reduction.
In 64 bit * 4, it performs reduction for each arithmetic and causes sub operation overhead for addition, and montogomery reduction for multiplication but doesn't perform naive modulus reduction instead.

In my opinion, for specific operation such as sign and encryption, number of arithmetic is less so we should do it with 64 bit * 4.
for arbitrary operation, number of arithmetic is unknown so we should do it with 52 bit * 5.

I would like to know if you have any idea about this comparison.
Thank you.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Compare the 64-bit-by-4 and 52-bit-by-5 field-arithmetic approaches described in the issue, including their modulus-reduction and operation-count tradeoffs. Review the repository's existing field arithmetic entry points and the referenced bitcoin-core implementation, then document which representation best fits the project's intended workloads; the issue does not name a specific file or test.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
cryptography
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
20/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.