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
Adding is super easy. We chain adders set to Each (red), Each (green) with Modulo Combiners set to Each and our modulus p.
I've split the 8 values that make up a scalar into a pair of 4 values, assigned to the 4 basic ores (iron ore, copper ore, coal, and stone). Why we will see in the next part.
I've split the 8 values that make up a scalar into a pair of 4 values, assigned to the 4 basic ores (iron ore, copper ore, coal, and stone). Why we will see in the next part.
Next, we need multiplication. Here is where the split representation comes in handy, since ML-KEM does not do a full NTT, but leaves out the last step, resulting in real and imaginary values.
To multiply to scalars, we first multiply (each red, each green) all four combinations of the inputs. The imaginary-imaginary part needs to be adjusted further, and multiplied with a constant, depending on zeta. We chose zeta = 3, so our values are coal = 3, stone = 27 (3^3), iron ore 38 (3^5 mod 41), and copper ore 14 (3^7 mod 41). It's basically like complex numbers, but with the value of i^2 changing around.
After multiplying that in, we then add it to the real-real multiplication. We also add the mixed pairs, and compute modulo 41 at the end. Since we at most multiply 3 6-bit integers (and later 12 bit for the full version), we don't have to be careful with reducing beforehand.
stpiper1@sophieschmieg Oh no, now I may *have* to start playing. 🔥🤦🏻♂️
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.