Розгляд операції багаторозрядного множення у паралельній моделі обчислень, від швидкодії якої залежить швидкодія асиметричних криптографічних програмно-апаратних комплексів. Огляд модифікації алгоритму реалізації операції множення двох N-розрядних чисел.
Аннотация к работе
Необхідно зменшити розрядність оброблюваних даних у два рази з 2N до N , при реалізації операції множення двох N-розрядних чисел на основі ШПФ та передобчислених коефіцієнтах ДПФ, побудувати ефективний алгоритм обчислення R2N у паралельній моделі обчислень, знайти кількість однорозрядних операцій виконуваних кожним з паралельних процесорів. N-розрядне число можна представити у вигляді N-розрядного сигналу, де комплексна чистина кожного розряду дорівнює нулю, тобто додавання нульової комплексної частини до кожного розряду багаторозрядного числа переводить число у сигнал. Перехід від N - до 2N-розрядних чисел та використання ШПФ для сигналів розрядністю 2N поясняється тим, що результатом множення двох N-розрядних чисел буде число розрядністю 2N. Алгоритм 1 множення двох N-розрядних чисел на основі ШПФ для сигналів розрядності 2N в паралельній моделі обчислень задіє не більше 2N паралельних процесорів на будь-якому кроці, кожний з яких виконає не більше 3?2log2 N комплексних операцій множення. При обчисленні одного перетворення сигналу розрядністю 2N на основі ШПФ для сигналів розрядністю 2N на кроці 2 та 4 Алгоритму 1 необхідно задіяти в два рази меншу кількість паралельних процесорів, тобто N процесорів, так як достатньо однієї операції комплексного множення для обчислення двох виразів ?W N ? X2N (r), які відрізняються лише знаком.