Claire Xen  🏳️‍⚧️ 🏳️‍🌈 🧙🏻‍♀️ BLM  🏴 🚩

Can you name applications for CLMUL that are not CRC, GCM, hashing/rng, or Erasure Code? I'm trying to create a list of possible applications. #RISCV #Bitmanip #Followerpower cc @rygorous @geofflangdale @alt_kia @lemire @rrika9

CLMUL a number with itself inserts zeroes between each input bit. Useful if you want to construct morton-codes. They are useful to index into large 2D arrays because they are very cache friendly.

I have another one. Afaik you can calculate the Number Theoretic Transform in GF2 using clmul. This gives you most of the goodies a FFT will, but without ever running into roundig Errors. You can use this for example to do fast bignum multiplications.

Do you have a reference for this? (Googled a bit but didn't find something that looks like that, maybe I just used the wrong search terms? I guess the fast bignum part refers to the Schoenhage-Strassen algorithm. But I can't seem to find anything specifically re NTT using CLMUL.)

Here is a paper using NTT over a Galois Field doing image filtering: https://www.computer.org/csdl/trans/tc/1977/09/01674935.pdf … They don't use GF(2) which clmul does natively, but GF(45 X 229 + 1) instead. I'm pretty sure that clmul can be used to compute these, but it's not exactly my area of expertise :-)

Ah, no. dug a bit deeper. You can't use clmul for that. It's plain modulo-prime arithmetic that they are using. :-/