Arithmetic with Very Large Integers Using Parallel Processing

摘要

We present a practical and efficient procedure for performing operations on very large integers by carrying out operations on components of r tuples representing these integers. Each integer can be uniquely represented by an r tuple consisting of its remainders upon division by m_1,m_2,m_3...m_n where each m_i is an integer greater than 2, and where gcd(m_i, m_j)=1 for i ≠ j. After computing the value of each component in the result, we can recover its value by multiplying its components by the corresponding basis vectors. These representations are unique so long as m_1,m_2,m_3...m_n is greater than the results of the arithmetic operation we wish to compute. There are two major advantages to this method: a) Time: The component computation can be done using parallel processing, thereby greatly reducing the execution time, and b) Size: Arithmetic can be performed on integers larger than those that can be ordinarily handled by a computer.