alt Hacker NewsTo make both addition and multiplication O(n), you can store numbers as their residues modulo a bunch of different primes and appeal to the Chinese Remainder Theorem. However, then size comparison becomes difficult.
Replies
im3w1l • last Sunday at 8:51 PM
I think the problem comes when you do a multiplication and you need more primes for uniqueness.
➕ show 1 reply
Residue number systems are really neat! They're sometimes used in crypto implementations, but there you're doing modular multiplication and in most cases the modular reduction then becomes costly, so it's not a free lunch. (Except in RSA and a few other cases. RSA-CRT gets you a "free" ~4x performance boost except it's more brittle to mistakes and side-channel / fault attacks.)
There's also NTT / Fourier multiplication as an option, for big integers or polynomials or modular arithmetic.