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

Размещено на http://www.allbest.ru//

Размещено на http://www.allbest.ru//

Національна академія наук України

Інститут кібернетики імені В.М. Глушкова

01.05.01 - Теоретичні основи інформатики та кібернетики

Автореферат

дисертації на здобуття наукового ступеня кандидата фізико-математичних наук

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

Терещенко Андрій Миколайович

Київ - 2010

Дисертацією є рукопис.

Робота виконана в Інституті кібернетики імені В.М. Глушкова НАН України.

Науковий керівник: доктор фізико-математичних наук, професор,

член-кореспондент НАН України

Задірака Валерій Костянтинович,

Інститут кібернетики імені В.М. Глушкова НАН України, завідувач відділу.

Офіційні опоненти:доктор фізико-математичних наук, професор,

член-кореспондент НАН України

Анісімов Анатолій Васильович,

Київський національній університет імені Тараса Шевченка, декан факультету кібернетики, кандидат технічних наук

Зінченко Ярослав Вікторович,

Інститут спеціального зв`язку та захисту інформації НТУ України “КПІ”, доцент спеціальної кафедри № 2.

Захист відбудеться “ 22 ” жовтня 2010 р. о 12 годині на засіданні спеціалізованої вченої ради Д 26.194.02 в Інституті кібернетики

імені В.М. Глушкова НАН України за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися в науково-технічному архіві

Інституту кібернетики імені В.М. Глушкова НАН України за адресою:

03680, МСП, Київ-187, проспект Академіка Глушкова, 40.

Автореферат розісланий “ 16 ” вересня 2010 р.

Вчений секретар

спеціалізованої вченої радиО.А. ВАГІС

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Якщо раніше арифметика багаторозрядних чисел, в основному, використовувалася в двоключовій криптографії для забезпечення необхідної криптостійкості і продуктивності відповідних алгоритмів (для запису одного числа потрібно від 1024 до 4096 бітів), то в останні роки в зв'язку з появою суперкомп'ютерів і розв'язанням на них надскладних задач область використання багаторозрядної арифметики значно розширилася. В останньому випадку це пов'язано з обов'язковим вивченням неусувної похибки і похибки заокруглення, які накопичуються протягом тривалих чисельних розрахунків. Неврахування цих похибок приводить до того, що інколи отримують комп'ютерні результати, які не мають фізичного змісту.

Достовірність отриманих результатів у значній мірі залежить від чутливості задачі до малих похибок заокруглення. Наприклад, для системи лінійних алгебраїчних рівнянь поняття добре та погано обумовлена матриця тісно пов'язана з обчислювальними можливостями конкретного комп'ютера і довжиною машинного слова. Внаслідок цього одна й та система може кваліфікуватися для однієї довжини мантиси машинного слова як “машинно погано обумовленою” або “майже вирожденою”, а для іншої “машинно добре обумовленою”. Таким чином, один із резервів для отримання достовірного результату для погано обумовленої задачі - підвищення точності представлення чисел і виконання операцій.

Найбільше навантаження в двоключовій криптографії лягає на операцію піднесення до степеня, що є найбільш складною з операцій. Вона реалізується через операції множення та піднесення до квадрата. Тому оптимізації за швидкодією алгоритмів багаторозрядного множення приділяється багато уваги в працях українських та закордонних фахівців.

Розробці нових методів обчислення операцій багаторозрядної арифметики та методам оптимізації алгоритмів за швидкодією присвячено праці вітчизняних та закордонних авторів: С.А. Абрамова, А.В. Анісімова, А.І. Березовського, А.О. Болотова, О.М. Василенка, М. Вельшенбаха, І.В. Горбенка, В.К. Задіраки, Я.В. Зінченка, А.А. Карацуби, Д. Кнута, П.Г. Комби, Х.К. Коха, А.М. Кудіна, С.С. Мельнікової, В.І. Нечаєва, П.Л. Монтгомері, О.С. Олексюка, Ю.П. Офмана, Д.А. Пітассі, М.В. Сінькова, М. Смарта, А.В. Черемушкіна, Л.Б. Шевчук, А. Шенхаге, В. Штрассена та інших.

З'являються нові комп'ютерні технології ефективної реалізації алгоритмів багаторозрядної арифметики на програмованих логічних інтегральних схемах (ПЛІС) для конкретних вхідних даних. Отже розробка нових методів реалізації багаторозрядних операцій, удосконалення існуючих, пошук областей ефективного їх використання є актуальними задачами сьогодення.

Необхідно також відмітити, що штатне математичне забезпечення сучасних багатопроцесорних комп'ютерів включає бібліотеки програм, які виконують операції над багаторозрядними числами. Це додає актуальності темі дослідження.

Зв'язок роботи з науковими програмами, планами, темами. Дисертаційна робота виконана в рамках наукових тем Інституту кібернетики імені В.М. Глушкова НАН України: ВМ.140.07 “Розробити нові та удосконалити існуючі алгоритми для розв'язання задач інформаційної безпеки” (виконується в рамках проекту для наукової молоді відповідно до постанови Президії НАН України № 66 від 06.04.2005 та розпорядження Президії НАН України № 231 від 14.04.2005); договір № 4 НДР “Кристал” від 11.09.2008 р.

Мета та завдання дослідження. Метою роботи є підвищення швидкодії операцій багаторозрядної арифметики, які використовуються для реалізації алгоритмів при розв'язанні задач двоключової криптографії, високоточних обчислень, цифрової обробки сигналів та інших задач дискретної, прикладної та обчислювальної математики.

Задачі дослідження у відповідності до поставленої мети полягають у наступному:

оптимізація за швидкодією алгоритмів обчислення циклічної згортки з використанням швидких перетворень Уолша та Фур'є;

оптимізація за швидкодією алгоритму швидкого перетворення Фур'є;

оптимізація алгоритмів багаторозрядного множення;

оптимізація алгоритмів обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня;

оптимізація алгоритмів обчислення квадратного та кубічного коренів від багаторозрядних чисел; швидкодія алгоритм багаторозрядний

порівняльний аналіз за швидкодією запропонованих алгоритмів з існуючими алгоритмами;

знаходження областей ефективного використання запропонованих алгоритмів.

Об'єкт дослідження - операції над багаторозрядними числами: циклічна згортка, множення однакової та кратної довжини, знаходження лишку, модулярне множення, піднесення до степеня, квадратний та кубічний корені.

Предмет дослідження - побудова ефективних за швидкодією алгоритмів виконання операцій над багаторозрядними цілими додатними числами за рахунок зменшення кількості однослівних операцій.

Методи дослідження. У дисертаційній роботі автором застосовувалися методи: швидких ортогональних перетворень, рекурентних співвідношень, а також основні поняття теорії складності алгоритмів.

Наукова новизна отриманих результатів. Усі теоретичні результати є новими, їх новизна полягає в розробці нових алгоритмів та удосконаленні існуючих методів багаторозрядного множення, обчислення циклічної згортки, обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня, обчислення квадратного та кубічного коренів від багаторозрядних чисел.

До наукових результатів належать наступні:

вперше запропоновано алгоритм множення багаторозрядних чисел на основі циклічної згортки;

удосконалено метод Пітассі:

а) для обчислення згортки розрядністю , -непарне, за рахунок оригінального представлення згортки розрядністю , -непарне, двома згортками меншої розрядності замість трьох згорток (розширення діапазону довжин циклічних згорток, в якому існують ефективні алгоритми їх обчислення);

б) для обчислення циклічної згортки розрядністю на основі алгоритму швидкого перетворення Уолша за рахунок введення корегуючого вектора (зменшення складності на 17%);

удосконалено діагональний метод множення багаторозрядних чисел за рахунок використання рекурентних співвідношень (швидкодія прискорена на 25%);

покращено метод Шенхаге - Штрассена для множення чисел розрядністю з використанням оригінальної модифікації швидкого перетворення Фур'є за рахунок використання матриці коефіцієнтів перетворення Фур'є () меншого розміру та формул переходу між дискретними перетвореннями Фур'є (ДПФ) розрядністю та (прискорення швидкодії удвічі);

вперше запропоновано оригінальний метод множення багаторозрядних чисел, який повністю виключає використання операції множення;

розроблена нова оригінальна реалізація алгоритму Монтгомері для обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня, яка базується на використанні двох класів лишків;

вперше запропоновано метод обчислення квадратного та кубічного коренів від багаторозрядних чисел, який не використовує операції множення і ділення.

Практичне значення отриманих результатів. Отримані в дисертаційній роботі результати досліджень можуть використовуватися для підвищення продуктивності систем двоключової криптографії, високоточних обчислень, цифрової обробки сигналів. Вони можуть бути основою для розробки нових методів реалізації багаторозрядних операцій.

На основі запропонованих алгоритмів та методів було розроблено програмне забезпечення, яке впроваджено в Публічному акціонерному товаристві “Дочірній банк Ощадбанк Росії”.

Результати роботи були використані в НДР “Кристал”.

Особистий внесок здобувача. Основні результати дисертації отримані автором самостійно. У працях, опублікованих у співавторстві, автору належать наступні результати: [1] - використання ідеї “розщеплення” Карацуби - Офмана та рекурентних співвідношень для діагонального методу, доведення діагонального модифікованого методу в загальному вигляді, отриманні оцінки складності; [2, 10] - автором запропонована модифікація алгоритму обчислення ДПФ, направлена на оптимізацію за швидкодією за рахунок використання резервів оптимізації: зменшення розміру матриці коефіцієнтів перетворення Фур'є () удвічі в порівнянні з методом В.К. Задіраки, попарне розміщення елементів дійсної та комплексної частин коефіцієнтів ДПФ, реалізація бітової інверсії на мові програмування низького рівня, використання динамічного розподілу пам'яті, оптимізація обчислення згортки за рахунок зменшення її розрядності втричі; [9] - автором запропоновано введення корегуючого вектора, алгоритм обчислення циклічної згортки з використанням швидкого перетворення Уолша (ШПУ); [11] - запропоновано метод реалізації операції багаторозрядного множення з використанням матриці передобчислень без використання операції однослівного множення.

Апробація результатів дисертації. Основні результати дисертаційного дослідження доповідалися та обговорювалися на ІІІ Всеукраїнській науково-практичній конференції “Технології безпеки інформації” (КПІ, 2005); міжнародній конференції “Питання оптимізації обчислень (ПОО-XXXII)” (Кацивелі, Крим, 19-23 вересня 2005); VII Міжнародній науково-технічній конференції “Штучний інтелект. Інтелектуальні системи - 2006” (Кацивелі, Крим, 24-29 вересня 2006); міжнародній конференції “Питання оптимізації обчислень (ПОО-XXXV)” (Кацивелі, Крим, 22-29 вересня 2009); на семінарах “Обчислювальна математика” при науковій раді “Кібернетика” НАН України (керівник доктор фізико-математичних наук, професор, член-кореспондент НАН України В.К. Задірака).

Публікації. За матеріалами дисертації опубліковано 11 робіт. З них 9 - у фахових виданнях ВАК України (з яких одноосібних 6), 2 - у матеріалах конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, чотирьох розділів, висновків, переліку використаних джерел та додатків. Загальний обсяг дисертації 172 сторінки, у тому числі 15 додатків на 43 сторінках, 19 рисунків, 23 таблиці, список використаних джерел містить 92 найменувань і розташований на 8 сторінках.

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

У вступі обґрунтовано актуальність теми дисертації, сформульовано мету й основні задачі дослідження, визначено об'єкт, предмет і методи досліджень, визначено наукову новизну та практичне значення отриманих результатів, особистий внесок автора в роботи, виконані у співавторстві, апробацію результатів дисертації та кількість публікацій за темою дисертації.

Перший розділ. Дано огляд існуючих методів та алгоритмів обчислення циклічної згортки, багаторозрядного множення однакової та кратної довжини, багаторозрядного лишку, модулярного багаторозрядного множення. Проаналізована обчислювальна складність алгоритмів.

Підрозділ 1.1 присвячений огляду відомого методу Пітассі обчислення циклічної згортки. Метод, узагальнений Девісом, обчислює циклічні згортки розрядністю та потребує обчислення трьох згорток меншої розрядності на всіх ітераціях.

Лема 1.1. Вхідні та вихідні послідовності згортки , , пов'язані співвідношеннями:

,

,(1)

де , , - оператори ( (парний), (непарний), (угору)): , , ; , , .

Співвідношення (1) представляють собою ітераційний метод Пітассі обчислення згорток довжиною , використовуючи розбиття на згортки половинної довжини . На кожній ітерації кількість згорток половинної довжини збільшується у три рази. Ітерації продовжуються до згорток довжиною 2. Якщо довжина початкової згортки, то буде згорток довжиною 2, для обчислення кожної з яких необхідно два множення. Відповідно загальна кількість множень складає . Якщо розбиття згортки відбувається до згортки довжиною 4 (для обчислення якої необхідно п'ять множень), то загальна кількість множень складає .

Підрозділ 1.2 присвячений аналізу алгоритмів та програм багаторозрядного множення. Відомо, що стандартний алгоритм множення вимагає операцій для множення двох -розрядних чисел. Більш якісні алгоритми можна отримати, використовуючи ідею Карацуби - Офмана та її рекурентного застосування, а також швидкі дискретні ортогональні перетворення. Серед найбільш швидких алгоритмів множення великих чисел можна виділити алгоритм Карацуби - Офмана, що вимагає порядку операцій, та алгоритм Шенхаге - Штрассена, що вимагає порядку операцій. Істотного зменшення часу виконання операції множення можна також досягти, використовуючи і розробляючи швидкі алгоритми обчислення арифметичної згортки на основі не тільки швидкого перетворення Фур'є (ШПФ), але й інших швидких лінійних дискретних перетворень, наприклад, Уолша і Хаара.

Реалізація прямокутної схеми стандартного алгоритму множення при множенні -розрядних чисел вимагає звертань до пам'яті комп'ютера. Цю кількість можна зменшити до , якщо підсумовувати кожну діагональ на регістрах, а потім записувати в пам'ять. Реалізація такої схеми множення називається діагональною, яка є найефективнішою для довжин чисел до 96 розрядів.

Одна з процедур, що дозволяє зменшити загальну кількість однослівних множень, запропонована Карацубою і Офманом. Вони запропоновували представляти цілі числа і , кожне з яких розташоване в -бітових словах, у вигляді:

, ,

де оператори , та , дають старші та молодші частини , відповідно. Якщо позначити , то множення можна записати у вигляді:

.

Ця формула дає можливість звести задачу множення -розрядних чисел до трьох множень -розрядних чисел. Використовуючи “розщеплення” за цією формулою рекурсивно, можна зменшити час виконання операції множення з величини порядку до величини порядку . Оптимізацію алгоритму Карацуби - Офмана за рахунок рекурсивного використання формули називають “розщепленням”, а оптимізацію за рахунок побудови ефективної за часом виконання програми - “розшивкою”.

Метод множення багаторозрядних чисел з використанням ШПФ був запропонований Ф. Штрассеном у 1972 р. Він заснований на ідеї використання теореми про дискретну згортку двох функцій для множення великих чисел, оскільки добуток багаторозрядних чисел є дискретною циклічною згорткою коефіцієнтів багаточленів.

Показано, що множення двох -розрядних чисел може здійснюватися зі складністю порядку операцій. Але константа в цій оцінці виявилася дуже великою, і перевага даного алгоритму в порівнянні з алгоритмом Карацуби - Офмана починає виявлятися для чисел, довжина яких перевищує 3072 байтів.

Задіракою В.К. був розвинутий підхід Шенхаге - Штрассена для швидкого множення в частині використання для його реалізації оригінальної модифікації алгоритму ШПФ із попередньою заготівлею елементів матриці перетворення. Тоді апріорні оцінки кількості операцій дійсного множення і додавання мають вигляд: , , де - кількість блоків, , - кількість операцій множення, додавання і віднімання.

Підрозділ 1.3 присвячений огляду відомих алгоритмів обчислення лишку та модулярного множення.

Основне обчислювальне навантаження лягає на виконання модулярних операцій над великими числами. При обчисленні лишку від добутку спочатку обчислюється добуток або . Далі використовується алгоритм ділення для обчислення лишку. Ділення є найбільш складною з основних арифметичних операцій над багаторозрядними числами. Перш за все воно має частку та лишок. Однак нас не цікавить частка, нам потрібен лише лишок. Отже, для прискорення процесу обчислення кроки алгоритму можуть бути дещо спрощені. Крок отримання лишку може виконуватись одним з добре відомих алгоритмів ділення з відновленням і без відновлення.

Алгоритм ділення без відновлення припускає від'ємний лишок. Для того, щоб відкоректувати лишок, під час виконання наступного циклу виконується або віднімання, або додавання, в залежності від того додатний знак лишку чи від'ємний.

Алгоритм Баретта обчислення лишку базується на рівності:

,

де , означає найближче багаторозрядне ціле число менше за .

У 1985 році П. Монтгомері (P. Montgomery) запропонував ефективний алгоритм обчислення , де , , , - бітові двійкові цілі числа. Цей алгоритм особливо зручний при застосуванні на комп'ютерах (сигнальних процесорах або мікропроцесорах), які здатні швидко виконувати арифметичні дії за модулем степені двійки. Особливістю алгоритму Монтгомері є те, що цей алгоритм дозволяє обчислити лишок без виконання ділення на . Алгоритм Монтгомері вимагає, щоб і були взаємно простими числами.

Алгоритми Баретта та Монтгомері вимагають попередніх передобчислень. Найбільший обсяг додаткових обчислень виконується в алгоритмі Монтгомері (див. табл. 1). Тому його застосування виправдовується лише при великій кількості виконання модулярної редукції або при реалізації операції піднесення до степеня. Для одноразового використання краще користуватися класичним методом. Алгоритм Баретта не набагато кращий за класичний алгоритм.

Таблиця 1

Складність алгоритмів знаходження лишку

Операція	Алгоритм
	Стандартний	Монтгомері	Баретта
Множення
Ділення		0	0
“Передобчислення”	Нормалізація
Перетворення аргументів	Немає	- дільник	Немає
“Післяобчислення”	Денормалізація	Редукція Монтгомері	Немає
Обмеження	Немає	, НСД

- нульовий розряд (),.

Другий розділ. Пропонується новий метод використання циклічної згортки для реалізації багаторозрядної операції множення. Багато уваги приділено двом різним підходам по удосконаленню методу Пітассі - Девіса обчислення циклічної згортки.

У підрозділі 2.1 показано, що багаторозрядна операція множення рівнозначна задачі обчислення циклічної згортки. Якщо багаторозрядні множники представити в спеціальному вигляді та використовувати як вхідні сигнали в циклічній згортці, то обчислення збігається з стандартним методом множення в стовпчик.

У роботі наведено новий алгоритм реалізації операції множення з використанням циклічної згортки.

У підрозділі 2.2 розглядається удосконалення методу Пітассі - Девіса. Пропонується метод обчислення згортки розрядністю , -непарне, що розширює діапазон розрядностей, в якому існують ефективні методи обчислення циклічної згортки (див. табл. 2). Для згорток такої розрядності показано, що достатньо обчислити дві згортки розрядністю на останній ітерації, на відміну від методу Пітассі - Девіса, в якому на кожній ітерації необхідно обчислювати три згортки. Використовується наступна властивість непарної розрядності: результат непарного циклічного зсуву в один бік дорівнює парному зсуву в інший бік.

Лема 2.1. Циклічна згортка має властивості: , , , де , - оператори ( (угору), (до низу)): , , ; , , .

У загальному вигляді пропонуються формули обчислення згортки розрядністю , , -непарне, :

де , , - оператори ( (парний), (непарний), (угору)): , , ; , , .

Таблиця 2

Кількість операцій множення при обчисленні згортки

розрядністю , ,

	Кількість операцій множення для обчислення згортки розрядністю	Розрядність згортки ,	Кількість операцій множення при обчисленні згортки розрядністю ,
3	4
5	10
7	16
9	19

У підрозділі 2.3 пропонується алгоритм обчислення циклічної згортки за допомогою використання ШПУ. Основою наведеного алгоритму є метод Пітассі (1), в якому пропонується використання додаткового (корегуючого) вектора, що дозволяє зменшити (на 17%) довжину відповідних послідовностей та обчислювальну складність щодо операцій однослівного додавання, віднімання та множення.

Запропонований метод проілюстровано на прикладі обчислення згортки довжиною з використанням ШПУ. При цьому достатньо виконати 5 операцій множення.

, , ; , ;

, .

Для обчислення згортки необхідно обчислювати корегуючий елемент . При збільшенні розрядності згортки збільшується кількість корегуючих елементів. Пропонується всі корегуючі елементи представити у вигляді корегуючого вектора і пропонується простий спосіб знаходження такого вектора.

Введені додаткові оператори , , ( (Уолш), (додавання), (віднімання)). Оператор представляє собою 1-й крок у перетворенні Уолша.

Теорема 2.1. Для обчислення згортки довжиною з використанням алгоритму ШПУ необхідно однослівних множень.

Лема 2.2. Кількість операцій додавання і віднімання для обчислення ШПУ вектора оцінюється виразом: , .

Оцінка кількості операцій додавання і віднімання для обчислення ШПУ в основних секціях має вигляд , .

Лема 2.3. Загальна кількість операцій додавання і віднімання запропонованого алгоритму обчислення згортки розрядністю на основі ШПУ визначається нерівністю .

Теорема 2.2. Оцінка кількості обчислювальних витрат, необхідних для обчислення згортки розрядністю за допомогою запропонованого алгоритму на основі ШПУ, має вигляд , де - загальна кількість операцій додавання та віднімання, - загальна кількість операцій множення.

Оцінки кількості операцій для обчислення швидкого перетворення Фур'є: , , .

Коефіцієнти прискорення , , ( - агрегований коефіцієнт) щодо операцій дійсного множення, додавання і віднімання для запропонованого алгоритму в порівнянні з алгоритмом на основі ШПФ мають вигляд:

, , ,

де , , - час виконання операції над цілими числами і з плаваючою комою відповідно ( для комп'ютера Celeron 1GHz). Далі в табл. 3 наведені , , для різних .

Таблиця 3

Порівняльний аналіз агрегованого коефіцієнта прискорення запропонованого алгоритму з алгоритмом на основі ШПФ

	5	6	7	8	9	10	11	12	13	14
	0.04	0.05	0.06	0.08	0.11	0.14	0.19	0.27	0.37	0.51
	0.24	0.34	0.48	0.69	1.00	1.46	2.14	3.14	4.64	6.87
	0.16	0.22	0.31	0.45	0.64	0.93	1.36	1.99	2.93	4.33

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

Третій розділ. Розглядається багаторозрядна операція множення.

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

Для удосконалення діагонального методу пропонується метод, який є комбінацією діагонального методу та методу Карацуби - Офмана з одним рівнем рекурсії (“розщеплення”):

. (2)

Зазначимо, що при (при множенні двослівних чисел) (2) збігається з формулою Карацуби - Офмана.

.

Теорема 3.1. Апріорна оцінка складності виконання операції множення

-розрядних чисел за формулою (2) має вигляд:

, , ,

де - кількість однослівних операцій множення, - кількість двослівних операцій додавання, - кількість однослівних операцій віднімання.

Якщо дорівнює сумі всіх , для яких степінь дорівнює , то перший доданок у (2) можна представити у вигляді , де коефіцієнти можна виразити рекурентними співвідношеннями:

; , ; , ; .(3)

Теорема 3.2. Апріорна оцінка складності виконання операції множення

-розрядних чисел при використанні удосконаленої модифікації діагонального методу (2) має вигляд

, , ,

де - кількість однослівних операцій множення, - кількість двослівних операцій додавання, - кількість однослівних і двослівних операцій віднімання.

З урахуванням (3) пропонується наступна формула:

.

Порівняльний аналіз за швидкодією модифікації діагонального методу в порівнянні з діагональним методом для різних процесорів наведено в табл. 4.

Таблиця 4

Коефіцієнти прискорення модифікації діагонального методу в порівнянні з діагональним методом

	166МГц	400Мгц
64	0.45	0.8016
128	0.78	0.7082
256	0.74	0.6737
512	0.77	0.6398
1024	0.74	0.6317

У підрозділі 3.2 пропонується оригінальна модифікація ШПФ з метою подальшої оптимізації за швидкодією алгоритму Шенхаге - Штрассена.

Теорема 3.3. Апріорна оцінка обчислювальних витрат, необхідних для реалізації запропонованої модифікації Шенхаге - Штрассена, має вигляд: , , де - кількість блоків.

При удосконаленні алгоритму використовувалися резерви оптимізації.

1. При обчисленні ДПФ дійсного сигналу використовується надлишок даних.

Розглянуто властивості ДПФ дійсних сигналів та їх взаємозв'язок.

Лема 3.1. Якщо та , - дійсний сигнал та його ДПФ, то , .

Лема 3.2. Якщо та , - дійсний сигнал та його ДПФ, то - дійсне число.

Лема 3.6. Якщо , та , , - дійсні сигнали та їх ДПФ, то сигнал , , має властивість: , .

Розглянуто взаємозв'язок ДПФ розрядностей та .

Лема 3. 3. Якщо , - дійсний сигнал, то ДПФ , сигналів (, ), , та , , мають властивість: .

Лема 3.4 (формули розпакування). Якщо , - дійсний сигнал, то ДПФ , сигналів , , та (, ), , пов'язані співвідношеннями:

, ; ,

, .

Лема 3.5 (формули пакування). Якщо , - дійсний сигнал, то ДПФ , сигналів (, ), , та , , пов'язані співвідношеннями:

, , ;

, ;

, .

2. Матриця коефіцієнтів перетворення Фур'є, елементами якої є передобчисленні синуси та косинуси, зменшена в два рази за рахунок використання взаємозв'язку між значеннями синусів та косинусів матриці: , , , де - розрядність згортки.

3. При обчисленні ДПФ необхідно виконувати операції з плаваючою комою на співпроцесорі. У базовому методі вхідна послідовність розбивається на блоки довжиною 8 біт (один байт). Пропонується розбивати послідовність на блоки довжиною 24 біти (три байти), що дає можливість максимально використовувати 63-бітну мантису співпроцесора та зменшити кількість операцій за рахунок зменшення довжини згортки у три рази. Використання 64-бітних процесорів, у яких співпроцесор має 127-бітну мантису, дасть змогу розбивати послідовність на блоки довжиною 56 бітів (7 байтів) та обчислювати операції множення з 1024-бітними числами, використовуючи лише 32-розрядну дискретну згортку (7·8·32=1792>1024).

4. Перегрупування оброблюваних даних за рахунок попарного розміщення елементів дійсної та комплексної частин коефіцієнтів ДПФ покращує швидкодію методу за рахунок збільшення операцій послідовного доступу (прискорення на 11%).

5. Використання динамічного розподілу пам'яті дає можливість робити обчислення великих множників до 6144 байт та прискорити час на 20%.

У роботі наведено алгоритм реалізації операції множення двох _розрядних чисел з обчисленням тільки -розрядних ДПФ. Коефіцієнти прискорення для різних наведено у табл. 5.

Таблиця 5

Порівняльний аналіз за швидкодією запропонованого методу

зі стандартним методом

Байт	Час обчислення, с	Коефіцієнт прискорення
384	14,06	5,687	2,472
768	7,17	3,70	1,938
1536	3,77	1,78	2,118
3072	2,054	0,97	2,118

Апріорний коефіцієнт прискорення:

, .

Порівняльний аналіз алгоритму Шенхаге - Штрассена за часом (сек) з базовим алгоритмом множення до здійсненої оптимізації 166МГц 400Мгц 512 16 8.2 1024 10 4.4 2048 5.5 2.3 4096 3 1.4 8192 1.7 0.75 16384 0.99 0.42 32768 0.56 0.23	Порівняльний аналіз алгоритму Шенхаге - Штрассена за часом (сек) з базовим алгоритмом множення після здійсненої оптимізації 166МГц 400Мгц 768 4.5 4.4 1536 2.4 2.5 3072 1.6 1.4 6144 1.01 0.8 12288 0.7 0.4 24576 0.4 0.23 49115 0.23 0.13 98230 0.14 0.07

У підрозділі 3.3 пропонується оригінальний метод множення великих цілих чисел, причому множення не використовується взагалі, а обчислювальний процес ґрунтується тільки на додаванні. Цей метод ефективний при великих . Ймовірність появи цифри від 0 до 9 у кожному розряді приблизно дорівнює 10%. Для обчислення результату множення використовується матриця передобчислень з дев'яти елементів. Кожен елемент матриці передобчислень дорівнює першому множнику, помноженому на порядковий номер у матриці передобчислень.

Для комп'ютера зручніше використовувати 16-річну систему числення, тому байт краще представити у вигляді двох 16-річних цифр (старшого і молодшого розрядів). Тоді матриця буде мати 15 елементів і процедуру обчислення добутку можна розбити на два етапи.

Оцінка загальної кількості необхідних обчислювальних витрат має вигляд: . Для процесорів типу Celeron, коефіцієнт . Тоді .

На повільних комп'ютерах найкращою буде модифікація, при якій використовується одночасно дві матриці передобчислень для старшого і молодшого розрядів кожного байта числа. При збільшенні потужності комп'ютера найкращою виявляється модифікація, при якій -й елемент матриці передобчислень послідовно додається до результату у відповідності з розрядами, значеннями яких є , перед тим як перейти до наступного елемента матриці передобчислень.

Четвертий розділ. Розглядається алгоритм Монтгомері, що використовується для обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня. Пропонується нова реалізація алгоритму Монтгомері. У реалізації використовуються два класи лишків, що дозволяє використовувати китайську теорему про лишки. Обчислення відбуваються одночасно у двох класах лишків.

Показано, що в алгоритмі Монтгомері задачу знаходження лишку множення двох -розрядних чисел за -розрядним модулем можна звести до знаходження лишку однослівних множень за однослівним модулем, який не є степенем двійки.

Лема 4.2. Якщо модуль такий, що , , і відомі числа такі, що , , , , то для будь-якого числа мають місце наступні співвідношення:

, , , де , .

Теорема 4.1 (перехід з одного класу лишків до іншого). Нехай задано два класи лишків з модулями і такими, що , , , і число має наступні лишки: , . Тоді для складності алгоритму представлення числа в класі лишків з модулем , де , мають місце оцінки: , , , , де , , - кількість однослівних операцій множення, ділення і віднімання, - кількість операцій обчислення однослівного модуля.

Теорема 4.2. При модулярному множенні -розрядних чисел та з використанням двох класів лишків кількість операцій можна представити наступними апріорними оцінками: , , , , де , , - кількість однослівних операцій множення, ділення, додавання і віднімання, - кількість операцій обчислення однослівного модуля.

ВИСНОВКИ

У дисертаційній роботі у відповідності з поставленою метою вирішена задача підвищення швидкодії операцій багаторозрядної арифметики, які використовуються при розв'язанні задач двоключової криптографії, високоточних обчислень, цифрової обробки сигналів та інших задач дискретної, прикладної та обчислювальної математики.

Основні результати виконання дисертаційної роботи:

1. Вперше запропоновано алгоритм множення багаторозрядних чисел на основі циклічної згортки.

2. Удосконалено метод Пітассі:

а) для обчислення згорток розрядністю , -непарне, за рахунок оригінального представлення початкової згортки двома згортками меншої розрядності. Проведено аналіз складності та показано, що удосконалення розширює діапазон використання методу Пітассі для ефективного обчислення згорток розрядністю , -непарне;

б) для обчислення циклічних згорток розрядністю на основі використання алгоритму швидкого перетворення Уолша за рахунок введення корегуючого вектора. Проведено аналіз складності запропонованого алгоритму множення. Встановлено, що кількість операцій однослівного множення становить , а кількість операцій однослівного додавання та віднімання - відповідно.

3. Запропонована модифікація діагонального методу множення багаторозрядних чисел, який є ефективним у діапазоні довжин чисел до 96 розрядів для одного числа, за рахунок використання рекурентних співвідношень, що зменшує кількість однослівних операцій множення в два рази. Теоретично обґрунтовано використання запропонованого методу для множення багаторозрядних чисел кратної довжини, що значно зменшує обчислювальну складність для такого класу задач.

4. Покращено метод Шенхаге - Штрассена для множення чисел розрядністю з використанням оригінальної модифікації швидкого перетворення Фур'є за рахунок резервів оптимізації: матриці коефіцієнтів перетворення Фур'є () меншого розміру та формул переходу між ДПФ розрядністю та . Отримана апріорна оцінка складності алгоритму. Практична реалізація запропонованого алгоритму та подальший порівняльний аналіз підтвердили прискорення обчислень більше ніж у два рази.

5. Вперше запропоновано оригінальний метод множення багаторозрядних чисел, який оснований тільки на додаванні та передобчисленнях.

6. Розроблена нова оригінальна реалізація алгоритму Монтгомері для обчислення багаторозрядного лишку, модулярного багаторозрядного множення та піднесення до степеня, який полягає у використанні двох додатково введених класів лишків, що дозволяє звести складність задачі обчислення багаторозрядного лишку до складності задачі переходу з одного класу лишків до іншого з використанням передобчислень.

7. Вперше запропоновано метод обчислення квадратного та кубічного коренів від багаторозрядних чисел, який не використовує операції множення і ділення.

ОСНОВНІ ПОЛОЖЕННЯ ДИСЕРТАЦІЇ ОПУБЛІКОВАНІ В ТАКИХ ПРАЦЯХ

Задирака В.К. Оптимизация алгоритмов быстрого умножения больших чисел. І / В.К. Задирака, С.С. Мельникова, А.Н. Терещенко // Управляющие системы и машины. - 2006. - № 3. - С. 13-21.

Задирака В.К. Оптимизация алгоритмов быстрого умножения больших чисел. ІІ / В.К. Задирака, С.С. Мельникова, А.Н. Терещенко // Управляющие системы и машины. - 2006. - № 4. - С. 23-32.

Терещенко А.Н. Быстрое умножение N-, 2N- и XN-словных чисел на N_словное число с использованием идеи Карацубы - Офмана / А.Н. Терещенко // Компьютерная математика. - 2006. - № 2. - С. 83-92.

Терещенко А.Н. Оценка сложности вычисления рекуррентных соотношений в модифицированном диагональном методе / А.Н. Терещенко // Компьютерная математика. - 2006. - № 3. - С. 110-120.

Терещенко А.Н. Быстрое вычисление квадратного и кубического корней без использования операций умножения и деления / А.Н. Терещенко // Искусственный интеллект. - 2006. - № 3. - С. 783-792.

Терещенко А.Н. Умножение больших N-разрядных чисел с вычислением только N-разрядных ДПФ / А.Н. Терещенко // Компьютерная математика. - 2008. - № 1. - С. 122-130.

Терещенко А.Н. Оптимизация метода Питасси вычисления свертки / А.Н. Терещенко // Искусственный интеллект. - 2009. - № 1 - С. 204-212.

Терещенко А.Н. Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю / А.Н. Терещенко // Компьютерная математика. - 2010. - № 1. - С. 73-82.

Терещенко А.Н. Реализация операции умножения с использованием преобразования Уолша / А.Н. Терещенко, С.С. Мельникова, Л.А. Гнатив, В.К. Задирака, Н.В. Кошкина // Международный научно-технический журнал Проблемы управления и информатики. - 2010. - № 2. - С. 102-126.

Задірака В.К. Про асимптотичну ефективність алгоритму Шенхаге - Штрассена / В.К. Задірака, С.С. Мельникова, А.М. Терещенко // Питання оптимізації обчислень (ПОО-XXXII): Міжнар. конференція, присвячена пам'яті академіка В.С. Михалевича, 19-23 вересня 2005 р.: праці міжнар. конференції. - Київ, 2005. - C. 82-83.

Задірака В.К. Множення без множення / В.К. Задірака, А.М. Терещенко // Питання оптимізації обчислень (ПОО-XXXII): Міжнар. конференція, присвячена пам'яті академіка В.С. Михалевича, 19-23 вересня 2005 р.: праці міжнар. конференції. - Київ, 2005. - C. 86-87.

АНОТАЦІЇ

Терещенко А.М. Ефективні за швидкодією алгоритми багаторозрядної арифметики. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.01 - теоретичні основи інформатики та кібернетики. - Інститут кібернетики імені В.М. Глушкова НАН України, Київ, 2010.

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

Удосконалено метод Пітассі для обчислення циклічних згорток розрядністю , -непарне, шляхом розбиття на дві згортки меншої довжини. Покращений метод Пітассі для обчислення згорток розрядністю з використанням ШПУ за рахунок введення корегуючого вектора. Запропоновано новий алгоритм реалізації багаторозрядної операції множення на основі циклічної згортки. Удосконалено діагональний метод багаторозрядного множення, використовуючи ідею Карацуби - Офмана та рекурентні співвідношення. Удосконалено алгоритм ШПФ. Удосконалено метод Шенхаге - Штрассена множення багаторозрядних чисел з використанням ШПФ за рахунок використання меншої матриці коефіцієнтів перетворення Фур'є () та формул переходу між ДПФ розрядністю та . Пропонується нова реалізація операції множення без використання операції однослівного множення з використанням тільки однослівних додавань. Розглянута нова реалізація алгоритму Монтгомері обчислення лишку за рахунок одночасного обчислення у двох класах лишків. У додатках наведені нові алгоритми обчислення квадратного та кубічного коренів від багаторозрядних чисел.

Ключові слова: багаторозрядна арифметика, циклічна згортка, багаторозрядне множення, модулярне множення, швидке перетворення Фур'є, швидке перетворення Уолша, складність обчислень.

Терещенко А.Н. Эффективные по быстродействию алгоритмы многоразрядной арифметики. - Рукопись.

Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 01.05.01 - теоретические основы информатики и кибернетики. - Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2010.

Диссертационная работа посвящена оптимизации по быстродействию алгоритмов выполнения операций с многоразрядными числами за счет уменьшения количества операций однословного умножения, сложения и вычитания.

В первом разделе диссертации рассмотрены и проанализированы алгоритмы и методы, которые используются для эффективной реализации операций многоразрядной арифметики. Рассмотрен метод Питасси - Девиса для вычисления циклической свертки путем ее разбиения на свертки половинной длины. Проанализированы методы реализации операции многоразрядного умножения, вычисления многоразрядного остатка, а также диапазоны длин многоразрядных чисел, в которых эти методы наиболее эффективны.

Во втором разделе показано, что циклическая свертка является связующим звеном при использовании быстрых ортогональных преобразований для реализации операции многоразрядного умножения. В этом разделе впервые предложен метод реализации операции умножения с использованием циклической свертки. Показано, что если к многоразрядным множителям добавить старшие нули и взять второй множитель в обратном порядке, то вычисление циклической свертки полностью совпадает с вычислением стандартного умножения в столбик, за исключением того, что результат циклической свертки будет в обратном порядке. Предложена модификация метода Питасси для вычисления циклических сверток длиной , _нечетное, что расширяет диапазон сверток, для которых существуют эффективные алгоритмы их вычисления. Предложена модификация метода Питасси для вычисления циклических сверток длиной с использованием быстрого преобразования Уолша (БПУ) за счет введения корректирующего вектора, что значительно уменьшает сложность по количеству операций однословного умножения, сложения и вычитания.

В третьем разделе рассмотрены операции умножения. Предложена модификация диагонального метода, который является самым эффективным в диапазоне длин чисел до 96 разрядов для одного числа, с использованием идеи Карацубы - Офмана и рекуррентных соотношений, что позволило уменьшить количество операций однословного умножения в два раза. Предложена оригинальная модификация алгоритма быстрого преобразования Фурье (БПФ) за счет использования матрицы коэффициентов преобразования Фурье () меньшего размера и других резервов оптимизации вычислений. Улучшен метод Шенхаге - Штрассена умножения больших чисел на основе быстрого преобразованиям Фурье (БПФ) за счет использования формул перехода между дискретными преобразованиями Фурье (ДПФ) разрядностью и . Данная модификация позволила ускорить метод более чем в два раза. Предложен новый метод многоразрядного умножения, который основан на матрице предвычислений и исключает использование операции однословного умножения.

В четвертом разделе рассмотрена новая оригинальная реализации алгоритма Монтгомери для вычисления многоразрядного остатка, модулярного многоразрядного умножения и возведения в степень за счет использования двух классов остатков.

Для всех предложенных методов получены априорные и апостериорные оценки сложности для определения области их эффективного использования. Для проверки теоретических результатов проведены численные эксперименты. Разработаны программы и проведен сравнительный анализ по быстродействию с существующими алгоритмами.

В приложениях приведены новые алгоритмы вычисления многоразрядных квадратного и кубического корней.

Ключевые слова: многоразрядная арифметика, циклическая свертка, многоразрядное умножение, модулярное умножение, быстрое преобразование Фурье, быстрое преобразование Уолша, сложность вычислений.

Tereshchenko A. The fast proceeding algorithms of multidigits arithmetic. - Manuscript.

The thesis is for obtaining of scientific degree of Candidate of Physical and Mathematical Sciences on a speciality 01.05.01 - Theoretical base of informatics and cybernetics. - V.M. Glushkov Institute of cybernetics of National Academy of Sciences of Ukraine, Kiev, 2010.

Thesis is dedicated to an optimization of the processing speed of multidigits calculation algorithms at the expenses of the reducing of single precision multiplication, addition and subtraction operations number.

The method Pitassi of the calculation of the cyclic convolutions of two series each of length , where is odd, has been improved at the expenses of the calculating only two auxiliary half-length convolutions. The method Pitassi of the calculation of the cyclic convolutions of two series each of length with using fast Walsh transform (FWT) has been improved with introducing the corrective vector.

The new algorithm of the realization of multidigits multiplication based on cyclic convolution is suggested. The modification of diagonal multidigits multiplication with using Karatsuba - Ofman idea and recurrent terms is suggested. The fast Fourier transform (FFT) algorithm has been improved. The Schonhage - Strassen multiplication method used FFT has been improved in computation two times. The new algorithm of the multidigits multiplication without using single precision multiplications and with using additions and precomputation table is suggested.

The new modular multiplication realization of Montgomery multiplication is developed. In new realization the calculation is proceeded in two complex modulus simultaneously.

The new algorithms of square and cubic roots calculation are given in appendixes.

Key words: multidigits arithmetic, cyclic convolution, multidigits multiplication, modular multiplication, FFT, FWT, complexity estimation.

Размещено на Allbest.ru

...