Distributed high performance large integer arithmetic

摘要

We have evaluated a number of techniques for obtaining distributed high performance arithmetic for large integers. Two main ideas are presented: a technique for handling carry propagation in parallel additions and a technique for distributing not only the processing but also the storage of very large integers onto a number of computers. These ideas have been compared to state-of-the-art arithmetic libraries. We have carried out performance evaluations on a Linux cluster with 32 computers and an SMP with eight processors. The performance of addition was improved by a factor 13, and that the method where the storage of an integer is distributed was superior to the approaches where only processing is distributed. The multiplication performance was improved by a factor of 7.