shakes76 / finite-transform-library Goto Github PK

From your (rather well-written) article "Fast Digital Convolutions using Bit-Shifts”, I understand that I can use a Rader prime as modulus in a Number Theoretic Transform, and apply a number theoretic transform with a power of 2 (which allows for convenient bitshifting), as when using a Fermat number as modulus.

You cite [R. Agarwal and C. Burrus, 1974] and [Leibowitz, 1976] for a computational implementation. They use a diminished-1 implementation, but their implementation seems only geared toward moduli that are Fermat numbers.

The Rader prime is not a Fermat number, but you seem to imply that an implementation for using Rader prime moduli is analogous to that of Fermat numbers. As this logic is not evident to me, I was wondering if you could help me by shedding some light on how addition, bitshift and multiplication is performed when using Rader prime moduli in the number theoretic transform.

For instance, how would these operations be executed when the modulus is selected as the Rader prime 641 (which is a factor of F5)?

The readme states " Lesser GNU Public License v3" but most other license statements do not say "Lesser" or "LGPL".