Cybernetics And Systems Analysis logo
Editorial Board Announcements Abstracts Authors Archive
KIBERNETYKA TA SYSTEMNYI ANALIZ
International Theoretical Science Journal
Volume 62 >>> № 5 SEPTEMBER — OCTOBER 2026
-->


DOI 10.34229/KCA2522-9664.26.5.4
UDC 519.6

V.K. Zadiraka
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine,
Kyiv, Ukraine,  zvk@ukr.net

A.M. Tereshchenko
V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine,
Kyiv, Ukraine,  teramidi@ukr.net


A MULTIWORD MULTIPLICATION ALGORITHM BASED
ON THE MERSENNE TRANSFORM

Abstract. The algorithm for implementing the multiword multiplication operation based on the number-theoretic Mersenne transform is considered. Algorithms based on the Mersenne transform can also be implemented on quantum computers with the possibility of superparallelization. The multiword multiplication operation is one of the main operations for encryption, decryption, generation and verification of keys in asymmetric cryptography. The speed of multiword operation determines the speed of asymmetric cryptography operations. A new fast algorithm for finding the inverse is presented, which is used to calculate the inverse Mersenne transform, which allows to build algorithms for implementing operations on numbers with a length of a million or more bits. The complexity of the algorithm based on the Mersenne transform for numbers with a length of N words is estimated and it is also noted that such an algorithm can be executed recursively. The limit of the maximum possible value of the multiplier depending on the length of the Mersenne transform p for the multiword multiplication algorithm is analyzed. The new multiplication algorithm by the Mersenne number modulo based on two half-length multiplications, instead of three multiplications, as in the Karatsuba method, is considered. A comparative analysis of the complexity in terms of the number of operations of single-word multiplication of the method based on the Mersenne transform in combination with the Karatsuba method and the Karatsuba method is carried out.

