METHODS OF BASIC NON-MODULAR OPERATIONS IN MODULAR ARITHMETIC USING INTERVAL POSITIONAL CHARACTERISTICS
Background. Residue Number Systems (RNS) and modular arithmetic enable independent processing of individual bits of numbers and find their application in many strategically important areas of science, such as cryptography, digital signal processing, high-precision calculations, etc. It is known that the main problem of the efficient use of RNS is the complexity of non-modular operations that require assessement of the positional values of modular numbers. The purpose of the study is a theoretical and scientific grounding of a new method of basic non-modular operations in modular arithmetic (comparison, sign determination, overflow detection), which is based on the calculation and analysis of interval positional characteristics of modular numbers. This method is characterized by its simplicity and allows to get reliable evaluation of the relative positional magnitude of a modular number asymptotically fast. Materials and methods. To solve the problem of the effective defenition of the relative positional value of a number represented in the residue number system, the Chinese Remainder Theorem has been used. The reliability of results of non-modular operations is proved by the fundamentals of Interval Analysis. Results. A new method of the definition of non-modular comparisons in residue number systems, sign determination and overflow detection based on the calculation and analysis of interval characteristics of modular numbers has been suggested. The formal conditions for the correct execution of non-modular operations using the proposed method have been identified. The analysis of the complexity of the interval characteristics calculation has been fulfilled. A probabilistic evaluation for the intersection of interval characteristics of two modular numbers, which leads to the violation of sufficient conditions for the correctness of non-modular operations, has been obtained. Conclusions. Comparison, sign determination and overflow detection operations in RNS can be reliably performed using the proposed interval positional characteristics evaluation technique in linear time for the sequential computations and logarithmic – in parallel. The proposed method does not require high hardware cost. In some cases, the interval positional characteristics do not enable to determine the result of the non-modular operation. The probability of occurrence of such cases is, where k is a count of bits to represent the fractional part of boundary interval characteristic, n is count of RNS modules.