Schönhage-Strassen algorithm with MapReduce for multiplying terabit integers
Tsz-Wo Sze · 2012
We present MapReduce-SSA, an integer multiplication algorithm using the ideas from Schönhage-Strassen algorithm (SSA) on MapReduce. SSA is one of the most commonly used large integer multiplication algorithms. MapReduce is a programming model invented for distributed data processing on large clusters. MapReduce-SSA is designed for multiplying integers in terabit scale on clusters of commodity machines. As parts of MapReduce-SSA, two algorithms, MapReduce-FFT and MapReduce-Sum, are created for computing discrete Fourier transforms and summations. These mathematical algorithms match the model of MapReduce seamlessly.