A simplified binary arithmetic for the Fermat number transform
Lawrence M. Leibowitz · IEEE Transactions on Acoustics Speech and Signal Processing · 1976
A binary arithmetic that permits the exact computation of the Fermat number transform (FNT) is described. This technique involves arithmetic in a binary code corresponding to the simplest one of a set of code translations from the normal binary representation of each integer in the ring of integers modulo a Fermat number Ft= 2b+ 1, b = 2t. The resulting FNT binary arithmetic operations are of the complexity of 1's complement arithmetic as in the case of a previously proposed technique which corresponds to another one of the set of code translations. The general multiplication of two integers modulo Ftrequired in the computation of FNT convolution is discussed.