Optimize modular multiplication

[PopcornPaws]

Description

Since there's no modular multiplication implemented in the crypto-bigint library yet , we initially used mul_wide when multiplying two Uint256 types to get an Uint512. This number was then modulo divided by the prime modulus/order to obtain the result of the modular multiplication. However, this proved to be extremely slow.

After experimenting a bit, we found that converting the Uint256 type into a bigint type and performing the modular multiplication on that value proved to be much faster, regardless of the type conversions. However, since bigint uses Vecs to represent big integer bytes, allocation and deallocation of vectors take up most time spent in a modular multiplication.

[PopcornPaws]

Issue tracker
PR with mul_mod

[haslersn]

Note that RustCrypto/crypto-bigint#108 can only be used if your modulus has 0xffffffffffffffff in all limbs except for the least significant limb. I don't know if this is the case here, since I'm not familiar with this project.

[PopcornPaws]

Thanks for the heads up @haslersn , I didn't thoroughly read your premise. Unfortunately this is not the case for us.