Lazy Reductions?

[jon-chuang]

I was wondering if lazy reductions are possible to speed up the EC operations.

This is as far as I can tell relevant for affine, Jacobian and projective formulas, where intermediate terms are composed of summands that are multiples of two or more field elements.

I'm pretty sure pairing formulas can benefit as well.

In Montgomery reduction mod N, we only require aR.bR to be in the range [0, RN-1], where we require R > N, rather than in the range [0, (R-1)^2].

We can probably use some appropriate compile time checks to make sure that no errors are introduced when utilising lazy reductions in writing formulas.

[Pratyush]

They should definitely help speed up operations noticeably, though we'll have to ensure that we're doing it properly across different moduli.

(It'll also increase the size of the prime field struct if we have to store an additional number_of_ops: u8 field. I think waiting for something like const generics to solve this might be worthwhile; in the meanwhile, we could experiment with new APIs on nightly)

[jon-chuang]

Hmm, I was wondering whether proc macros could be used to do the compile time checks without introducing the storage and runtime overhead.

What would be cool is if you could use proc macros to insert modular reductions where necessary, while the base multiplications don't do the reduction.

The current modular multiplication used in the assembly iirc does the modular reduction interspersed with the multiplication, so that may have to be reworked too.

Over all, it would require a complete redesign of the arithmetic system.

But its an interesting problem nonetheless, one is essentially creating a DSL system rather than relying on atomic primitives, that are only optimized at the lowest level of semantic understanding by the compiler. So we introduce more semantics that allows more aggressive optimisation.

[Pratyush]

@jon-chuang do you think this is plausible without a complete rewrite? I think if we wanted to pursue this it would make sense to do for specific curves, instead of generically (as the latter might be too difficult). Also guide to pairing-based-cryptography indicates that achieving good performance with lazy reductions is difficult for pairing-friendly curves.