Оптимізація багаторозрядного множення на основі ШПФ у паралельній моделі обчислень

Автор(и)

  • Андрій Миколайович Терещенко старший інженер-програміст ТОВ «СімКорп – Україна»

DOI:

https://doi.org/10.18372/2410-7840.16.7533

Ключові слова:

паралельна модель обчислень, асиметрична криптографія, багаторозрядна арифметика, багаторозрядне множення, ДПФ, ШПФ.

Анотація

Розглядається операція багаторозрядного множення у паралельній моделі обчислень, від швидкодії якої залежитьшвидкодія асиметричних криптографічних програмно-апаратних комплексів. Наведено модифікацію алгоритмуреалізації операції множення двох N-розрядних чисел на основі ШПФ та попереднім обчисленням коефіцієнтів ДПФ.У новому алгоритмі операції виконуються над сигналами розрядності N, у противагу стандартному алгоритму, якийоперує сигналами розрядністю 2N. Даний алгоритм дозволяє зменшити у два рази кількість задіяних паралельнихпроцесорів, зберігаючи обчислювальну складність для кожного з процесорів, у порівняні зі стандартним алгоритмом.Наведений алгоритм є ефективним також і в послідовній моделі обчислень.

Біографія автора

Андрій Миколайович Терещенко, старший інженер-програміст ТОВ «СімКорп – Україна»

кандидат фізико-математичних наук

Посилання

. Zadiraka V.K. (1985) «About requirements for

parallel data processing in FFT processor» Algorithm

and computer software optimization, Kyiv.: V.M.

Glushkov Institute of Cybernetics of NAS of

Ukraine, P. 3-10.

. Zadiraka V., Oleksyuk O. (2003) «Computer

multidigit arithmetic: Naukove vidanya», Kyiv, 263 p.

. Tereshchenko A.N. (2008) «Multiplication of big

numbers of the length of N with computing only

DTF of the length of N», Computer mathematics,

№ 1, P. 122-130.

. Tereshchenko A.N., Zadiraka V.K. (2012)

«Optimization of big numbers of the length of N

multiplication based on DTF of the length of N»,

Programming problems, № 4, P. 116-130.

##submission.downloads##

Опубліковано

2015-02-03

Як цитувати

Терещенко, А. М. (2015). Оптимізація багаторозрядного множення на основі ШПФ у паралельній моделі обчислень. Захист інформації, 16(3), 178–184. https://doi.org/10.18372/2410-7840.16.7533

Номер

Том 16 № 3 (2014)

Розділ

Статті

Ліцензія

Науковий журнал дотримується принципів відкритого доступу (Open Access) та забезпечує вільний, негайний і постійний доступ до всіх опублікованих матеріалів без фінансових, технічних або юридичних обмежень для читачів.

Усі статті публікуються у відкритому доступі відповідно до ліцензії Creative Commons Attribution 4.0 International (CC BY 4.0).

Авторські права

Автори, які публікують свої роботи в журналі:

  • зберігають за собою авторські права на свої публікації;

  • надають журналу право на перше опублікування статті;

  • погоджуються на поширення матеріалів за ліцензією CC BY 4.0;

  • мають право повторно використовувати, архівувати та поширювати свої роботи (у тому числі в інституційних та тематичних репозитаріях) за умови посилання на первинну публікацію в журналі.