УДК 519.6
В.К. ЗАДІРАКА,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
zvk140@ukr.net
А.М. ТЕРЕЩЕНКО,
Інститут кібернетики ім. В.М. Глушкова НАН України, Київ, Україна,
teramidi@ukr.net
ОПТИМІЗАЦІЯ БАГАТОРОЗРЯДНОЇ ОПЕРАЦІЇ МНОЖЕННЯ
НА ОСНОВІ ДИСКРЕТНИХ ПЕРЕТВОРЕНЬ (ФУР’Є, КОСИНУСНИХ,
СИНУСНИХ) У ПАРАЛЕЛЬНІЙ МОДЕЛІ ОБЧИСЛЕННЯ
Анотація. Розглянуто операцію багаторозрядного множення, від швидкодії якої залежить
швидкодія асиметричних криптографічних програмно-апаратних комплексів.
Запропо-новано алгоритми реалізації операції множення двох N -розрядних чисел
на основі дискретних косинусних та синусних перетворень (ДКП та ДСП).
За рахунок вико-ристання ДКП та ДСП розділено обчислення для дійсної
та уявної частин дискретного перетворення Фур’є (ДПФ) дійсного сигналу парної довжини,
що дає змогу перевести обчислення з поля комплексних чисел у поле дійсних чисел
та зменшити складність багаторозрядної операції множення за кількістю однорозрядних операцій комплексного множення.
Проведено заміну операцій алгоритму для збереження симетрії у дійсній або уявній частинах багаторозрядних чисел,
що дає змогу використовувати ДКП та ДСП меншої розрядності N / 2 + 1 та розширює можливості
з розпаралелювання під час реалізації багаторозрядного множення.
Ключові слова: багаторозрядне множення, багаторозрядна арифметика, асиметрична криптографія, дискретне косинусне перетворення, дискретне синусне перетворення, дискретне перетворення Фур’є, швидкий алгоритм обчислення Фур’є.
ПОВНИЙ ТЕКСТ
СПИСОК ЛІТЕРАТУРИ
- Анісімов А.В. Алгоритмічна теорія великих чисел. Модулярна арифметика великих чисел. Київ: Академперіодика, 2001. 153 с.
- Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. Київ: Наукова думка, 2003. 263 с.
- Задирака В.К. Теория вычисления преобразования Фурье. Киев: Наукова думка, 1983. 213 с.
- Задірака В.К., Терещенко А.М. Комп’ютерна арифметика багаторозрядних чисел у послідовній та паралельній моделях обчислень. Київ: Наукова думка, 2021. 136 с.
- Качко Е.Г. Распараллеливание алгоритмов умножения чисел многократной точности. Вестник Уфимского государственного авиационного технического университета. 2011. Е 15, № 5 (45). С. 142–147.
- Николайчук Я.М., Касянчук М.М., Якименко І.З., Івасьєв С.В. Ефективний метод модулярного множення в теоретико–числовому базисі Радемахера–Крестенсона. Вісник Національного університету «Львівська політехніка». Комп’ютерні системи та мережі. 2014. № 806. C. 195–199.
- Хіміч О.М., Сидорук В.А. Використання мішаної розрядності у математичному моделюванні. Математичне та комп’ютерне моделювання. Серія: Фізико-математичні науки. 2019. Вип. 19. С. 180–187.
- Карацуба А.А., Офман Ю.П. Умножение многоразрядных чисел на автоматах. ДАН CCCP. 1962. Т. 145, № 2. С. 293–294.
- Cooley J.W., Tukey J.W. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation. 1965. Vol. 19, N 90. P. 297–301.
- Schonhage A., Strassen V. Schnelle Multiplikation groen Zahlen. Computing. 1971. Vol. 7, Iss. 3–4. P. 281–292.
- Pitassi D.A. Fast convolution using the Walsh transform. Proc. 1971 Symp. Applications of Walsh Functions (13–15 April 1971, Washington, D.C., USA). Washington, D.C., 1971. P. 130–133.
- Терещенко А.Н., Мельникова С.С., Гнатив Л.А., Задирака В. К., Кошкина Н.В. Реализация операции умножения с использованием преобразования Уолша. Проблемы управления и информатики. 2010. № 2. С. 102–126.
- Montgomery P.L. Modular multiplication without trial division. Mathematics of Computation. 1985. Vol. 44, N 170. Р. 519–521.
- Cook S.A. On the minimum computation time of functions. PhD thesis. Harvard University, Department of Mathematics. 1966. URL: http://cr.yp.to/bib/1966/cook.html.
- Ahmed N., Natarajan T., Rao K.R. Discrete cosine transform. IEEE Transactions on Computers. 1974. Vol. C–23, Iss. 1. P. 90–93. http://dx.doi.org/10.1109/T-C.1974.223784.
- Jain A.K. A fast Karhunen–LoЩve transform for a class of random processes. IEEE Transactions on Communications. 1976. Vol. 24, N 9. P. 1023–1029.
- Gluth R. Regular FFT–related transform kernels for DCT/DST – based polyphase filter banks. Proc. IEEE 1991 International Conference on Acoustics, Speech and Signal Processing (ICASSP 1991) (14–17 April 1991, Toronto, Canada). Toronto, 1991. P. 2205–2208.
- Чичева М.А. Эффективный алгоритм дискретного косинусного преобразования четной длины. Компьютерная оптика. 1998. № 18. С. 147–149.
- Гнатів Л.О., Луц В.К. Цілочислові модифіковані синус–косинусні перетворення типу VII. Метод побудови і роздільні направлені адаптивні перетворення для intra–прогнозування з блоками яскравості 8x8 у кодуванні зображень/відео. Кібернетика та системний аналіз. 2021. Т. 57, № 1. С. 178–190.
- Терещенко А.М. Оптимізація багаторозрядного множення на основі ШПФ у паралельній моделі обчислень. Захист інформації. 2014. Т. 16, № 3. С.178–184.
- Терещенко А.М., Задирака В.К. Реалізація багаторозрядної операції множення на основі дискретних косинусних та синусних перетворень. Кібернетика та комп’ютерні технології. 2021. № 4. С. 61–79.
