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

[ashWhiteHat]

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.

[fjarri]

The benefit of 5x52 is lazy reduction, so you can do several operations without reducing and then reduce the whole thing. It is mainly helpful in point addition, if I remember correctly. It would be an interesting experiment to replace it with Montgomery multiplication (everything you need is already in crypto-bigint) and see how the performance changes.

Edit: Note that the operations in 5x52 are also manually optimized for the specific form of the modulus (which has the top 223 bits set). I am not sure if the compiler will be able to optimize something automatically in the Montgomery multiplication, or how much it is possible to optimize at all. Just something to keep in mind when doing the comparison.

Edit 2: I just remembered there are actually methods in crypto-bigint (with prefix _special) which are optimized for moduli of the type k256 has.

[ashWhiteHat]

p256 field is implemented with each time modular reduction
we can compare to benchmark

[ashWhiteHat]

methods in crypto-bigint (with prefix _special)

That's interesting.
Could you put the link?

[ashWhiteHat]

I found.
https://github.com/RustCrypto/crypto-bigint/blob/master/src/uint/add_mod.rs#L28