Bij op roosters gebaseerde post-kwantumcryptografie worden vaak polynomen van graad n = 256 met elkaar vermenigvuldigd. Als de naïeve methode, waarbij alle paren coëfficiënten met elkaar worden vermenigvuldigd, ongeveer n² vermenigvuldigingen nodig heeft en de methode met de getaltheoretische transformatie (NTT) ongeveer n log₂ n, welke waarde ligt dan het dichtst bij de factor waarmee de NTT het aantal vermenigvuldigingen vermindert?

Antwoord: B. Ongeveer 1/32

De naïeve methode heeft n² = 256² = 65.536 vermenigvuldigingen nodig en de methode met de NTT n log₂ n = 256 × 8 = 2048, dus 65.536 ÷ 2048 = 32, een vermindering tot ongeveer 1/32. De getaltheoretische transformatie past het idee van de snelle fouriertransformatie toe op gehele getallen modulo een priemgetal, en na de transformatie is alleen nog een vermenigvuldiging per coëfficiënt nodig. ML-KEM rekent met coëfficiënten modulo q = 3329 en is ontworpen om met de NTT te worden berekend, dus NTT-schakelingen vormen een centraal onderdeel van versnellers voor post-kwantumcryptografie. Daarnaast gebruiken ML-KEM en ML-DSA veel functies uit de SHA-3-familie (SHAKE) om matrices en willekeurige waarden te maken, dus ook versnellers daarvoor zijn effectief.