Ефективні за швидкодією алгоритми багаторозрядної арифметики - Автореферат

На даний час існує багато прикладних задач: в двоключовій криптографії (шифрування, дешифрування, електронний цифровий підпис, криптографічні протоколи), аналізу та фільтрації цифрових сигналів, моделюванні фізичних, хімічних (біохімічних) процесів, аеродинаміки, гідродинаміки, розрахунку оболонок ядерних реакторів, при розвязанні яких активно використовується арифметика багаторозрядних чисел. Якщо раніше арифметика багаторозрядних чисел, в основному, використовувалася в двоключовій криптографії для забезпечення необхідної криптостійкості і продуктивності відповідних алгоритмів (для запису одного числа потрібно від 1024 до 4096 бітів), то в останні роки в звязку з появою суперкомпютерів і розвязанням на них надскладних задач область використання багаторозрядної арифметики значно розширилася. Розробці нових методів обчислення операцій багаторозрядної арифметики та методам оптимізації алгоритмів за швидкодією присвячено праці вітчизняних та закордонних авторів: С.А. Необхідно також відмітити, що штатне математичне забезпечення сучасних багатопроцесорних компютерів включає бібліотеки програм, які виконують операції над багаторозрядними числами. Задачі дослідження у відповідності до поставленої мети полягають у наступному: оптимізація за швидкодією алгоритмів обчислення циклічної згортки з використанням швидких перетворень Уолша та Фурє;У вступі обґрунтовано актуальність теми дисертації, сформульовано мету й основні задачі дослідження, визначено обєкт, предмет і методи досліджень, визначено наукову новизну та практичне значення отриманих результатів, особистий внесок автора в роботи, виконані у співавторстві, апробацію результатів дисертації та кількість публікацій за темою дисертації.Метод, узагальнений Девісом, обчислює циклічні згортки розрядністю та потребує обчислення трьох згорток меншої розрядності на всіх ітераціях. Якщо довжина початкової згортки, то буде згорток довжиною 2, для обчислення кожної з яких необхідно два множення. Якщо розбиття згортки відбувається до згортки довжиною 4 (для обчислення якої необхідно пять множень), то загальна кількість множень складає . Відомо, що стандартний алгоритм множення вимагає операцій для множення двох-розрядних чисел. Серед найбільш швидких алгоритмів множення великих чисел можна виділити алгоритм Карацуби - Офмана, що вимагає порядку операцій, та алгоритм Шенхаге - Штрассена, що вимагає порядку операцій.Пропонується новий метод використання циклічної згортки для реалізації багаторозрядної операції множення. Якщо багаторозрядні множники представити в спеціальному вигляді та використовувати як вхідні сигнали в циклічній згортці, то обчислення збігається з стандартним методом множення в стовпчик. Пропонується метод обчислення згортки розрядністю ,-непарне, що розширює діапазон розрядностей, в якому існують ефективні методи обчислення циклічної згортки (див. табл. Для згорток такої розрядності показано, що достатньо обчислити дві згортки розрядністю на останній ітерації, на відміну від методу Пітассі - Девіса, в якому на кожній ітерації необхідно обчислювати три згортки. У загальному вигляді пропонуються формули обчислення згортки розрядністю , ,-непарне, : де , , - оператори ((парний), (непарний), (угору)): , , ; , , .Пропонується алгоритм Шенхаге - Штрассена реалізації операції багаторозрядного множення з використанням оригінальної модифікації алгоритму ШПФ. Для удосконалення діагонального методу пропонується метод, який є комбінацією діагонального методу та методу Карацуби - Офмана з одним рівнем рекурсії (“розщеплення”): . -розрядних чисел за формулою (2) має вигляд: , , , де - кількість однослівних операцій множення, - кількість двослівних операцій додавання, - кількість однослівних операцій віднімання. -розрядних чисел при використанні удосконаленої модифікації діагонального методу (2) має вигляд Порівняльний аналіз за швидкодією модифікації діагонального методу в порівнянні з діагональним методом для різних процесорів наведено в табл.Розглядається алгоритм Монтгомері, що використовується для обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня. У реалізації використовуються два класи лишків, що дозволяє використовувати китайську теорему про лишки. Обчислення відбуваються одночасно у двох класах лишків. Показано, що в алгоритмі Монтгомері задачу знаходження лишку множення двох-розрядних чисел за-розрядним модулем можна звести до знаходження лишку однослівних множень за однослівним модулем, який не є степенем двійки.У дисертаційній роботі у відповідності з поставленою метою вирішена задача підвищення швидкодії операцій багаторозрядної арифметики, які використовуються при розвязанні задач двоключової криптографії, високоточних обчислень, цифрової обробки сигналів та інших задач дискретної, прикладної та обчислювальної математики. Удосконалено метод Пітассі: а) для обчислення згорток розрядністю ,-непарне, за рахунок оригінального представлення початкової згортки двома згортками меншої розрядності. Запропонована модиф

ОСНОВНИЙ ЗМІСТ ДИСЕРТАЦІЇ