Large integer multiplication on hypercubes (Q1200131)

The known algorithm of \textit{A. Schönhage} and \textit{V. Strassen} for large integer multiplication [Computing 7, 281-292 (1971; Zbl 0223.68007)] is mainly based on the Fermat number transform (FNT). Now this algorithm is realized on a connection machine with parallel hypercube architecture. Using such a computer it is possible to overcome the word-length restrictions of the FNT. Thus this technique makes the FNT more attractive for applications. The results show multiplication times of 2 s for 8-Mbit integers, an improvement of about 5 times over previous work.