інтернет-адреса сторінки: http://jnas.nbuv.gov.ua/article/UJRN-0001335527 Кібернетика та системний аналіз А - 2019 / Випуск (2022, Т. 58, № 4)
Задірака В. К., Терещенко А. М. Оптимізація багаторозрядної операції множення на основі дискретних перетворень (Фур'є, косинусних, синусних) у паралельній моделі обчислення Розглянуто операцію багаторозрядного множення, від швидкодії якої залежить швидкодія асиметричних криптографічних програмно-апаратних комплексів. Запропоновано алгоритми реалізації операції множення двох N-розрядних чисел на основі дискретних косинусних і синусних перетворень (ДКП та ДСП). За рахунок використання ДКП та ДСП розділено обчислення для дійсної та уявної частин дискретного перетворення Фур'є (ДПФ) дійсного сигналу парної довжини, що надає змогу перевести обчислення з поля комплексних чисел у поле дійсних чисел та зменшити складність багаторозрядної операції множення за кількістю однорозрядних операцій комплексного множення. Проведено заміну операцій алгоритму для збереження симетрії у дійсній або уявній частинах багаторозрядних чисел, що надає змогу використовувати ДКП і ДСП меншої розрядності N/2 + 1 і розширює можливості з розпаралелювання під час реалізації багаторозрядного множення.
https://doi.org/10.1007/s10559-022-00495-6
Scopus
Бібліографічний опис: Задірака В. К., Терещенко А. М. Оптимізація багаторозрядної операції множення на основі дискретних перетворень (Фур'є, косинусних, синусних) у паралельній моделі обчислення. Кібернетика та системний аналіз. 2022. Т. 58, № 4. С. 139–161. doi: https://doi.org/10.1007/s10559-022-00495-6 URL: http://jnas.nbuv.gov.ua/article/UJRN-0001335527 |
Cybernetics and Systems Analysis / Issue (2022, 58 (4))
Zadiraka V.K.,
Tereshchenko A.M.
Optimization of multidigit multiplication based on discrete transforms (Furie, cosine, sine) in parallel computational model The authors consider the multidigit multiplication operation, on whose speed the speed of asymmetric cryptographic software and hardware depends. Algorithms for implementing the multiplication of two N-digit numbers based on discrete cosine and sine transforms (DCT and DST) are proposed. Due to the use of DCT and DST, the calculations for the real and imaginary parts of the discrete Fourier transform (DFT) of a real even-length signal are separated, which allows translating the complex-number calculations to real-number calculations. The operations of the algorithm are replaced in order to preserve symmetry in the real or imaginary parts of the multidigit numbers, which allows the use of DCT and DST of lower length N / 2 + 1 and increases the possibility of parallelizing in multidigit multiplication. © 2022, Springer Science+Business Media, LLC, part of Springer Nature. Keywords: asymmetric cryptography, discrete cosine transform, discrete Fourier transform, discrete sine transform, fast Fourier algorithm, multidigit arithmetic, multidigit multiplication, Cosine transforms, Cryptography, Discrete Fourier transforms, Asymmetric cryptography, Discrete sine transforms, Fast fourier algorithms, Fourier, Imaginary parts, Multidigit arithmetic, Multidigit multiplication, Optimisations, Real part, Sine transforms, Discrete cosine transforms
Cite: Zadiraka V.K.,
Tereshchenko A.M.
(2022). Optimization of multidigit multiplication based on discrete transforms (Furie, cosine, sine) in parallel computational model. Cybernetics and Systems Analysis, 58 (4), 139–161. doi: https://doi.org/10.1007/s10559-022-00495-6 http://jnas.nbuv.gov.ua/article/UJRN-0001335527 [In Ukrainian]. |