DOI
10.34229/KCA2522-9664.25.3.17
УДК 519.6
В.К. ЗАДІРАКА
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
zvk140@ukr.net
А.М. ТЕРЕЩЕНКО
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
teramidi@ukr.net
ЕФЕКТИВНИЙ АЛГОРИТМ ПІДНЕСЕННЯ ДО КВАДРАТА
БАГАТОСЛІВНИХ ЧИСЕЛ
Анотація. Запропоновано метод реалізації операції піднесення до квадрата числа
довжиною N слів (N = 2n ), який дає змогу обчислювати
на основі восьми множень чисел довжиною N / 4 слів N ≥ 4. Операція піднесення до квадрата є однією з основних операцій шифрування,
дешифрування та верифікації ключів асиметричної криптографії. Від швидкодії цієї операції залежить швидкодія операцій асиметричної криптографії.
Згідно з теоремою оцінено складність запропонованого методу для чисел довжиною N слів та показано,
що обчислення може бути виконано на основі чотирьох піднесень до квадрата чисел довжиною N / 4 слів та чотирьох множень чисел довжиною N / 4 слів.
Піднесення до квадрата чотирислівного числа на основі запропонованого методу може бути виконано із застосуванням восьми множень,
що на одне множення меньше ніж у методі Карацуби, який використовується рекурсивно.
Запропонований метод може бути застосований рекурсивно, що підвищує можливість з розпаралелювання операції піднесення
до квадрата великих чисел. Результати роботи можуть бути використані для розроблення швидких алгоритмів багатослівної арифметики
та для реалізації операції піднесення до квадрата великих чисел у мікросхемному виконанні.
Ключові слова: багатослівна арифметика, багатослівне множення, багатослівне піднесення до квадрата, піднесення до квадрата за модулем, асиметрична криптографія.
повний текст
СПИСОК ЛІТЕРАТУРИ
- 1. Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах. ДАН CCCP, 1962. Т. 145. С. 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. Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с.
- 5. Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. Київ: Наук. думка, 2003. 263 с.
- 6. Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико-числовому базисі Радемахера–Крестенсона. Вісн. Нац. ун-ту «Львівська політехніка». Комп’ютерні системи та мережі. 2014. № 806. C. 195–199.
- 7. Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фіз.-мат. науки. Зб. наук. праць. 2019. Вип. 19. С. 180–187.
- 8. Задірака В.К., Терещенко А.М. Комп‘ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наук. думка, 2021. 136 с.
- 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. Задирака В.К., Кудин А.М. Построение программно-аппаратных комплексов арифметики сверхбольших чисел. Компьютерная математика. 2001. Т.1. С. 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.
