2025, issue 1, p. 43-53
Received 10.02.2025; Revised 27.02.2025; Accepted 25.03.2025
Published 28.03.2025; First Online 30.03.2025
https://doi.org/10.34229/2707-451X.25.1.4
Previous | FULL TEXT (in Ukrainian) | Next
Square a Multi-Digit Number on 8 Processors in a Parallel Computational Model
Andrii Tereshchenko 
V.M. Glushkov Institute of Cybernetics of the NAS of Ukraine, Kyiv
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. Currently, data security and confidentiality are becoming an urgent challenge not only for individuals, but also at the state level. The level of cyberattacks has grown to such an extent that hackers can disable servers, change data in cloud storage, which makes it impossible to work entire government agencies for a long period, which requires significant efforts to restore resources. Cyberattacks are becoming more organized and selective. The use of asymmetric cryptographic software and hardware complexes is becoming an obligatory element of protection. The speed of asymmetric cryptographic operations such as encryption, decryption, key verification depends on the speed of the modulo squaring operation. Using fast methods, the operation of squaring a number of N digits can be performed with less complexity than the operation of multiplying two numbers of N digits.
This paper considers a method for implementing the squaring operation, which allows reducing the number of multiplication and squaring operations compared to the Karatsuba method. The proposed method can be used recursively and is convenient for parallelization, which increases its range of effective use.
The purpose of the article is to reduce the number of single-digit multiplication and squaring operations to speed up the execution time of the operation of squaring a number with a length of N digits (N=2n, N≥4). Reduce the number of multiplications with a length of N/4 digits to 8 operations in the case of squaring a number with a length of N digits. Reduce the overall computational complexity and find a modification in which the number of addition and subtraction steps will be the smallest compared to other modifications. Build a squaring algorithm based on the modification found. Find an efficient method of squaring numbers with a length of up to 4096 bits with the possibility of parallelization.
Results. The structure of a number that is divided into four parts for the implementation of the squaring operation is considered. The effect of splitting a 4-digit number into a 2-digit number and a 4-digit number with a simpler structure, artificially created due to the repetition of its parts, on the implementation of the squaring operation is investigated. A method for implementing the squaring operation of a 4-digit number in eight one-digit multiplications is developed, which is one multiplication less than in the Karatsuba method, which is performed recursively. To obtain the result of the squaring operation, linear combinations of the multiplication results are used. The paper presents such a modification of the implementation, which has a small number of addition and subtraction operations in linear combinations. An algorithm based on the proposed modification is presented, which shows how a 4-digit number with a heterogeneous structure can be split into a 2-digit number and a 4-digit number with a simpler structure due to repetition. An analysis of the complexity in terms of the number of single-digit multiplication operations depending on the length of the number N is carried out in the case of recursive use of the algorithm for implementing the square operation for comparison with the Karatsuba method.
Conclusions. The paper presents an algorithm for implementing the operation of squaring a 4-digit number based on eight single-digit multiplications, three of which are squaring operations. The example shows the implementation of the operation of squaring a 4-digit number with a heterogeneous structure. The complexity of the proposed method is estimated for numbers of length N digits, and it is shown that the calculation can be performed on the basis of three squaring operations of numbers of length N/4 digits and five multiplications of numbers of length N/4 digits. Based on the comparative analysis, it is shown that the proposed squaring method is better than the Karatsuba method by 11 % for (N = 4) and by 16 % with increasing N. To verify the result of the calculation, the algorithm-program SquaringNumber2aa in the APL programming language is implemented. The method can be used recursively, which increases the possibilities of parallelizing the implementation of the square operation of large numbers, which increases its effective range of use to 4096 bits.
Keywords: multidigit arithmetic, multidigit multiplication, multidigit squaring, multidigit squaring by modulo, asymmetric cryptography, parallel computational model.
Cite as: Tereshchenko A. Square a Multi-Digit Number on 8 Processors in a Parallel Computational Model. Cybernetics and Computer Technologies. 2025. 1. P. 43–53. (in Ukrainian) https://doi.org/10.34229/2707-451X.25.1.4
References
1. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM. 1978. Vol. 21, N 2. P. 120–126. https://doi.org/10.1145/359340.359342
2. Zadiraka V.K., Kudyn A.M. Construction of hardware and software systems for arithmetic of very large numbers. Kompiuternaia matematyka. 2001. V.1. P. 158–163. (in Russian)
3. Tereshchenko A., Zadiraka V. Algorithm for calculation the carry and borrow signs in multi-digit operations in the parallel computational model. International Journal of Computing. 2023. 22(1). P. 21–28. https://doi.org/10.47839/ijc.22.1.2875
4. Karatsuba A., Ofman Yu. Multiplication of many-digital numbers by automatic computers. Dokl. Akad. Nauk SSSR. 1962. 145 (2). P. 293–294. (in Russian) http://mi.mathnet.ru/dan26729
5. Cook S.A. On the Minimum Computation Time of Functions, 1966 PhD thesis, Harvard University Department of Mathematics. http://cr.yp.to/bib/1966/cook.html (accessed: 10.02.2025)
6. Anisimov A.V. Multi-digit algorithmic theory. Multi-digit modular arithmetic. Kyiv: “Akademperiodika”. 2001. 153 p. (in Ukrainian) http://books.zntu.edu.ua/book_info.pl?id=21106
7. Schonhage A., Strassen V. Schnelle Multiplikation großen Zahlen. Computing. 1971. Vol. 7, No. 3–4. P. 281–292. https://doi.org/10.1007/BF02242355
8. Zadiraka V., Oleksyuk О. Computer arithmetic of the multidigit number. Kyiv: Naukove vydannya, 2003. 263 p. (in Ukrainian)
9. Nykolaichuk Y.M., Kasianchuk M.M., Yakimenko I.Z., Ivasiev S.V. Effective method of modular multiplication in the number-theoretic basis of Rademacher – Chrestenson. Visnik Natsionalnogo universitetu "Lvivska politehnika". Komp’yuterni sistemi ta merezhi. 2014. No. 806. P. 195–199. http://nbuv.gov.ua/UJRN/VNULPKSM_2014_806_31 (in Russian)
10. Khimich O.M., Sydoruk V.A. Using of the mixed size in the mathematical model. Matematichne ta komp’yuterne modelyuvannya. SerIya: FIziko-matematichnI nauki. Zb. nauk. prats. 2019. Vol. 19. P. 180–187. (in Ukrainian) https://doi.org/10.32626/2308-5878.2019-19.180-187
11. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multidigit numbers in sequential and parallel computational models. Kyiv: Naukova dumka, 2021. 136 p. (in Ukrainian)
12. Tereshchenko A., Zadiraka V. Generating Big Numbers for Testing Multi-Digit Arithmetic Algorithms. Cybernetics and Computer Technologies. 2021. Iss. 2. P. 39–56. (in Ukrainian) https://doi.org/10.34229/2707-451X.21.2.4
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)
Previous | FULL TEXT (in Ukrainian) | Next