Keywords: multiword arithmetic, multiword multiplication, multiword squaring, multiword modulo multiplication, modulo exponentiation of a multiword number, number-theoretic transformation, 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. Schnhage A. Multiplikation groer Zahlen. Computing. 1966. Vol. 1. P. 182–196.
    3. Zadiraka V.K., Tereshchenko A.M. Computer arithmetic of multi-digit numbers in sequential and parallel computing models. Kyiv: Nauk. Dumka, 2021. 136 p.
    4. Cook S.A. On the minimum computation time of functions. Chapter 3, Ph. D. Thesis Harvard University, Cambridge, 1966. P. 51–77.
    5. Harvey D., van der Hoeven J. Integer multiplication in time O(nlogn). Annals of Mathematics. Second Series. 2021. Vol. 193, N 2. P. 563–617. https://doi.org/10.4007/annals.2021.10.4007/annals.2021.193.2.4.
    6. Anisimov A.V. Algorithmic theory of large numbers. Modular arithmetic of large numbers. Kyiv: Akademperiodika, 2001. 153 p.
    7. Nikolaychuk Y., Pitukh I. High-performance computing in the residue number system. Cybernetics and Systems Analysis. 2025. Vol. 61. P. 685–696. https://doi.org/10.1007/10.1007/s10559-025-00802-x.
    8. Semotiuk M.V. Number-theoretical methods of factoring composite numbers and calculating the discrete logarithm. Cybernetics and Systems Analysis. 2022. Vol. 58. P. 309–318. https://doi.org/10.1007/s10559-022-00463-0.
    9. Kudin A.M., Kudin I.A., Chikhladze V.Z. Applying the general theory of optimal algorithms in cryptography, steganography, and blockchain technology. Cybernetics and Systems Analysis. 2025. Vol. 61. P. 566–576. https://doi.org/10.1007/s10559-025-00792-w.
    10. Zadiraka V.K., Tereshchenko A.M. An efficient algorithm for squaring multi-word numbers. Cybernetics and Systems Analysis. 2025. Vol. 61. P. 521–526. https://doi.org/10.1007/s10559-025-00788-6.
    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. https://doi.org/10.47839/ijc.22.1.2875.
    12. Matsumoto M., Nishimura T. Mersenne twister: A 623-dimensionally equidistributed uniform pseudorandom number generator. ACM Trans. on Modeling and Computer Simulation. 1998. Vol. 8, N 1. P. 3–30. https://doi.org/10.1145/272991.272995.
    13. Aiello W., Rajagopalan S.R., Venkatesan R. Design of practical and provably good random number generators. Journal of Algorithms. 1998. Vol. 29, N 2. P. 358–389. https://doi.org/10.1006/jagm.1998.0952.
    14. Tian X., Benkrid K. Mersenne twister random number generation on FPGA, CPU and GPU. 2009 NASA/ESA Conference on Adaptive Hardware and Systems. San Francisco. CA. USA, 2009. P. 460–464. https://doi.org/10.1109/ahs.2009.11.
    15. Cannizzo F. VMT19937: A SIMD-Friendly pseudo random number generator based on Mersenne twister 19937, 2023. URL: https://arxiv.org/pdf/2309.16682.
    16. Rader C.M. Discrete convolutions via Mersenne transforms (MIT Lincoln Laboratory). IEEE Transactions on Computers. 1972. Vol. C-21, N 12. P. 1269–1273. https://doi.org/10.1109/t-c.1972.223497.
    17. Winograd S. On computing the discrete Fourier transform. Proc. National Academy of Sciences USA. 1976. Vol. 73, N 4. P. 1005–1006.
    18. Reed I.S., Truong T.K. Fast Mersenne-prime transforms for digital filtering. Proceedings of the Institution of Electrical Engineers. 1978. Vol. 125, N 5. https://doi.org/10.1049/piee.1978.0107.
    19. Wan-Chi Siu, Constantinides A. Hardware realization of Mersenne number transforms for fast digital convolution. ICASSP'84. IEEE International Conference on Acoustics, Speech, and Signal Processing. San Diego CA. USA, 1984. P. 234–237. https://doi.org/10.1109/icassp.1984.1172738.
    20. Boussakta S., Alshibami O., Bouridane A. Radix-4 decimation-in-frequency algorithm for the new Mersenne number transform. 10th IEEE International Conference on Electronics, Circuits and Systems, 2003. ICECS 2003. Proceedings of the 2003, Sharjah, United Arab Emirates, 2003. Vol. 3. P. 1133–1136 (2004). https://doi.org/10.1109/icecs.2003.1301711.
    21. Hamood M.T., Boussakta S. Efficient algorithms for computing the new Mersenne number transform. Digital Signal Processing. 2014. Vol. 25. P. 280–288. URL: https://eprint.ncl.ac.uk/fulltext.aspx?url=197541/DD7BC629-F2AA-4E17-938E-44293A4706C1.pdf&pub_id=197541.
    22. Nussbaumer H.J. Digital filtering using complex Mersenne transforms. (IBM (France)). IBM Journal of Research and Development. Sep. 1976. Vol. 20, N 5. P. 498–504. https://doi.org/10.1147/rd.205.0498.
    23. Bria O.N., Horacio A., Wanza V. RTL fast convolution using the Mersenne number transform CIC-Digital (Comisiуn de Investigaciones Cientнficas de la Provincia de Buenos Aires), 1996. URL: https://openalex.org/W376966329.
    24. Talahmeh S., Pepe S. Enhancing Mersenne transforms by RNS with application to discrete convolution. International Journal of Systems Science. 1997. Vol. 28, N 4. P. 423–427. URL: https://www.academia.edu/62096696/Enhancing_Mersenne_transforms_by_RNS_with_application_to_discrete_convolution.
    25. Boussakta S., Hamood M.T. and Rutter N. Generalized new Mersenne number transforms. IEEE Transactions on Signal Processing. May 2012. Vol. 60, N 5. P. 2640–2647. https://doi.org/10.1109/tsp.2012.2186131.
    26. Reis E., Benlamri R. Accelerating convolutional neural network using discrete orthogonal transforms. TechRxiv. May 19, 2021. https://doi.org/10.36227/techrxiv.14593686.v1.
    27. Prasetiyo Hong S., Arthanto Y.F., Kim J.-Y. Accelerating deep convolutional neural networks using number theoretic transform. IEEE Transactions on Circuits and Systems. I: Regular Papers. Jan. 2023. Vol. 70, N 1. P. 315–326. https://doi.org/10.1109/tcsi.2022.3214528.
    28. Le Ph-H. Ch., Li X. BinaryViT: Pushing binary vision transformers towards convolutional models. Conference: 2023 IEEE/CVF. Conference on Computer Vision and Pattern Recognition Workshops (CVPRW). 2023. URL: https://arxiv.org/pdf/2306.16678.
    29. Solinas J. Generalized Mersenne prime. In: van Tilbong, H.C.A. (Eds.). Encyclopedia of Cryptography and Security. Boston, MA: Springer. https://doi.org/10.1007/0-387-23483-7_174.



Editorial Board Announcements Abstracts Authors Archive
about scope office editorial board instructions for authors subscriptions contacts
© 2026 Kibernetika.org. All rights reserved.