Large integer multiplication on hypercubes
type: Item
instance of: scholarly article
title: Large integer multiplication on hypercubes
zbMATH Open document ID: 0757.65152
DOI: 10.1016/0743-7315(92)90080-7
author: Barry S. Fagin
published in: Journal of Parallel and Distributed Computing
publication date: 1993-01-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 65T50
Mathematics Subject Classification ID: 65Y10
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 96778
zbMATH Keywords: Schönhage-Strassen algorithm
zbMATH Keywords: large integer multiplication
zbMATH Keywords: Fermat number transform
zbMATH Keywords: hypercube architecture
reviewed by: Manfred Tasche
MaRDI profile type: Publication
full work available at URL: 0743-7315(92)90080-7
OpenAlex ID: W2092690651
description: scientific article; zbMATH DE number 96778