k256: SIMD optimizations for field element "pair" operations

[tarcieri]

I was noticing that GLV decompositions operate on pairs of field elements and frequently performs the same operations on both field elements.

If we had a type like:

struct Pair<F: Field>(F, F)

...it could provide various arithmetic ops, even core::ops where applicable, that operate over both field elements in parallel in safe Rust.

You'd use it concretely as Pair(Scalar, Scalar) or Pair(FieldElement, FieldElement), and the SIMD arithmetic impls would likely be specific to one or the other, but they could otherwise provide a common API for operations that could potentially be performed in parallel on AVX-512, NEON, or SVE.

The main place I think this could be really interesting is in lincomb_vartime_glv_wnaf which calls into WnafBase::multiscalar_mul with pairs of WnafBase and WnafScalar, unfortunately I just moved k256 to using the wnaf crate and want to stabilize that ASAP which would preclude doing a more custom w-NAF implementation specifically for k256 like we have for scalar multiplication, though we could always stop using the wnaf crate and switch back to a vendored implementation (though k256 is currently the only consumer of the wnaf crate).

Alternatively we could do something like:

type FieldElementPair = (FieldElement, FieldElement);
type ScalarPair = (Scalar, Scalar);

...though I think that would preclude writing our own trait impls on the type aliases?

[Pranavjeet-Naidu]

I can make a pr to stabilise wnaf:

• delete the vendor implementation
• add wnaf unit tests
• add k256 integrations tests
• some release cleanup

once this is done, I want to profile mul_vartime, lincomb_vartime, mul_by_generator_and_mul_add_vartime. I'm curious to see if scalar decomposition is the bottleneck, worst case it is and then we can just do SIMD k256.

[tarcieri]

I already replaced the vendored implementation of wNAF in k256 with the wnaf crate, which I noted in the description as I want to stabilize the wnaf crate ASAP.

Things are basically wrapped up at this point and I'm effectively ready to do releases. This is just leaving a note for the future (and the more I thought about it, something like Pair seems generically useful if there were a way for fields to plug in SIMD implementations).

Additional tests for k256. Unit testing wnaf seems hard as it's a fully generic implementation, and the first thing that would be needed there is coming up with a testing strategy involving some sort of mock field element, which is something I think needs care in its design.