A simplified binary arithmetic for the Fermat number transform

Abstract

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 F <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</inf> = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">b</sup> + 1, b = 2 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</sup> . 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 F <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">t</inf> required in the computation of FNT convolution is discussed.