Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації

Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації

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

Повний опис

Збережено в:
Бібліографічні деталі
Опубліковано в: :Реєстрація, зберігання і обробка даних
Дата:2004
Автори: Богданов, О.М., Зінченко, Я.В.
Формат: Стаття
Мова:Ukrainian
Опубліковано: Інститут проблем реєстрації інформації НАН України 2004
Теми:
Методи захисту інформації в комп’ютерних системах і мережах
Онлайн доступ:https://nasplib.isofts.kiev.ua/handle/123456789/50708
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації / О.М. Богданов, Я.В. Зінченко // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 94-106. — Бібліогр.: 11 назв. — укр.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine
id nasplib_isofts_kiev_ua-123456789-50708
record_format dspace
spelling Богданов, О.М.
Зінченко, Я.В.
2013-10-28T19:41:56Z
2013-10-28T19:41:56Z
2004
Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації / О.М. Богданов, Я.В. Зінченко // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 94-106. — Бібліогр.: 11 назв. — укр.
1560-9189
https://nasplib.isofts.kiev.ua/handle/123456789/50708
519.6:519.712.3:510.52
Для підвищення швидкодії асиметричних криптографічних систем розроблено методи зменшення часу реалізації операції множення надвеликих чисел. Указані методи базуються на застосуванні математичного апарату вейвлет-перетворень і, в порівнянні з відомими методами, дозволяють суттєво зменшити обчислювальну складність операції множення багаторозрядних чисел.
Для повышения быстродействия асимметричных криптографических систем разработаны методы уменьшения времени реализации операции умножения сверхбольших чисел. Указанные методы базируются на применении математического аппарата вейвлет-преобразований и, по сравнению с известными методами, позволяют существенно уменьшить вычислительную сложность операции умножения многоразрядных чисел.
For increasing speed of asymmetric cryptographic systems methods of the reduction of time for realizing multiplication operation of long numbers are developed. These methods are founded on using mathematical transformations (wavelet-transformations).They greatly reduce the computing difficulty of multiplication operation of long numbers.
uk
Інститут проблем реєстрації інформації НАН України
Реєстрація, зберігання і обробка даних
Методи захисту інформації в комп’ютерних системах і мережах
Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
Методы уменьшения времени реализации операции умножения сверхбольших чисел для систем защиты информации
Methods of the Reduction of Time for Realizing Multiplication Operation of Long Numbers for Information Protection Systems
Article
published earlier
institution Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection DSpace DC
title Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
spellingShingle Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
Богданов, О.М.
Зінченко, Я.В.
Методи захисту інформації в комп’ютерних системах і мережах
title_short Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
title_full Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
title_fullStr Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
title_full_unstemmed Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
title_sort методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації
author Богданов, О.М.
Зінченко, Я.В.
author_facet Богданов, О.М.
Зінченко, Я.В.
topic Методи захисту інформації в комп’ютерних системах і мережах
topic_facet Методи захисту інформації в комп’ютерних системах і мережах
publishDate 2004
language Ukrainian
container_title Реєстрація, зберігання і обробка даних
publisher Інститут проблем реєстрації інформації НАН України
format Article
title_alt Методы уменьшения времени реализации операции умножения сверхбольших чисел для систем защиты информации
Methods of the Reduction of Time for Realizing Multiplication Operation of Long Numbers for Information Protection Systems
description Для підвищення швидкодії асиметричних криптографічних систем розроблено методи зменшення часу реалізації операції множення надвеликих чисел. Указані методи базуються на застосуванні математичного апарату вейвлет-перетворень і, в порівнянні з відомими методами, дозволяють суттєво зменшити обчислювальну складність операції множення багаторозрядних чисел. Для повышения быстродействия асимметричных криптографических систем разработаны методы уменьшения времени реализации операции умножения сверхбольших чисел. Указанные методы базируются на применении математического аппарата вейвлет-преобразований и, по сравнению с известными методами, позволяют существенно уменьшить вычислительную сложность операции умножения многоразрядных чисел. For increasing speed of asymmetric cryptographic systems methods of the reduction of time for realizing multiplication operation of long numbers are developed. These methods are founded on using mathematical transformations (wavelet-transformations).They greatly reduce the computing difficulty of multiplication operation of long numbers.
issn 1560-9189
url https://nasplib.isofts.kiev.ua/handle/123456789/50708
citation_txt Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації / О.М. Богданов, Я.В. Зінченко // Реєстрація, зберігання і оброб. даних. — 2004. — Т. 6, № 1. — С. 94-106. — Бібліогр.: 11 назв. — укр.
work_keys_str_mv AT bogdanovom metodizmenšennâčasurealízacííoperacíímnožennânadvelikihčiseldlâsistemizahistuínformacíí
AT zínčenkoâv metodizmenšennâčasurealízacííoperacíímnožennânadvelikihčiseldlâsistemizahistuínformacíí
AT bogdanovom metodyumenʹšeniâvremenirealizaciioperaciiumnoženiâsverhbolʹšihčiseldlâsistemzaŝityinformacii
AT zínčenkoâv metodyumenʹšeniâvremenirealizaciioperaciiumnoženiâsverhbolʹšihčiseldlâsistemzaŝityinformacii
AT bogdanovom methodsofthereductionoftimeforrealizingmultiplicationoperationoflongnumbersforinformationprotectionsystems
AT zínčenkoâv methodsofthereductionoftimeforrealizingmultiplicationoperationoflongnumbersforinformationprotectionsystems
first_indexed 2025-11-25T23:31:40Z
last_indexed 2025-11-25T23:31:40Z
_version_ 1850582652835332096
fulltext Методи захисту інформації в комп’ютерних системах і мережах 94 УДК 519.6:519.712.3:510.52 О. М. Богданов, Я. В. Зінченко Військовий інститут телекомунікацій та інформатизації Національного технічного університету України «КПІ» вул. Московська, 45/1, 01011 Київ, Україна Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації Для підвищення швидкодії асиметричних криптографічних систем ро- зроблено методи зменшення часу реалізації операції множення надве- ликих чисел. Указані методи базуються на застосуванні математич- ного апарату вейвлет-перетворень і, в порівнянні з відомими метода- ми, дозволяють суттєво зменшити обчислювальну складність опера- ції множення багаторозрядних чисел. Ключові слова: асиметричні криптографічні системи, надвеликі чис- ла, вейвлет-перетворення. У більшості асиметричних криптографічних систем захисту інформації при шифруванні, дешифруванні і генерації ключів основною є операція модулярного зведення в ступінь, яка являє собою багаторазове виконання операції множення за модулем простого числа чи добутку простих чисел. З метою забезпечення необ- хідної практичної криптостійкості зазначених систем, розмірності модулів для них вибираються рівними 512…2048 бітам і більше. Оскільки ж процесори сучас- них універсальних ПЕОМ не спеціалізовані на багаторозрядну арифметику, то обчислення ними добутків надвеликих чисел «стовпчиком» (складність цього традиційного методу порядку 2m , де m — довжина числа в бітах) вимагає істот- них часових витрат, що обумовлює низьку швидкість роботи програмних реаліза- цій асиметричних криптосистем. Одним із основних рішень проблеми підвищення швидкодії програмних реа- лізацій асиметричних криптосистем є застосування спеціальних методів множен- ня надвеликих чисел [1]. На сьогоднішній день розроблена досить велика кіль- кість таких методів, кожен з яких має свою область ефективного застосування в залежності від області значень т, моделі обчислень, програмної чи апаратної реа- лізації. Усі ці методи є рекурсивними і засновані на зведенні множення т-роз- рядних чисел до послідовності множень чисел з меншою кількістю розрядів. При їх практичній реалізації т-розрядні двійкові числа, що перемножуються, на- © О. М. Богданов, Я. В. Зінченко Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 95 приклад u і v , представляються як масиви l-бітних слів ( )Kuuuu ,,,, 321 K та ( )Kvvvv ,,,, 321 K , де K — кількість l-бітних блоків у числах. Довжина блоку дорі- внює розрядності процесора використовуваної ЕОМ. Асимптотично найшвидшим з відомих методів є метод Шенхаге-Штрассена [1, 2]. Він заснований на ідеї використання теореми про дискретну згортку двох функцій і дозволяє помножити два т-розрядних двійкових числа за mmm logloglog кроків (бітових операцій). Оскільки дискретна згортка дає осно- вний внесок в оцінку складності методу, то для ефективного її обчислення вико- ристовується алгоритм швидкого перетворення Фур’є (ШПФ). Однак, викорис- тання для обчислення добутків надвеликих чисел алгоритму ШПФ пов’язане з де- якими обчислювальними труднощами, оскільки цей алгоритм розроблений для поля комплексних чисел, а перемножуються цілі багаторозрядні числа. До таких труднощів варто віднести витрати машинного часу на обчислення тригонометри- чних функцій, а також боротьбу з помилками заокруглення при обчисленні триго- нометричних функцій виду Ni N eW p2-= . Авторами пропонуються два методи зменшення часу реалізації операції мно- ження надвеликих чисел. Перший — це модифікація методу, який був запропоно- ваний у роботі [3]. Сутність модифікації полягає в заміні операції обчислення ко- ефіцієнтів Уолша з використанням швидкого перетворення Уолша (ШПУ) на опе- рацію обчислення цих коефіцієнтів із використанням швидкого перетворення Ха- ара (ШПХ). У порівнянні з запропонованим у [3] модифікований метод дозволяє зменшити час виконання операції множення надвеликих чисел за рахунок скоро- чення кількості додавань, необхідних для її реалізації. Другий метод є самостій- ним методом авторів і заснований на використанні вейвлетів Хаара для ефектив- ного обчислення дискретної згортки без переходу в поле комплексних чисел. На відміну від відомих, розроблений метод дозволяє зменшити час виконання опера- ції множення надвеликих чисел за рахунок скорочення кількості множень, необ- хідних для її реалізації. Розглянемо запропоновані методи по-порядку. З [3] відомо, що загальна кількість додавань, які необхідні для обчислення циклічної згортки двох послідовностей x та y довжиною nN 2= (згортка дає ос- новний внесок в оцінку складності методу множення великих чисел), дорівнює: ( ) ( ),75,2231325,332342 111111 321 -+×=×-+-+×= =++= +-+--+ ++++ å nn QQQQ nnnnnnn (1) де 1 1 2 ++ ×= nnQ — кількість додавань, необхідних для виконання кроку 1 алгори- тму (обчислення коефіцієнтів Уолша xF та yF вихідних послідовностей x та y з використанням ШПУ); ( )11 2 234 --+ -= nnQ — кількість додавань, необхідних для виконання кроку 2 алгоритму (обчислення вектора лінійних комбінацій з коефіці- єнтів xF та yF ); ( )nnQ 25,33 1 3 ×-= ++ — кількість додавань, необхідних для ви- конання кроку 3 алгоритму (обчислення коротких згорток). О. М. Богданов, Я. В. Зінченко 96 Оптимізація алгоритму обчислення циклічної згортки за кількістю додавань можлива за рахунок мінімізації кількості додавань при виконанні кроку 1. Відомо [4], що кількість додавань, необхідних для обчислення коефіцієнтів Уолша та Хаара векторів довжиною nN 2= з використанням швидких алгорит- мів, дорівнює nn 2× та ( )122 -n відповідно. З приведених нижче співвідношень, які пов’язують перетворення Уолша та Хаара, випливає, що перетворення Уолша можна замінити перетворенням Хаара. Останнє забезпечує економію кількості додавань (при 2562 == nN приблизно в чотири рази) і, відповідно, більш високу швидкість обчислень. Ці співвідношення дають сімейство ортогональних перет- ворень, яке включає перетворення Уолша та Хаара. До цих перетворень відно- ситься один загальний алгоритм швидкого обчислення. Відповідно до [5] позначимо матриці Хаара [ ]nH 2 й Уолша-Адамара [ ]nW2 по- рядку n2 , рядки яких являють собою n2 функцій Хаара й Уолша, нормованих на n2/1 ; розіб’ємо матриці [ ]nH 2 і [ ]nW2 на ( )1+n прямокутних підматриць [ ]k nMH 2 і [ ]k nMW2 розміром ( )122 -´ kn , nk ...,,1= . Матриця [ ]0 2nMH являє собою перший рядок 0H , матриця [ ]0 2nMW являє собою перший рядок 0W , а матриці [ ]k nMH 2 і [ ]k nMW2 формуються з функцій Хаара й Уолша рангу r , причому kk r 22 1 <£- . Матриці [ ]nH 2 і [ ]nW2 , а також підматриці [ ]k nMH 2 і [ ]k nMW2 пред- ставлені на рис. 1. } [ ] } [ ] [ ] [ ] ï ï ï ï ï ï ï ï î ï ï ï ï ï ï ï ï í ì ï ï þ ï ï ý ü - - - - ---- ïþ ï ý ü -- -- H H H H H HM H H HH HH M M M 3 3 7 6 5 4 2 3 3 2 1 31 0 30 22000000 00220000 00002200 00000022 11111111 11111111 22220000 00002222 } [ ] } [ ] [ ] [ ] ï ï ï ï ï ï ï ï î ï ï ï ï ï ï ï ï í ì ï ï þ ï ï ý ü ---- ---- ---- ---- ---- þ ý ü ---- ---- W W W W W WM W W WW WW M M M 3 3 7 6 5 4 2 3 3 2 1 31 0 30 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111 Рис. 1. Матриці і підматриці Хаара й Уолша-Адамара Між підматрицями [ ]k nMH2 й [ ]k nMW2 існує матричне співвідношення, яке їх зв’язує [6]: [ ] [ ] [ ] [ ] ,...,,1,2222 11 nkMHSWMW kk nkkn =××= -- (2) де [ ]12 -kW — упорядкована матриця Уолша-Адамара порядку 12 -k , а [ ]12 -kS — ма- триця перестановок порядку 12 -k . Матриця Хаара порядку 2n Матриця Уолша-Адамара порядку 2n Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 97 Оскільки [ ]12 -kW і [ ]12 -kS симетричні й ортогональні, то є можливість одер- жати зворотне співвідношення: [ ] [ ] [ ] [ ] ....,,1,2222 11 nkMWSWMH kk nkkn =××= -- (3) У роботі [7] доводиться справедливість виразів (2) і (3) та визначаються спів- відношення, що зв’язують перетворені вектори ( ) 1210 ...,,, -nwwww VVVV й ( ) 1210 ...,,, -nHHHH VVVV , які відповідають вихідному вектору V . Помноживши праві частини виразів (2) і (3) на вектор V , одержимо: [ ] [ ] ,.. 12 12 11 12 12 22 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ ××= ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - -- - - k k kk k k H H w w V V SW V V (4) [ ] [ ] ... 12 12 11 12 12 22 ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ ××= ÷ ÷ ÷ ÷ ø ö ç ç ç ç è æ - - -- - - k k kk k k w w H H V V SW V V (5) Набори коефіцієнтів перетворених векторів, що з’являються у виразах (4) і (5), називаються зонами. Із співвідношень видно, що зона перетвореного вектора HV визначає відповідну зону перетвореного вектора wV . Ця властивість показує, що якщо вектор V апроксимується деякою підмножиною зон перетворених век- торів HV і wV чи, зокрема, якщо ці вектори усікаються наприкінці зони, то після зворотних перетворень виходить вихідний наближений вектор V . У співвідношеннях (4) і (5) відповідні зони зв’язані ортогональними перетво- реннями. З теореми Парсеваля випливає, що енергії відповідних зон перетворених векторів однакові. На рис. 2 наведено схему алгоритму швидкого обчислення перетворення Ха- ара 8-го порядку. Згідно [7], повторне застосування співвідношення (4) дозволяє одержати з цієї схеми схему алгоритму швидкого обчислення перетворення Уол- ша 8-го порядку, представлену на рис. 3. Пунктирними лініями обведені перетво- рення Уолша нижчих порядків, після яких здійснюються перебудови матриць [ ]S . Таким чином, застосування співвідношень (2) і (3) призводить до того, що перетворення Хаара діє так само, як і перетворення Уолша, а кількість додавань, необхідних для обчислення коефіцієнтів Уолша послідовності довжини nN 2= , зменшується на величину ( ) 2221222 1 +-×=--× +nnnn nn . З урахуванням того, що в алгоритмі (1) обробляються дві послідовності ( x і y ), і для кожної з них ви- ходить зазначений виграш, загальне зменшення кількості додавань складе О. М. Богданов, Я. В. Зінченко 98 ( ) ( ) 422422 121 +-=--× +++ nn nnn . Загальна кількість додавань, необхідних для обчислення циклічної згортки модифікованим алгоритмом, буде дорівнювати: ( ) ,425,131325,3323442 11112 321 -×-×=×-+-+-= =++= -+--+ ++++ å nnnnnnn ZZZZ (6) де ( )42 2 1 -= ++ nZ — кількість додавань, необхідних для виконання кроку 1 алго- ритму (обчислення коефіцієнтів Уолша xF та yF вихідних послідовностей x і y з використанням ШПХ); ( )11 22 234 --++ -== nnQZ — кількість додавань, необхід- них для виконання кроку 2 алгоритму (обчислення вектора лінійних комбінацій з коефіцієнтів xF та yF ); ( )nnQZ 25,33 1 33 ×-== +++ — кількість додавань, необхід- них для виконання кроку 3 алгоритму (обчислення коротких згорток). Рис. 2. Схема алгоритму швидкого обчислення перетворення Хаара Рис. 3. Схема алгоритму швидкого обчислення перетворення Уолша Вихідний вектор V0 V1 V2 V3 V4 V5 V6 V7 Коеф. Хаара VH0 VH1 VH2 VH3 VH4 VH5 VH6 VH7 a k b Початок операції a + kb Вихідний вектор V0 V1 V2 V3 V4 V5 V6 V7 Коеф. Уолша VW0 VW1 VW2 VW3 VW4 VW5 VW6 VW7 a k b Початок операції a + kb Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 99 Результати порівняння вихідного (1) і модифікованого (6) алгоритмів приве- дені в зведеній табл. 1, яка містить кількість додавань, необхідних для обчислення циклічної згортки кожним з них. Аналіз таблиці показує, що для обчислення цик- лічної згортки по вихідному алгоритму (1) необхідне виконання більшої кількості операцій додавання, ніж по модифікованому алгоритму (6). Таблиця 1. Складність алгоритмів обчислення циклічної згортки n + 1Q + 2Q + 3Q + SQ + 1Z + 2Z + 3Z + SZ Економія кількості додавань 10 20480 76684 173563 270727 4092 76684 173563 254339 16388 9 9216 25220 57257 91693 2044 25220 57257 84521 7172 8 4096 8236 18787 31119 1020 8236 18787 28043 3076 7 1792 2660 6113 10565 508 2660 6113 9281 1284 Ефективність модифікованого алгоритму визначимо коефіцієнтом ефектив- ності h за співвідношенням: %.100× - = + ++ å åå Q ZQ h (7) На рис. 4 зображений графік залежності коефіцієнта ефективності модифіко- ваного алгоритму, вираженого у відсотках, від значень n . З графіка видно, що ма- ксимальна економія за кількістю додавань досягається при невеликих значеннях n . Рис. 4. Ефективність модифікованого алгоритму 0 5 10 15 20 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 n h,% О. М. Богданов, Я. В. Зінченко 100 На основі модифікованого алгоритму згортки будується метод зменшення ча- су реалізації операції множення надвеликих чисел [8]. Приведемо його короткий покроковий опис. Крок 1. Обчислити згортку з використанням алгоритму (6). Крок 2. Обчислити добуток u на v , виконуючи зсуви і додавання l -роз- рядних чисел. При програмній реалізації розробленого методу на сучасних 32-бітних проце- сорах значення параметрів l і K вибираються в такий спосіб. Багаторозрядні чи- сла u і v розбиваються на блоки довжиною, рівною 16-ти бітам ( 16=l ), і до ко- жного з блоків зліва додається така ж кількість нулів. З отриманих 32-бітних бло- ків (16 нулів плюс 16 значущих біт) формуються два часові ряди. Їхні довжини рівні aK 2= . Довжина кожного часового ряду подвоюється шляхом додавання до нього такої ж кількості нульових 32-бітних блоків (у цьому випадку результатом обчислення циклічної згортки буде лінійна згортка, яка, з урахуванням зсувів і додавань l -розрядних чисел, і є добутком u і v ). Загальна кількість 32-бітних блоків в одному часовому ряді KN n ×== 22 дорівнює розмірності дискретного перетворення Уолша і, як правило, не перевищує 1024 . У результаті справедливе співвідношення: 328162 +=×=×== nb NKm . Порівняння розробленого методу зменшення часу реалізації операції мно- ження надвеликих чисел з методом, запропонованим у роботі [3], показує, що при реалізації розробленого методу на ЕОМ необхідно виконання меншої кількості операцій додавання. У випадку, якщо 107 << n (довжини багаторозрядних чи- сел-співмножників варіюються від 1024 до 8192 біт), економія кількості додавань складає від 7 % до 12 %. Зазначений діапазон довжин чисел-співмножників є най- більш придатним для сучасної класичної асиметричної криптографії. Тепер розглянемо другий метод зменшення часу реалізації операції множення надвеликих чисел. Відповідно до роботи [9], введемо деякі позначення. Позначимо циклічну згортку ( )yxrxy o двох векторів x і y довжини nN 2= : ( ) å - = Åt -=== 1 0 ,1,0, N m mkmxy Nkyxrkr N (8) де N Å — додавання за модулем N , а також їхню лінійну згортку ( )yxS xy à : ( ) å -- = += 1 0 . kN m kmmxy yxkS (9) Оскільки згортки (8) і (9) можна легко виразити одну через іншу за допомо- гою співвідношень: ( ) ( ) ( ),1--+= mNSmSmr xyxyxy (10) Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 101 ( ) ( ) ,1,0, -== NmmrmS yxxy )) (11) де 12,0 ,,0 ,, ,,0 ,, -= î í ì ³ < = î í ì ³ < = Nr Nr Nry y Nr Nrx x r r r r )) , то алгоритми, отримані для циклічної згортки, легко перетворюються в алгоритми лінійної згортки і на- впаки. Визначимо знакову згортку ( )yxPxy Ñ векторів x і y довжини nN 2= в такий спосіб: ( ) å - = Å= 1 0 N m mkkxy N yxkP Sign ,úû ù êë é -÷ ø öç è æ Å mkm N (12) де Sign ( ) î í ì <- ³ = .0,1 ,0,1 x x x Запишемо циклічну згортку (8) в матричній формі: ,yxrr cxy == t (13) де cx — циркулянтна матриця; представимо її у виді: å - = = 1 0 , N m m mc Dxx (14) де D — матриця циклічного зсуву на одну позицію. Характеристичний поліном ( )ld матриці D , рівний ( )1-Nl , при NN 2= ро- зкладається над  на множники: ( ) ( )( )( ) ( )1,...,111 22 +++-= Nd lllll , (15) внаслідок чого справедливе твердження про те, що матриця D приводиться над  . Для розуміння суті наступних міркувань, приведемо доведену в [9] теорему про перетворення циркулянтної матриці до блочно-діагонального виду за допомо- гою перетворення Хаара. Теорема. Матриця циклічного зсуву на один розряд перетворенням Хаара приводиться до блочно-діагонального виду, тобто: { },2...42100 1 NSSSSSSdiagAHDH -==- (16) О. М. Богданов, Я. В. Зінченко 102 де iS — матриця, розмірністю ,22 ii ´ з елементами [ ] ï î ï í ì ==-=- += = ,0 ,1,0,12,1 ,1,1 0Skl kl S i lki H — матриця перетворення Хаара. З (16) випливає, що: .1 AHHD -= (17) Підставимо (17) в (14): ( ) . `1 0 1 0 11å å - = - = -- == N m N m m m m mc HAHxAHHxx (18) Помноживши (18) зліва на H і справа на 1-H , одержимо: . 1 0 1 å - = - = N m m mc AxHHx (19) Таким чином, з (19) випливає, що перетворення Хаара приводить циркулянт- ну матрицю до блочно-діагонального виду, що і потрібно було довести. Співвідношення (19) також може бути записане в такий спосіб: , 4 0 12 0 20 1 Õ å = - = + - ´= N i k k ikc i i shhHHx (20) де ih — коефіцієнти розкладання вектора x по функціям Хаара; знак ( )´ означає прямий добуток матриць. Перейдемо безпосередньо до алгоритму обчислення згортки. Кінцеві часові ряди 10 ...,, -Nxx та 10 ,..., -Nyy представимо векторами-стовп- цями: ú ú ú ú û ù ê ê ê ê ë é = -1 1 0 Nx x x x M , ú ú ú ú û ù ê ê ê ê ë é = -1 1 0 Ny y y y M . (21) Позначимо вектори циклічного зсуву у виді: Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 103 ú ú ú ú û ù ê ê ê ê ë é- =¢ - - 2 0 1 N N x x x x M , ú ú ú ú û ù ê ê ê ê ë é =¢¢ 0 2 1 x x x x M , ú ú ú ú û ù ê ê ê ê ë é =¢¢¢ - 1 1 0 x x x x N M . (22) Набір матриць ,,,, SPOE які перетворюють вектор довжини N у вектори довжини 2N , визначимо як: ú ú ú ú û ù ê ê ê ê ë é = -2 2 0 Nx x x Ex M , ú ú ú ú û ù ê ê ê ê ë é = -1 3 1 Nx x x Ox M , ú ú ú ú û ù ê ê ê ê ë é + + + = -- 12 32 10 NN xx xx xx Px M , ú ú ú ú û ù ê ê ê ê ë é - - - = -- 12 32 10 NN xx xx xx Sx M . (23) Відзначимо, що: ., ,, OyEySyOyEyPy OxExSxOxExPx -=+= -=+= (24) Оскільки довжина вектора після перетворення будь-яким із приведених вище операторів стає в два рази менше, то перетворення припиняються, коли x стає одномірним вектором (числом). Справедливі співвідношення: ( ) ., EyOxOyExOPOyOxEyExEP xyxy Ñ¢+Ñ=Ñ+Ñ= (25) Розглянемо допоміжні згортки ba, і c виду: ( ) ( ) ( ) .,, EyExOxcOyxOEOySxbyOEExPyExa Ñúû ù êë é -¢=Ñ-=Ñ=+Ñ=Ñ= (26) Тоді: ., caOPbaEP xyxy +=-= (27) Співвідношення (26) і (27) зводять обчислення знакової згортки векторів до- вжиною N до обчислення трьох знакових згорток довжиною 2N . Оскільки зго- ртка (12) векторів [ ]0xx = і [ ]0yy = є [ ]00 yxPxy = , то для обчислення згортки (12) векторів довжиною N буде потрібно n3 операцій множення. Порівнявши співвідношення (20) з алгоритмом (26), (27), який представляє собою кінцевий ітераційний процес, бачимо, що використання перетворення Хаа- О. М. Богданов, Я. В. Зінченко 104 ра дає можливість звести обчислення циклічної згортки tr до визначення ряду знакових згорток коефіцієнтів розкладання векторів x і y по системі Хаара. Розглянемо більш ефективний алгоритм обчислення дискретної циклічної згортки tr припускаючи, що yx = . Представимо згортку (8) з використанням співвідношень (13) і (20) в опера- торному виді. Для цього визначимо матриці KMVL ,,, і G , які перетворюють вектор довжиною N у вектори довжиною 2N : ú ú ú ú ú û ù ê ê ê ê ê ë é = -12 1 0 Nx x x Lx M , ú ú ú ú ú û ù ê ê ê ê ê ë é = - + 1 12 2 N N N x x x Vx M , ú ú ú ú ú û ù ê ê ê ê ê ë é + + + = -- + 112 121 20 NN N N xx xx xx Mx M , ú ú ú ú ú û ù ê ê ê ê ê ë é - - - = -- + 112 121 20 NN N N xx xx xx Kx M , ú ú ú ú ú û ù ê ê ê ê ê ë é × × × = -- + 112 121 20 NN N N xx xx xx Gx M . (28) Відзначимо, що: .,, ,,, VyLyGyVyLyKyVyLyMy VxLxGxVxLxKxVxLxMx ×=-=+= ×=-=+= (29) Справедливі співвідношення: ( ) . , ²+= += ExOxOxExOr OxOxExExEr xx xx oo oo (30) Із співвідношень (30) випливає, що для обчислення циклічної згортки t= rrxy векторів довжиною N необхідне визначення циклічної згортки векторів довжи- ною .2N Розглянемо допоміжні згортки a і b виду: ( ) ( ) ., ExOxbxOExOEPxPxa ooo =++== (31) Тоді: ., bbOrbbaEr xxxx ¢¢¢+¢¢=¢¢¢--= (32) Методи зменшення часу реалізації операції множення надвеликих чисел для системи захисту інформації ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2004, Т. 6, № 4 105 Таким чином, необхідна згортка виходить за допомогою лінійної комбінації допоміжних згорток: a , b , b ¢¢ і b ¢¢¢ . Для обчислення циклічної згортки tr по представленому алгоритму необхід- не виконання ( ) ( ) 42334233 22 loglog nnNN ++=++ операцій множення. На основі розглянутого швидкого алгоритму обчислення дискретної цикліч- ної згортки будується метод зменшення часу реалізації операції множення надве- ликих чисел [10]. Приведемо його короткий покроковий опис. Крок 1. Обчислити згортку з використанням алгоритму (32). Крок 2. Обчислити добуток u на v , виконуючи зсуви і додавання l -роз- рядних чисел. При програмній реалізації розробленого методу на сучасних 32-бітних проце- сорах значення параметрів l і K вибираються за тим же принципом, що і для ме- тоду, заснованому на ШПУ. Порівняємо розроблений метод з методом, описаним в [11], в якому для об- числення дискретної циклічної згортки tr використовується модифікований алго- ритм ШПФ з попередньою заготовкою елементів матриці перетворення. Склад- ність методу [11] дорівнює: ( ) ( ) ,1612log25,1161 2 log5,1 161log3 1 22 2 --×=-÷ ø ö ç è æ -= =--= - ´ nnNN KKT (33) де aK 2= — кількість блоків, на які розбиваються багаторозрядні числа-спів- множники. Результати порівняння методів приведені в зведеній табл. 2, яка містить кіль- кість «малих» множень, необхідних для обчислення добутку багаторозрядних чи- сел кожним з них. Таблиця 2. Складність методів множення багаторозрядних чисел n 5 6 7 8 9 10 11 12 13 T´ 368 944 2288 5360 12272 27632 61424 135152 294896 W´ 70 199 580 1705 5050 15019 44800 133885 400630 Аналіз таблиці показує, що ефективність розробленого методу при 12£n вище ефективності методу, запропонованого в [11]. Для вказаних значень n при обчисленні добутку багаторозрядних чисел розробленому методу потрібна менша кількість «малих» множень, ніж методу, який використовує ШПФ. 1. Кнут Д. Искусство программирования. Т. 2: Получисленные алгоритмы. — М.: Издательс- кий дом «Вильямс», 2001. — 832 с. 2. Шенхаге А., Штрассен В. Быстрое умножение больших чисел // Кибернетический сбор- ник. — 1973. — Вып. 2. — С. 87–98. О. М. Богданов, Я. В. Зінченко 106 3. Задирака В.К., Мельникова С.С. Анализ сложности алгоритма умножения сверхбольших чисел на основе коэффициентов Уолша // Кибернетика и систем. анализ. — 2001. — № 6. — С. 99– 110. 4. Толстых Г.Д. Сверхбыстрое спектральное преобразование по функциям Хаара // Изв. вузов – радиоэлектроника. — 1979. — № 7. — С. 86–89. 5. Andrews H.C. Computer Techniques in Image Processing. — New York: Academic Press, 1970. — Р. 73–90. 6. Alexits G. Convergence Problems of Orthogonal Series. — New York: Pergamon, 1961. — Р. 46–62. 7. Файн Б. Связь между преобразованиями Хаара и Уолша-Адамара // ТИИЭР. — 1972. — № 5. — С. 100–113. 8. Богданов А.М., Зинченко Я.В. Модификация алгоритма умножения сверхбольших чисел на основе коэффициентов Уолша // Захист інформації. — 2002. — № 3. — С. 46–52. 9. Садыхов Р., Шаренков А. Алгоритмы ускоренной свертки // Автоматика. — 1986. — № 3. — С. 71–75. 10. Богданов А.М., Зинченко Я.В. Умножение сверхбольших чисел и быстрое преобразование Хаара // Захист інформації. — 2002. — № 4. — С. 58–67. 11. Задирака В.К., Мельникова С.С. Быстрое умножение многоразрядных чисел с использо- ванием БПФ // Кибернетика и систем. анализ. — 1996. — № 3. — С. 63–67. Надійшла до редакції 26.11.2004 Таблиця 1. Складність алгоритмів обчислення циклічної згортки Таблиця 1. Складність алгоритмів обчислення циклічної згортки Таблиця 1. Складність алгоритмів обчислення циклічної згортки Таблиця 2. Складність методів множення багаторозрядних чисел

Схожі ресурси