High Speed Modulo Calculation Algorithm with Radix-2ᵏ SD Number

Abstract

In RSA Cryptograms, many modulo calculations are used, but modulo calculation is based on many subtractions and it takes long a time to calculate it. In this article, we explain a new modulo calculation algorithm using a table. And we prove that upper 3 digits of Radix-2ᵏ SD numbers are enough to specify the answer. In the first section, we present some useful theorems for operations of Radix-2ᵏ SD Number. In the second section, we define Upper 3 Digits of Radix-2ᵏ SD number and prove that property. In the third section, we prove some property connected with the minimum digits of Radix-2ᵏ SD number. In the fourth section, we identify the range of modulo arithmetic result and prove that the Upper 3 Digits indicate two possible answers. And in the last section, we define a function to select true answer from the results of Upper 3 Digits.