Add basic NTTs

[hanno-becker]

Long-term, we want high-performance NTTs with an internal interface similar if not equal to that of https://github.com/neon-ntt/neon-ntt. To kick off the ASM integration, however, let's first integrate deinterleaved assembly versions of the NTT and inverse NTT only, and add the necessary compiler time options to switch between C and ASM build.

Acceptance criteria:

• [ ] Deinterleaved forward and inverse NTTs for MLKEM are added to this repository as standalone ASM files in a separate ASM directory.
• [ ] A compile time option is added that allows to switch between C-only and ASM version of this repository.
• [ ] Said compile-time option controls all existing assembly plus the newly added NTT and invNTT.
• [ ] CI is adjusted to build, test and benchmark the repository with and without ASM.

Finding a long-term internal interface is explicitly out of scope. If possible, stick with the existing internal interface to the NTTs. If it's not possible, let's discuss.

[vincentvbh]

Hi, @hanno-becker.

I think more things are worth noting. As far as I can tell, the memory access patterns of the plain C (in ML-KEM reference) and the ASM versions (opt-ed implementation in literature) are quite different. It might be better to determine which memory access pattern should be included in the beginning. The differences in memory access patterns imply the differences in tables of twiddle factors.

Thanks, Vincent

[mkannwischer]

Hi @vincentvbh, why would the twiddle factors matter? It's not like we are going to link multiple NTT implementations, so we may as well have separate tables for each implementation.

Using asymmetric multiplication (i.e., pre-computing part of the basemul in case a polynomial is multiplied by multiple others) or not is a much harder question as it requires changing the API. But we have to start somewhere...

[vincentvbh]

How do you define basic?

[vincentvbh]

You can change the table during compile time, but what does basic stand for? How do you generate the twiddle factors? That's not basic, and people are going to have very hard time to understand how tables are generated.

[vincentvbh]

You can go ahead without pointing out the differences(I didn't say you should stop), but then that is fairly unfriendly for auditing.