Numerous publications in recent years indicate that the prospects for creating high-speed computer systems (CS) based on the use of a modular number system (MNS) open up wide opportunities for using CSs with a high degree of parallelization of the processing of integer data. The application of the main properties of MNS and the possibility of using the tabular principle of data processing significantly increases the speed of performing integer arithmetic operations in comparison with the traditional binary positional number system. Research in this area shows the effectiveness of using MNS to increase the speed of execution besides to the arithmetic operations of addition, subtraction and multiplication of integers and the operation of exponentiating of the integers. However, until now there are no effective methods for exponentiating numbers in the MNS in all numeric domain (positive and negative). Therefore, this article developed a system of mathematical ratios that describe the researched process, based on which a method for for exponentiating numbers is developed, which unlike the known ones, can be implemented in the negative numeric domain. On the basis of the obtained method, algorithms for exponentiating numbers in the MNS were obtained, according to which devices for their implementation were synthesized. Arithmetic operation, computer system, system of mathematical ratios, exponentiating numbers, modular number system, modular structure, positional number system, tabular multiplication code.
2023 Copyright for this paper by its authors. • Diffie-Hellman algorithm: the operation of raising integers to a power is used to create a shared secret key between two participants. Participants choose a random number and the raising to a power of this number is performed using the public key of another participant, after which the resulting number is transmitted to another participant. Then other participant also raises the resulting number to the power of its private key to get the shared secret key. • ElGamal algorithm: operation of raising to a power used to encrypt and decrypt messages. When encryption, the sender randomly chooses a number and raises the recipient's public key to the power of that number, and also raises the plaintext of the message to the power of the sender's private key. The results of the operations are multiplied to get the ciphertext. When decrypting, the recipient raises the first part of the ciphertext to the power of their private key, then uses that number to divide the second part of the ciphertext to get the original plaintext. • Hash functions: Hash functions are widely used in computer science for data protection and integrity checking. One of the more popular hash functions, SHA-256, uses modulo exponentiation to compute a hash value. • The operation of exponentiation modulo is also widely used in banking. For example, SSL uses
RSA to encrypt data between a browser and a server.
• In addition, the operation of exponentiating integers modulocan be used in data networks to speed
up calculations and reduce the amount of transmitted information.
• Pseudo-random number generation: Pseudo-random number generators often use exponentiation
modulo to generate a sequence of random numbers. One of the most popular algorithms for
generating pseudo-random numbers is the Mersenne algorithm, which uses the operation of
exponentiation modulo [
In general, the operation of exponentiating integers modulo is one of the key elements of many
cryptographic algorithms and has many practical applications in computer science and other fields. At
the moment, many modern programming languages do not have tools (operators) that can implement
the operation of exponentiating numbers, it is especially difficult to implement this operation for
negative numbers [
So, research is aimed at developing a method for exponentiating numbers modulo MNS are relevant and important. However, practical methods cannot be used to perform the exponentiating operation in the negative numeric domain [8]. The article gives a method for performing this operation in various numeric domains.
By the type of the original number presented in the MNS CMNS = (c1 || c2 || ... || ck −1 || ck || ck +1 || ... || cl ), where || – mathematical sign of the concatenation operation: gluing operation, joining operation; it is difficult to attribute the number to any of the numeric domains. Consider the options of finding numbers in the MNS in the required numeric domains.
The first option. The original number represented in the MNS CMNS has an additional two (or one) sign bits +СMNS and −CMNS , where:
1, if CMNS 0, +CMNS = 0, if CMNS 0;
0, if CMNS 0, −CMNS = 1, if CMNS 0.
In this case, the original number in the MNS will be represented as
CMNS = [ +CMNS || −CMNS || (c1 || c2 || ... || ck −1 || ck || ck +1 || ... || cl )]. For this option, it is technically difficult
to determine the sign of the result of the operation [
The second option. When performing the operation of exponentiating numbers by an arbitrary
modulo MNS in all numeric domain, it is supposed to convert the number CMNS in a modular
structure (MS) CM→NS [
Research conducted in recent decades in the field of development of an effective number system at the level of the arithmetic-logical device of the CS by a number of authors (Valah M., Svoboda A., Sabo N., Akushsky I. Ya., Yudytskyi D. I., Nikolaychuk Y. M., Dolgov O. I., Torgashov V. A ., Amerbaev V. M., etc.) proved that the application of the MNS as a CS number system showed that the use of the MNS as a CS number system to perform basic arithmetic operations (addition, subtraction and multiplication between integers and real numbers) significantly increases the speed of implementation of the above operations. Research in the field of the application of the non-positional number system (NPNS), to which the MNS belongs, shows that its practical use in the CS allows to significantly increase the productivity of the realization of arithmetic operations. It should be noted that there is a class of problems and algorithms where in addition to performing an integer arithmetic operations (addition, subtraction, multiplication), there is a need to implement the operation of exponentiating numbers in all numeric domain. This problem is discussed in the works of scientists Dr. Dimitrios Schinianakis and Thanos Stouraitis, who explored MNS in cryptography. In particular, in work [9] providing a detailed explanation of cryptographic algorithms based on the MNS, including RSA, ElGamal, and elliptic curve cryptography.
They discuss the problem and limitation of using the MNS in cryptography, such as the difficulty of handling negative numbers. Various methods have been explored to solve this problem and ensure the reliability of cryptographic systems based on the system of residual classes.
Thus, the unsolvedness of the above-listed problem, connected primarily with the operation of exponentiating numbers in the negative numeric domain in MNS, determined the purpose of the article.
The principle of realization of the system of mathematical ratios is developed using the main internals of the NPNS that define the non-positional code data structure of the MNS which ensures high productivity (speed) and reliability of arithmetic operations for the implementation of computational algorithms in the CS, consisting of a set of arithmetic (modular) operations [10]. A distinctive feature of this article is that the proposed system of mathematical ratios of the process of exponentiating numbers in all numeric domain will significantly expand the scope of MNS and increase the speed of this operation in CS, and the method are reduced to algorithms, on the basis of which classes of patent-eligible devices for which Ukrainian patents have been obtained have been developed [11, 12]. 3. Realization of computing exponentiation of numbers in the MNS in all numeric domain
A system of mathematical ratios the process of exponentiating numbers was developed based on an analytical ratio (C MrNS )→ = f (CM→NS ) which defines the relation of the result C MrNS number exponentiating operations CMNS in the MNS (to the degree of r) presented in the MS, from the number
Let's define SMR (C MrNS )→ = f (CM→NS ) for values r = 2 and p1 = 2 . In this case, in the MNS we have that:
l D = pk = (0 || 0 || ... || 0 || ... || 0),
k=1 1 l
D = pk = (1|| 0 || ... || 0 || ... || 0), 2 k=2 where l – the number of bases of the MNS.
According to the representation of the MS numbers in the MNS, we have that: 1 CM→NS = 2 D + CMNS , (C MrNS )→ = 12 D + C MrNS .
When changing the domain of numbers CMNS and CM→NS from the mathematical expression (3) can be defined as: (C MrNS )→ = 1 D + C MrNS mod D.
2 Let's carry out the following numerical transformations:
1 1 2 (CM→NS )2 = CM→NS CM→NS = ( D + CMNS ) ( D + CMNS ) = CMNS + CMNS D +
2 2 In this case, expression (5) will be presented as:
Mathematical ratio (9) is a generalized SMR process of exponentiating numbers modulo MNS. For the convenience of applying ratio (9), it is sometimes possible to use the ratio: [c1r (mod p1) || c2r (mod p2 ) || ... || ckr (mod pk ) || ... || clr (mod p1)]→ = = (c1→ || c2→ || ... || ck→−1 || ck→ || ck→+1 || ... || cl ) → r Processed numbers C MrNS and (CM→NS )r are in the range: − 1 D C MrNS 1 ( D − 1) , 2 2 0 (CM→NS )r D −1.
Based on SMR (9) implementation of the operation of exponentiating numbers, consider the method of tabular (matrix) realization of the operation of exponentiating numbers modulo MNS in all numeric domain [15-18]. With a tabular realization of the operation of exponentiating numbers modulo pk MNS, the residues of the number CM→NS are encoded by the tabular multiplication code (TMC) [13] as follows ck→ = [c→k || (ck→ )* ]. The sign c→k of the TMC can be represented in the
For pk – an even number: following form.
For pk – an even number:
For pk – an odd number: wherein 0 (сk→ )* pk .
2
For pk – an odd number: wherein 0 (сk→ )* ( pk −1) .
0, if 0 ck→ c→k = pk , 2 p 1, if k ck→ pk − 1.
2 0, if 0 ck→ c→k = 1, if ( pk −1) 2 ( pk −1) 2
, ck→ pk −1. (сk→ )* = сk→ , if 0 сk→ с→ = pk − сk→ , if k pk ; 2 p k сk→ pk − 1, 2 (сk→ )* = сk→ , if 0 сk→ k→ = pk − сk→ , if с ( pk −1)
2 ( pk −1)
; 2 сk→ pk −1, (11) (12) (13) (14) (15) 2
Result (сk→ сk→ ) mod pk residue multiplication operations сk→ on itself modulo pk submitted to TMC, i.е.
in the form
k→ || [(сk→ )* (сk→ )* ]mod pk . ( c→k + c→k ) = 0 (mod 2). In this case, we have that:
(сk→ сk→ ) mod pk = [(сk→ )* (сk→ )* ]mod pk , wherein 0 [(сk→ )* (сk→ )* ]mod pk pk −1.
Based on the developed SMR (8) and using the tabular realization of the modular multiplication operation [13, 19-22], the article improves the method of exponentiating numbers modulo MNS in all numeric domain.
The developed method. A method for exponentiating numbers in the MNS in all numeric domain consists of the following stages: 1. Set the initial numbers for the realization of the method for exponentiating number CMNS = (c1 || c2 || ... || ck −1 || ck || ck +1 || ... || cl ), an arbitrary modulo pk (k = 1, l) MNS (to the degree
the condition performed of r). 2.
Coding of initial numbers CMNS into code words [23] presented in the MS of the form CM→NS :
p ck→ = pk −ck→, if k ck→ pk −1,
2 wherein 0 (ck→)* pk ; 2 0, if 0 ck→ (pk −1) , 2 for pk – an odd number: c→ = k
p 1, if k ck→ pk −1, 2 (ck→)* = ck→ , if 0 ck→ (pk −1);
2 ck→ = pk −ck→, if (pk −1)
2 wherein 0 (ck→)* (pk −1);
2 the form k→ ||[(ck→)(ck→)]mod pk .
1, if (pk −1) 2
ck→ pk −1, ck→ pk −1, − 1 D CMNS 1 (D −1), (CMrNS )→ = 1 D + CMrNS , if CMrNS 0, 1 1
2 − D CMrNS (D −1), 2 2 2 2 0 CM→NS D −1. (CMrNS )→ = 1 D − CMrNS , if CMrNS 0, 0 (CM→NS )r D −1.
2 3. Representation of the residues c→ k of the number CM→NS = (c1→ ||c2→ ||...|| ck→−1 || ck→ || ck→+1 ||...|| cl→) in the MS by modules pk (k =1, l) based on the 4. Definition of result (ck→)2 = (ck→ ck→)mod pk, (k =1, l) modular multiplication operations in 5. Determining the result of an operation (CM→NS )r−1 CM→NS modD =(c1→)r−1mod p1 || exponentiating numbers ck of integer CMNS = (c1 ||c2 ||...|| ck−1 || ck || ck+1 ||...|| cl) modulo pk (k =1, l) MNS to the degree r. → 6. According to the SMR: c1r(mod p1)||...||ckr(mod pk)||...||clr(mod pl) = (c1→ ||c2→ ||... ...|| ck→−1 || ck→ || ck→+1 ||...|| cl→)r the process of exponentiating numbers modulo, the operation is implemented:
(CM→NS )r−1 CM→NS mod D =(c1→)r−1 mod p1 || (c2→)r−1 mod p2 ||...
...|| (ck→)r−1 mod pk ||...|| (cl→)r−1 mod ml(c1→ || c2→ ||...|| ck→−1 || ck→ || ck→+1 ||...||cl→) exponentiating numbers modulo pk MNS in all numeric domain.
The result of the research is induced in the form of using the developed method for exponentiating numbers for the MNS with bases p1 = 2, p2 = 5, p3 = 7, wherein D = 70. Total volume of positive codewords CMNS in the MNS presented in Table 1, where CPNS – number in the positional number system (PNS). Table 2 submitts the original positive numbers CMNS and numbers in MS CM→NS . The practical use of the developed method for the MNS with bases p1 = 2, p2 = 5, p3 = 7, l D = pk = p1 p2 p3 = 2 5 7 = 70 is presented in the form of examples.
k=1
Example 1. Let CMNS = 2 = (0 || 2 || 2) and r = 2. Let’s define the value of CMrNS = 22. Because CMNS = 2 0, then we get that CM→NS = 1 D + CMNS = 35 + 2 = 37 = (1|| 0 || 0) + (0 || 2 || 2) = 2 = (1|| 2 || 2) = 37. Because r = 2 as a result of multiplying the value of CM→NS = (1|| 2 || 2) by itself 11 = 1(mod 2), 2 2 = 4(mod 5) and 2 2 = 4(mod 7), we get that (CM→NS )2 = (1|| 4 || 4) = 39.
Check: (CM→NS )2 = 372 = 37 37 = 1369 = 39(mod 70) = (1|| 2 || 2) (1|| 2 || 2) = (1|| 4 || 4) = 39.
1 1 (CM2NS )→ = D + CM2NS , CM2NS = (CM2NS )→ − D , 22 = 39 − 35 = 4, 22 = 4.
2 2 Example 2. Let CMNS = −2 2 = (0 || 2 || 2) and r = 2. Because
1 CM→NS = D − CMNS = 35 − 2 = 33 = (1|| 0 || 0) − (0 || 2 || 2) = (1|| 3 || 5) = 33. Because r = 2 2 11 = 1(mod 2), 3 3 = 4(mod 5), 5 5 = 4(mod 7), we get that (CM→NS )2 = (1|| 4 || 4) = 39. CMNS = −2 0, then we have
2 1 CMNS = (CM2NS )→ − D , (−2)2 = 39 − 35 = 4, (−2)2 = 4.
2 Example 3. Let CMNS = −2 2 = (0 || 2 || 2) and r = 3. Because CMNS = −2 0, then we have that 1 CM→NS = D − CMNS = 35 − 2 = 33 = (1|| 0 || 0) − (0 || 2 || 2) = (1|| 3 || 5) = 33. The first iteration of the 2 multiplication gives the result: CM→NS CM→NS = (CM→NS )2 , 11 = 1(mod 2), 3 3 = 4(mod 5), 5 5 = 4(mod 7). The second iteration (because r = 3 ): (CM→NS )2 CM→NS . In this case we have (CM→NS )2 = (1|| 4 || 4), (CM→NS )3 = (CM→NS )2 CM→NS = (1|| 4 || 4) (1|| 3 || 5) = (1|| 2 || 6) = 27.
Check: (CM→NS )3 = 333 = 35937 = 27(mod 70) = CM→NS CM→NS CM→NS = (1|| 3 || 5) (1|| 3 || 5) (1|| 3 || 5) = 3 1 = (1|| 2 || 6) = 27. CMNS = (CM3NS )→ − D, (−2)3 = 27 − 35, (−23 ) = −8.
2 CM→NS = 1 2
Example 4. Let
CMNS = −3 3 = (1|| 3 || 3) and r = 3.
CMNS = −3 0, then
D − CMNS = 35 − 3 = 32 = (1|| 0 || 0) − (1|| 3 || 3) = (0 || 2 || 4) = 32. The first iteration of the multiplication gives the result: CM→NS CM→NS = (CM→NS )2 = (0 || 2 || 4) (0 || 2 || 4) = (0 || 4 || 2). The second iteration (because r = 3 ): (CM→NS )2 CM→NS = (CM→NS )3 = (0 || 4 || 2) (0 || 2 || 4) = (0 || 3 ||1). Thus, we get that C MrNS = (−3)3 = (0 || 3 ||1) = 8.
The procedure for realization the operation of exponentiating numbers in the MNS in a positive numeric domain has been researched. As the operation of exponentiating numbers is one of the key operations of many algorithms and protocols that are used in modern CS (programming, cryptography, optimization algorithms, etc.), and there is no effective implementation of this operation, especially for negative numbers. Two options for representing numbers in the MNS are considered, in all numeric domain. The first option is as follows: the original number in the MNS has an additional two sign bits +CMNS and −CMNS . These bits symbolize the sign of the number in the MNS. The second option is as follows: for perform the process of realizing the operation of exponentiating numbers by modulo MNS in all numeric domain, it is supposed to represent the original number in a modular structure. The article developed a method for exponentiating numbers in the MNS, both in positive and negative numeric domain. This method is based on the use of a synthesized mathematical model in an analytical ratio, which is a generalized system of mathematical ratios of the process of exponentiating numbers modulo MNS. The development of the method was carried out by applying a special coding of numbers in the MS using the tabular principle of data processing. The result of the developed method is presented in the form of examples of the operation of exponentiating numbers represented in the MNS. An analysis of the solution of examples showed the practical value of the developed method.