Sophie SchmiegI've discovered Aquilo in Factorio, and looking at how the tech tree involves quantum computing, it is time to prepare.
It's time to implement ML-KEM.
Let's start with a simplified version, using n = 8, p = 41, and zeta = 3.
The first thing we need are addition and multiplication in the NTT domain
Factorio is very helpful here, since all values are vectors of 64 bit integers.
ML-KEM needs vectors of 12 bit integers, so 64 bit is plenty
Richard Barrell@sophieschmieg ah aren't Factorio signal values 32 bit signed ints or did they upgrade in 2.0?
@0x2ba22e11 oh, if they're 32 bits, I'll need to adjust the multiplier unit for the full version, but it's just adding another modulo before the constants are multiplied in
@sophieschmieg I checked this last night and they are definitely signed 32 bits. 1<<31 is -2.1bn and subtracting 1 from that gives me +2.1bn
@0x2ba22e11 thanks, good to know. Not that tragic for ML-KEM, but kind of sad for ML-DSA. (Although my plan was to only maybe implement ML-KEM anyways, it's a certain kind of fun that you only need some amount of)
@0x2ba22e11 it does make implementing SHAKE a bit harder (it likes being implemented as a 5x5x64 bit array), unfortunately, but I'm not sure if I'll even attempt that in the first place.