Efficient Number Comparison in the Residue Number System based on Positional Characteristics
An important operation for data processing is a number comparison. In Residue Number System (RNS), it consists of two steps: the computation of the positional characteristic of the number in RNS representation and comparison of its positional characteristics in the positional number system. In this...
| Main Authors: | , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ivannikov Institute for System Programming of the Russian Academy of Sciences
2019-06-01
|
| Series: | Труды Института системного программирования РАН |
| Subjects: | |
| Online Access: | https://ispranproceedings.elpub.ru/jour/article/view/1149 |
| _version_ | 1818749746621186048 |
|---|---|
| author | Mikhail Grigorievitch Babenko Andrei Tchernykh Nikolay Ivanovitch Chervyakov Viktor Andreevich Kuchukov Vanessa Miranda-Lopes Raúl Rivera Rodriguez Zhihui Du |
| author_facet | Mikhail Grigorievitch Babenko Andrei Tchernykh Nikolay Ivanovitch Chervyakov Viktor Andreevich Kuchukov Vanessa Miranda-Lopes Raúl Rivera Rodriguez Zhihui Du |
| author_sort | Mikhail Grigorievitch Babenko |
| collection | DOAJ |
| description | An important operation for data processing is a number comparison. In Residue Number System (RNS), it consists of two steps: the computation of the positional characteristic of the number in RNS representation and comparison of its positional characteristics in the positional number system. In this paper, we propose a new efficient method to compute the positional characteristic based on the approximate method. The approximate method as a tool to compare numbers does not require resource-consuming non-modular operations that are replaced by fast bit right shift operations and taking the least significant bits. We prove that in case when the dynamic range of RNS is an odd number, the size of the operands is reduced by the size of the module. If one of the RNS moduli is a power of two, then the size of the operands is less than the dynamic range. It makes our method efficient for hardware implementation of cryptographic primitives and digital signal processing. |
| first_indexed | 2024-12-18T04:08:41Z |
| format | Article |
| id | doaj.art-a0cffe16b41c413a8b68efc8805e655a |
| institution | Directory Open Access Journal |
| issn | 2079-8156 2220-6426 |
| language | English |
| last_indexed | 2024-12-18T04:08:41Z |
| publishDate | 2019-06-01 |
| publisher | Ivannikov Institute for System Programming of the Russian Academy of Sciences |
| record_format | Article |
| series | Труды Института системного программирования РАН |
| spelling | doaj.art-a0cffe16b41c413a8b68efc8805e655a2022-12-21T21:21:31ZengIvannikov Institute for System Programming of the Russian Academy of SciencesТруды Института системного программирования РАН2079-81562220-64262019-06-0131218720110.15514/ISPRAS-2019-31(2)-131147Efficient Number Comparison in the Residue Number System based on Positional CharacteristicsMikhail Grigorievitch Babenko0Andrei Tchernykh1Nikolay Ivanovitch Chervyakov2Viktor Andreevich Kuchukov3Vanessa Miranda-Lopes4Raúl Rivera Rodriguez5Zhihui Du6Кафедра прикладной математики и математического моделирования Северо-Кавказского федерального университетаЦентр научных исследований и высшего образования Энсенада, Мексика; Институт системного программирования РАН им. В.П. Иванникова, Россия; Южно-Уральский государственный университет, РоссияСеверо-Кавказский федеральный университетСеверо-Кавказский федеральный университетЦентр научных исследований и высшего образования Энсенада, МексикаЦентр научных исследований и высшего образования Энсенада, МексикаУниверситет Цинхуа, КНРAn important operation for data processing is a number comparison. In Residue Number System (RNS), it consists of two steps: the computation of the positional characteristic of the number in RNS representation and comparison of its positional characteristics in the positional number system. In this paper, we propose a new efficient method to compute the positional characteristic based on the approximate method. The approximate method as a tool to compare numbers does not require resource-consuming non-modular operations that are replaced by fast bit right shift operations and taking the least significant bits. We prove that in case when the dynamic range of RNS is an odd number, the size of the operands is reduced by the size of the module. If one of the RNS moduli is a power of two, then the size of the operands is less than the dynamic range. It makes our method efficient for hardware implementation of cryptographic primitives and digital signal processing.https://ispranproceedings.elpub.ru/jour/article/view/1149система остаточных классовнемодульные операциисравнение чиселприближенный метод |
| spellingShingle | Mikhail Grigorievitch Babenko Andrei Tchernykh Nikolay Ivanovitch Chervyakov Viktor Andreevich Kuchukov Vanessa Miranda-Lopes Raúl Rivera Rodriguez Zhihui Du Efficient Number Comparison in the Residue Number System based on Positional Characteristics Труды Института системного программирования РАН система остаточных классов немодульные операции сравнение чисел приближенный метод |
| title | Efficient Number Comparison in the Residue Number System based on Positional Characteristics |
| title_full | Efficient Number Comparison in the Residue Number System based on Positional Characteristics |
| title_fullStr | Efficient Number Comparison in the Residue Number System based on Positional Characteristics |
| title_full_unstemmed | Efficient Number Comparison in the Residue Number System based on Positional Characteristics |
| title_short | Efficient Number Comparison in the Residue Number System based on Positional Characteristics |
| title_sort | efficient number comparison in the residue number system based on positional characteristics |
| topic | система остаточных классов немодульные операции сравнение чисел приближенный метод |
| url | https://ispranproceedings.elpub.ru/jour/article/view/1149 |
| work_keys_str_mv | AT mikhailgrigorievitchbabenko efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT andreitchernykh efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT nikolayivanovitchchervyakov efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT viktorandreevichkuchukov efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT vanessamirandalopes efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT raulriverarodriguez efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics AT zhihuidu efficientnumbercomparisonintheresiduenumbersystembasedonpositionalcharacteristics |