×

Modular arithmetic and its applications in info-communication technologies. (Модулярная арифметика и ее приложения в инфокоммуникационных технологиях.) (Russian) Zbl 1417.94003

Moscow: Fizmatlit (ISBN 978-5-9221-1716-6/hbk). 400 p. (2017).
Let \({m_1},...,{m_k}\) be a set of pairwise coprime integers called the moduli. By the the Chinese Remainder Theorem (CRT) every integer \(X,0 \leqslant X < M = \prod {m_i}\) has unique representation with the list of residues \(X \equiv (X\bmod {m_1},\ldots,X\bmod {m_k})\) (in the book is also used notation \(X\bmod m = |X{|_m}\)). Representation by residues allows in computers to perform addition/substraction and multiplication in parallel, since if \(X \equiv ({x_1},\ldots,{x_k}),Y \equiv ({y_1},\ldots,{y_k})\), then e.g. \(X + Y \equiv (({x_1} + {y_1})\bmod {m_1},\ldots,({x_k} + {y_k})\bmod {m_k})\), thus to increase speed of computation and use (generally) smaller numbers – both properties are very valuable in e.g. cryptography. But representation by residues makes also several functions more complicated – comparison of values, division and floating-point calculations, sign and overflow detection etc, thus in spite of some nice properties residue-based architecture has found in hardware limited application.
In 1950s in the Soviet Union computers working on this principle were produced (Perspectives on Soviet and Russian Computing: First IFIP WG 9.7 Conference, SoRuCom 2006, Petrozavodsk, Russia, July 3–7, 2006, Revised Selected Papers, Springer, Sep 6, 2011 – Computers – 274 pages) and although the SU financing for development of computers based on residue principle was cut, the theoretical development continued and this book from a collection of authors from Stavropol (the Soviet computers based on residues were also produced in Stavropol) is an example of this research.
This book is a collection of algorithms developed by authors for residue computers - proposals for hardware implementation and applications to cryptography, RSA and elliptic curve cryptosystems and digital signal processing. The book does not require high-level mathematical education, just some knowledge of number theory (modulus calculations, CRT) and elements of linear algebra. It is difficult to evaluate the practical value of the proposed algorithms, since the authors do not provide data about digital tests in real hardware. Residue number systems are more complex than the standard implementations, thus the efficiency of their implementation should be tested in hardware.
The style of the book makes it also rather difficult to follow. Even elementary assertions are not proved and are often very vague (“obviously”, ”or something similar” etc), same concepts are defined several times but using different notations, definitions may appear on some pages after they have been used, for mathematical concepts are sometimes used Russian abbreviations, sometimes English (without explanation), lower-case mathematical symbols appear some lines later in upper-case, some assertions are elementary erroneous (e.g. assertion on p. 207 “the residue class \(Z/\bmod 7 \equiv 1\) consists of integers 269341059,36,15,8,1” – the set contains also integers 15, 22,... – it is infinite), there are even problems with use of Russian language. Headings of sections 6.1–6.2 suggest, that here is presented the authors’ invention ‘neurocomputer’, but if the (full of errors) corresponding pages pp 202..209 are explanation of this discovery then already the medieval Chinese mathematician Ch’in Chiu-Shao, 19th century English mathematicians W.G. Horner, P. Ruffini and many others also knew, what is ‘neurocomputer’.
Nevertheless, for specialists in this area who can auto-correct mistakes this book may be a valuable resource – if they manage to get it, since the book has notice “Not for sale”.

MSC:

94-02 Research exposition (monographs, survey articles) pertaining to information and communication theory
94A05 Communication theory
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
94A60 Cryptography
94B40 Arithmetic codes
68M07 Mathematical problems of computer architecture
68-02 Research exposition (monographs, survey articles) pertaining to computer science
PDF BibTeX XML Cite