ARIAN: A Scalable Method for Adding aRbItrAry Numbers on Modern Processors

摘要

High precision calculations that exceed the register's width on a computing system require arbitrary arithmetic. An application example where arbitrary long numbers are widely used is cryptography because longer numbers offer higher encryption security. Modern systems typically employ up to 64-bit registers, way less than what an arbitrary number requires, while conventional algorithms do not exploit hardware characteristics as well. In this paper, we propose ARIAN, a new scalable method to add arbitrary long numbers which utilizes logical operations rather than arithmetic to perform calculations. We also extended our algorithm (AR-AVX) to utilize AVX (Advanced Vector eXtensions) instructions to exploit parallelization and further increase calculation speed up. Experimental results show that the proposed methodology achieves a speed up of more than 120× on average, comparing to current implementations, while with the addition of AVX we achieve a 300× speed up on average.