Cybernetics And Systems Analysis logo
Інформація редакції Аннотації статей Автори Архів
Кібернетика та Системний Аналіз
Міжнародний Науково-Теоретичний Журнал
Том 62 >>> № 5 ВЕРЕСЕНЬ — ЖОВТЕНЬ 2026
-->


DOI 10.34229/KCA2522-9664.26.5.4
УДК 519.6

В.К. ЗАДІРАКА
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
 zvk@ukr.net

А.М. ТЕРЕЩЕНКО
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
 teramidi@ukr.net


АЛГОРИТМ БАГАТОСЛІВНОГО МНОЖЕННЯ
НА ОСНОВІ ПЕРЕТВОРЕННЯ МЕРСЕННА

Анотація. Розглянуто алгоритм реалізації багатослівної операції множення на основі теоретико-числового перетворення Мерсенна. Числа Мерсенна та їхні властивості широко використовують в кібербезпеці, цифровому обробленні сигналів. Алгоритми на основі перетворення Мерсенна можна також реалізувати на квантових комп’ютерах з можливістю суперрозпаралелювання. Операція багатослівного множення є однією з основних операцій шифрування, дешифрування, генерування та верифікації ключів асиметричної криптографії. Від швидкодії цієї багатослівної операції залежить швидкодія операцій асиметричної криптографії. Наведено новий швидкий алгоритм знаходження оберненого числа, яке використовується для обчислення оберненого перетворення Мерсенна, що дає змогу будувати алгоритми реалізації операцій над числами довжиною у мільйон або більше бітів. Отримано оцінку складності алгоритму на основі перетворення Мерсенна для чисел довжиною N слів і зазначено, що такий алгоритм може виконуватися рекурсивно. Проаналізовано межу максимально можливого значення множника в залежності від довжини перетворення Мерсенна p для алгоритму багатослівного множення. Запропоновано новий алгоритм множення за модулем числа Мерсенна на основі двох операцій множення половинної довжини замість трьох множень за методом Карацуби. Здійснено порівняльний аналіз складності за кількістю операцій однослівного множення алгоритму на основі перетворення Мерсенна у комбінації з методом Карацуби та на основі методу Карацуби на прикладі багатослівної операції піднесення до квадрата.

Ключові слова: багатослівна арифметика, багатослівне множення, багатослівне піднесення до квадрата, багатослівне множення за модулем, піднесення багатослівного числа до степеня за модулем, теоретико-числове перетворення, асиметрична криптографія.


повний текст

СПИСОК ЛІТЕРАТУРИ

    1. Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах. ДАН CCCP, 1962. Т. 145. С. 293–294.
    2. Schnhage A. Multiplikation groer Zahlen. Computing. 1966. Vol. 1. P. 182–196.
    3. Задірака В.К., Терещенко А.М. Комп‘ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 136 с.
    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. Анісімов А.В. Aлгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с.
    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.



Інформація редакції Аннотації статей Автори Архів
Журнал Тематичні Розділи Редакція Редакційна колегія Приклади документів Передплата Контакти
© 2026 Kibernetika.org. All rights reserved.