C&SA | Contents

Volume 61 >>> № 3 MAY — JUNE 2025

-->

DOI 10.34229/KCA2522-9664.25.3.17

UDC 519.6

V.K. Zadiraka¹, A.M. Tereshchenko²

¹ V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

zvk140@ukr.net

² V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine

teramidi@ukr.net

AN EFFICIENT ALGORITHM FOR SQUARING MULTI-WORD NUMBERS

Abstract. A method of implementing the operation of squaring a number with a length of N words (N = 2ⁿ ) is proposed, which allows performing calculations based on eight multiplications of numbers with a length of N / 4 words (N ≥ 4 ). The squaring operation is one of the main operations of encryption, decryption, and verification of keys in asymmetric cryptography. The speed of operations of asymmetric cryptography depends on the speed of the square operation. The complexity of the proposed method for numbers with a length of N words is evaluated in the form of the theorem, and it is shown that the calculation can be performed based on four squares of numbers with a length of N / 4 words and four multiplications of numbers with a length of N / 4 words. For squaring a 4-word number, the developed method requires eight one-word multiplication operations, one multiplication less than in the Karatsuba‘s method, which is used recursively. The method can be used recursively, which increases the possibility of parallelizing the implementation of squaring large numbers. The results of the paper can be used for the development of fast multi-word arithmetic algorithms and the implementation of the squaring of large numbers in a circuit design.

Keywords: multiword arithmetic, multiword multiplication, multiword squaring, multiword squaring by modulo, asymmetric cryptography.

full text

REFERENCES

1. Karatsuba A.A., Ofman Yu.P. Multiplication of multi-digit numbers on automata. DAN SSSR, 1962.Vol. 145. P. 293–294.

2. Cook S.A. On the Minimum Computation Time of Functions. Chapter 3, Ph. D. Thesis Harvard University, Cembridge, 1966. P 51–77.

3. Schnhage A. Multiplikation grober Zahlen. Computing. 1966. Vol. 1. P. 182–196.

4. Anisimov A.V. Algorithmic theory of large numbers. Modular arithmetic of large numbers [in Ukrainian]. Kyiv: Akademperiodika, 2001. 153 p.

5. Zadiraka V., Oleksiuk O. Computer arithmetic of multi-digit numbers [in Ukrainian]. Kyiv: Nauk. Dumka, 2003. 263 p.

6. Nikolaychuk Ya.M., Kasyanchuk M.M., Yakymenko I.Z., Ivasiev S.V. An effective method of modular multiplication in the Rademacher–Krestenson number-theoretic basis. Bull. National University “Lviv Polytechnic”. Computer systems and networks. 2014. N 806. P. 195–199.

7. Khimich O.M., Sydoruk V.A. Using mixed bitness in mathematical modeling. Mathematical and computer modeling. Series: Phys.-Math. Sciences. Collection of scientific works. 2019. Iss. 19. P. 180–187.

8. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-digit numbers in sequential and parallel computing models [in Ukrainian]. Kyiv: Nauk. Dumka, 2021. 136 p.

9. 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.

10. Zadiraka V.K., Kudin A.M. Construction of software and hardware complexes for arithmetic of very large numbers. Komp'yuternaya matematika. 2001. Vol.1. P. 158–163.

11. 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. Vol. 22, N 1. P. 21–28.