Score:-2

Straightforward modular arithmetic for power-of-two moduli

in flag

Why if $q$ is a power-of-two integer, then doing arithmetic modulo $q$ (addition and multiplication) is very efficient and straightforward?

forest avatar
vn flag
I’m voting to close this question because it's about simple mathematical operation's efficiency in computers and is not specific to cryptography.
Mark avatar
ng flag
its worth mentioning this can be cryptographically relevant --- one (significant) difference between the NIST PQC finalists Saber and Kyber are that Saber has a power-of-two moduli $2^{13}$ (and fast modular reduction), while Kyber uses an NTT friendly moduli, which admit more efficient (but more complex) multiplication algorithms. This has led to cryptographic research comparing the two, and even figuring out how to embed power-of-two multiplication into a NTT friendly ring.
Score:3
my flag

Why if $q$ is a power-of-two integer, then doing arithmetic modulo $q$ (addition and multiplication) is very efficient and straightforward?

Because processors already have efficient addition and multiplication operations over moderately large ranges (32 or 64 bits), and the modulo operation is so efficient (just discard the bits above $q$, a simple and operation with a constant). And, because for many operations (including addition and multiplication) the higher-order bits don't affect the lower-order bits, sometimes we don't even have to do that - we can just ignore them...

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.