Open AccessDetermining the rank of a number in the residue number system
Author(s) -
Mikhail Babenko,
Nikolay Nikolaevich Kucherov,
Andrei Tchernykh,
Viktor Kuchukov,
Elena Golimblevskaia,
Ekaterina A. Kuchukova,
Irina Vashchenko
Publication year - 2021
Language(s) - English
Resource type - Conference proceedings
DOI - 10.47350/iccs-de.2021.01
Subject(s) - rank (graph theory) , mathematics , residue number system , residue (chemistry) , value (mathematics) , combinatorics , discrete mathematics , algorithm , statistics , chemistry , biochemistry
In this article, the formulation and proof of the theorem on the difference in the ranks of the numbers represented in the Residue Number System is carried out. A method is proposed that allows to reduce the amount of necessary calculations and increases the speed of calculating the rank of a number relative to the method for calculating the rank of a number based on the approximate method. To find the rank of a number in the method for calculating the rank of a number based on the approximate method, it is necessary to calculate n operations with numbers exceeding the modulus value; in the proposed method, it is necessary to calculate n·(n−1)/2 operations not exceeding the value of the module.