Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Управління інформацією
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
ДОСЛІДЖЕННЯ ШВИДКОДІЇ ВИКОНАННЯ МУЛЬТИПЛІКАТИВНИХ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 2
З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ”
для студентів базових напрямів
6.170101 “Безпека інформаційних і комунікаційних систем”,
6.170102 “Системи технічного захисту інформації”,
6.170103 “Управління інформаційною безпекою”
Затверджено на засiданнi кафедри “Захист інформації”,
протокол № від 2008 р.
Львів – 2008
Дослідження швидкодії виконання мультиплікативних операцій з довгими числами: Методичні вказівки до лабораторної роботи №2 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с.
Укладачі: А.Е.Лагун, к.т.н., доцент
В.М.Іванюк, асистент
Відповідальний за випуск:
І.Я. Тишик, старший викладач.
Рецензент: В.В.Максимович, д.т.н., професор.
Мета роботи - вивчити алгоритми множення та ділення довгих чисел та навчитися розробляти програмне забезпечення для реалізації цих алгоритмів на комп’ютері; дослідити швидкодію алгоритмів множення довгих чисел.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Множення довгих чисел з використанням стовпчика.
При виконанні операції множення довгих чисел можна скористатися моделюванням стовпчика, виконуючи на кожному кроці перенесення в наступний розряд.
рис.1. Блок-схема алгоритму, що реалізує арифметичну операцію множення довгого числа на коротке.
Блок-схема одиного з варіантів алгоритму множення довгого числа на коротке, де коротке число є беззнаковим цілим (unsigned int), наведена на рис.1.
Використовується додаткова змінна t для визначення кількості розрядів результату і формування перенесення в наступний розряд. Довге число записане в масиві a, а коротке – в змінній b.
В першу чергу значення результату обнулюється. Далі перевіряється, чи короткий множник дорівнює 0. Якщо так, то в результаті буде число нуль. Інакше відбувається формування розрядів результату множення, які дорівнюють остачі від ділення на основу системи числення добутку розряду довгого множника на короткий множник плюс розряд перенесення.
Значення перенесення в наступний розряд результату є цілою частиною від ділення добутку ai*b+t на основу системи числення.
На останньому кроці формуються значення кількості розрядів результату, старші розряди результату за рахунок цілочисельного ділення та остачі цілочисельного ділення значення перенесення t на основу системи числення.
Алгоритм множення довгого числа на довге (рис.2) подібний до описаного вище алгоритму множення за винятком того, що під час формування розрядів результату перемножуються відповідні розряди довгих чисел ai та bi. Також відбувається додавання до кожного розряду результату множення значення проміжного множення на окремий розряд tti.
1.2. Алгоритм ділення довгих чисел.
Ділення двох довгих чисел полягає в знаходженні цілої частини частки і остачі. Вважаємо, що дільник – це число, яке ділить, ділене – число, на яке ділять, частка – результат ділення. Можливі три випадки.
якщо дільник дорівнює діленому, то ціла частина результату дорівнює 1, а остача 0;
якщо дільник менший за ділене, то ціла частина частки дорівнює нулю, а остача – дільнику;
якщо дільник більший за ділене, то необхідна підпрограма ділення двох довгих чисел.
рис.2. Блок-схема алгоритму множення довгих чисел способом стовпчика.
1000143123567 | 73859998
-73859998 | 13541 (Ціла частина частки)
261543143
- 221579994
399631495
- 369299990
303315056
295439992
78750647
- 73859998
4890649 (Залишок)
Далі починаються проблеми. Наприклад, поділимо стовпчиком два довгі числа 1000143123567 і 73859998.
На кожному етапі підбирається цифра (1, 3, 5 і т.д.), така, що добуток цієї цифри на дільник дає число менше, але найближче до числа. Для початку спростимо приклад. Нехай число А буде менше В • 10, тоді в результаті (цілої частини ділення) буде одна цифра. Наприклад, А дорівнює 564, а В – 63 і маємо десяткову систему числення. Спробуємо підібрати цифру результату, але не методом прямого перебору, а методом поділу відрізка навпіл. Нехай Down – верхня межа інтервалу зміни цифри, яка підбирається, Up – нижня межа інтервалу, Ost дорівнює діленому, Div – операція цілочисельного ділення.
Результат покрокового виконання алгоритму зводимо в таблицю 1.
Таблиця 1.
Down
Up
С=В • ( (Down+Up) Div 2)
Ost=564
0
10
315 = 63 • ( (0 + 10) Div 2)
C<Ost
5
10
441 = 63 • ( (5 + 10) Div 2)
C<Ost
7
10
504 = 63 • ( (7 + 10) Div 2)
C<Ost
8
10
567 = 63 • ( (8 + 10) Div 2)
C<Ost
8
9
504 = 63 • ( (8 + 9) Div 2)
C<Ost
Отже, результат – ціла частина частки – дорівнює (Up + Down) Div 2, залишок від ділення – різниця між значеннями Ost і С. Нижню межу (Down) змінюємо, якщо результат (С) менший залишку, верхню (Up), якщо більший.
Ускладнимо приклад. Нехай А дорівнює 27856, а В – 354. Основою системи числення є не 10, а 10000. Результати цього випадку наведені в таблиці 2.
Ціла частина частки дорівнює 78, залишок від ділення - 27856 мінус 27612, тобто 244. В одному з варіантів алгоритму ділення використовуються підпрограми порівняння довгих чисел Less і More, а також підпрограма множення довгого числа на коротке.
Блок-схема алгоритму ділення довгих чисел, вхідними параметрами якого є два довгих числа a і b, а вихідними - ціла частина результату ділення res і остача ost, наведена на рис.3.
На першому кроці задаються початкові умови для результату, а саме обнуляються масиви цілої частини та остачі ділення, а в нульові розряди цих
Таблиця 2.
Down
Up
С
Ost=27856
0
10000
1770000
С>Ost
0
5000
885000
C>Ost
0
2500
442500
C>Ost
0
1250
221250
C>Ost
0
625
110448
C>Ost
0
312
55224
C>Ost
0
156
27612
C<Ost
78
156
41418
C>Ost
78
117
34338
C>Ost
78
97
30798
C>Ost
78
87
29028
C>Ost
78
82
28320
C>Ost
78
80
27966
C>Ost
78
79
27612
C<Ost
масивів записується 1. Далі алгоритм визначає, чи не рівні між собою два числа. Якщо так, то цілій частині результату присвоюється значення 1.
Інакше, якщо дільник менший за ділене, то в масив остачі результату копіюється дільник, оскільки дільник і буде остачею від ділення.
В протилежному випадку дільник також копіюється в ost і вводиться додаткова змінна zs, яка визначає різницю між довжиною дільника і діленого. Якщо дільник менший від діленого, помноженого на основу числення, то це означає, що в результаті є одна цифра і тоді змінна zs зменшується на 1. Кількість розрядів цілої частини результату дорівнює zs+1.
На наступному кроці знаходимо чергову цифру результату, доки значення змінної зсуву не стане дорівнювати нулю за допомогою алгоритму підбору цифри результату методом поділу відрізку навпіл, блок-схема якого наведена на рис.4.
Оскільки цифра цілої частини результату не перевищує основи системи числення, то нижній межі відрізка, на якому шукається потрібна цифра, присвоюється значення 0, а верхній – значення основи системи числення (Osn).
Далі формується цикл, в якому шукається потрібна цифра, доки нижня
рис.3. Блок-схема алгоритму ділення довгих чисел.
межа не стане більша за верхню.
В циклі відбуваються такі дії. Перемножується середина відрізка пошуку ((Up+Down)/2) на ділене і одержане значення перевіряється з дільником. Якщо дільник більший за одержане значення, то нижній межі присвоюється значення середини відрізка, якщо менший, то верхній межі присвоюється середина відрізка, а якщо значення рівні, то верхній межі присвоюється середина, а нижня межа стає рівна верхній.
На наступному кроці одержана цифра перемножується на ділене для того, щоб знайти остачу від ділення. Потім від дільника віднімається результат множення і записується в масив ost, в якому знаходиться остача результату
рис.4. Пошук цілої частини частки методом поділу відрізку навпіл.
ділення.
На останньому кроці алгоритм повертає знайдену цифру цілої частини результату ділення.
Після закінчення роботи алгоритму ділення довгих чисел, в змінній res буде знаходитися ціла частина результату ділення, а в ost – остача результату ділення.
1.3. Алгоритм швидкого множення.
Маємо два довгих числа в канонічній формі:
, (1)
Існує набагато ефективніший алгоритм, що називається “швидким множенням” і дозволяє замінити множення натуральних чисел невеликою кількістю підсумовувань.
Алгоритм швидкого множення використовує вирази:
якщо b – парне, то a*b=(2a)*(b/2),
якщо b – непарне, то a*b=a+a*(b-1) (2)
і наведений на рисунку 5.
рис.5. Блок-схема алгоритму швидкого множення довгих чисел.
Після завершення роботи алгоритму b стане рівним нулю, а p – добутку.
1.4. Множення з використанням швидкого перетворення Фур’є (ШПФ).
Для множення дуже довгих чисел використовуються алгоритми, що працюють за допомогою згортки Фур’є:
(3)
з наступним перетворенням. Підсумовування відбувається за k, l – ми номерами відповідних розрядів чисел a та b.
У коефіцієнтів згортки є практичний смисл – вони дають результат множення многочлена a0+a1x1+…+an-1xn-1 на многочлен b0 + b1x1 +… + bm-1xm-1, де степені m та n – довільні натуральні числа.
(a0+a1x1+…+an-1xn-1)(b0 + b1x1 +… + bm-1xm-1)=c0 + c1x1 +… + cn+m-1xn+m-1
Числа в записі за основою Osn є многочленами, де x – це основа, тому згортка може бути проінтерпретована як результат множення числа
А= a0+a1Osn1+…+an-1Osnn-1 на число B= b0 + b1Osn1 +… + bm-1Osnm-1 без обчислення перенесень.
A(B=с0+c1Osn1+…+cn+m-1Osnn+m-1 (4)
Конструкцію, яку утворюють коефіцієнти ci називають пірамідою множення, оскільки довжина виразу для коефіцієнтів спочатку зростає, досягаючи максимуму в середині, а потім спадає, перетворюючись в кінці на нуль.
c0=a0*b0;
c1=a0*b1+a1*b0;
c2=a0*b2+a1*b1+a2*b0;
…
…
cn+m-3=an-1*bm-2+an-2*bm-1;
cn+m-2=an-1*bm-1;
cn+m-1=0
В цьому випадку базовий тип, що використовується повинен мати достатній об’єм для зберігання коефіцієнтів порядку (n+m-1)*Osn2, які знаходяться на вершині піраміди.
Таким чином, для множення довгих чисел достатньо
Обчислити коефіцієнти згортки ci, i=0..n+m-1.
Зробити необхідні перенесення, щоб всі коефіцієнти були менші Osn.
Всі перенесення можна обчислити протягом O(n+m) кроків, переходячи від молодших розрядів до старших.
Блок-схема фрагменту алгоритму кроку 2 зображена на рис.6.
рис.6. Фрагмент алгоритму перенесення в наступний розряд.
Таким чином, основна складність алгоритму множення полягає в обчисленні коефіцієнтів згортки на кроці 1. Для цього можна використати швидке перетворення Фур’є і швидке перетворення Хартлі.
Швидке перетворення Фур’є комплексного вектора (a0, a1, …, aN-1) обчислюється як комплексний вектор з координатами (y0, y1, …, yN-1):
(5)
де ( - комплексний корінь N-го степеня з одиниці, тобто
(6)
Індекс степеня N може бути відсутній, тоді степінь кореня дорівнює кількості координат вектора, що перетворюється.
До дискретного перетворення Фур’є існує обернене, яке обчислюється за формулою
(7)
1.5. Застосування ШПФ для обчислення згортки a(b.
В ШПФ використовується теорема про згортку: перетворення Фур’є від згортки двох векторів є скалярним добутком Фур’є-образів цих векторів:
с= a(b ( ШПФ(c)=ШПФ(a)*ШПФ(b),
звідки c=ШПФ-1(ШПФ(a)*ШПФ(b)).
Таким чином, алгоритм обчислення згортки складається з трьох кроків:
Обчислити ШПФ(a) і ШПФ(b).
Скалярно перемножити одержані вектори.
Обчислити зворотне перетворення Фур’є від скалярного добутку.
Перемноження многочленів зводиться до скалярного перемноження відповідних векторів.
Вважаємо, що на кожному кроці розміри векторів однакові і дорівнюють N, оскільки не можна скалярно перемножити короткий вектор на довший, тому загальний час має порядок O(N log N). Найвищої швидкодії досягають варіанти ШПФ, що працюють з векторами розміру 2k, тому вектори за необхідності потрібно доповнити нулями.
Як приклад візьмемо A=(3,4), B=(5,4,3,2,1). Числа зберігаються задом наперед, а саме старший розряд йде останнім. Тоді алгоритм швидкого множення виглядає наступним чином:
Знайти найменше число Len – степінь двійки: Len≥a0+b0. Для розглянутих чисел Len=8.
Доповнити A і B ведучими нулями до Len: A=(3,4,0,0,0,0,0,0), B=(5,4,3,2,1,0,0,0).
Обчислити ШПФ дійсних векторів на обидвох масивах цифр.
Скалярно перемножити перетворені вектори, одержавши вектор розміру Len.
Застосувати зворотне перетворення Фур’є, результатом якого буде згортка.
Перетворити згортку в масив цілих чисел, зробити перенесення.
Цифри для довгих чисел зберігаються в цілочисельному форматі. Тому для ШПФ їх необхідно скопіювати в тимчасові масиви типу з плаваючою крапкою. Якщо необхідно одержувати результат максимальної довжини N, то необхідно виділити для довгих чисел пам’ять розміру не менше MaxLen=2k, де MaxLen – мінімальний степінь двійки, який більший за N. Наприклад, якщо максимальний результат буде складатися із 1000 цифр за основою Qsn, то мінімальний об’єм пам’яті MaxLen=1024, оскільки будемо рахувати ШПФ саме такої довжини.
В [5] наведений алгоритм та програма, що реалізує ШПФ – функція RealFFT().
Цей алгоритм повертає вектори довгих чисел в стиснутому вигляді (перед використанням запам’ятовуємо розміри масивів в інших змінних):
A[0], A[N/2], A[1], A[2], …, A[N/2-1]
B[0], B[N/2], B[1], B[2], …, B[N/2-1]
Всі обчислення проходять у форматі з плаваючою крапкою і використовують ірраціональні числа, тому результат буде не набором цілих чисел, а наближеним до нього. Для одержання результату кожну координату вектора необхідно округлити до найближчого цілого числа.
Проблема полягає в тому, що якщо точність обчислень недостатньо висока, то округлення може здійснюватися не до потрібного числа. Тоді алгоритм завершиться, проте результат буде невірний. Оскільки арифметичні операції з дійсними числами не можуть здійснюватися абсолютно точно, то розмір використаного типу даних повинен бути досить великим, щоб помилка на кожному знаку була меншою 0,5.
Наприклад при використанні типу даних розміру 1 дріб 1/3 представиться у вигляді 0,3. Під час додавання трьох дробів одержимо 1/3+1/3+1/3=(у форматі для чисел з плаваючою крапкою) =0,9.
Якщо взяти дві цифри, то 1/3=0,33 і 0,33+0,33+0,33=0,99. При цьому точність обчислень значно зросла.
Взагалі кажучи, є два шляхи підвищення точності обчислень, один з яких пов’язаний із збільшенням довжини типу, що використовується, – наприклад, в мові СІ від float до double, від double до double2 і т.д. Другий підхід більш гнучкий і передбачає зменшення довжини основи Osn. Таким чином, число стане довшим, буде займати більше пам’яті, але за рахунок цього підвищиться точність.
На останньому кроці необхідно перетворити згортку у довге число.
2. ЗАВДАННЯ
2.1. Домашня підготовка до роботи
1) Вивчити основні алгоритми множення та ділення довгих чисел, а також способи підвищення швидкодії виконання мультиплікативних операцій з довгими числами.
2) Скласти блок-схеми алгоритмів та програми для реалізації операцій множення (стовпчиком, швидке множення, множення з використанням перетворення Фур’є) або ділення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться з лабораторної роботи №1. Дані для роботи беруться за вказівкою викладача.
3) Дослідити швидкість виконання мультиплікативних операцій для розрядності довгих чисел від 50 до 200. Накреслити графіки відповідних залежностей і порівняти одержані результати.
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
3. ЗМІСТ ЗВІТУ
1) Номер і назва лабораторної роботи.
2) Повний текст завдання.
3) Остаточні версії блок-схем алгоритмів.
4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення.
5) Остаточні версії програм.
6) Результати роботи програм.
4. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Поясніть алгоритм множення довгого числа на коротке способом стовпчика.
2. В чому відмінність між алгоритмами множення стовпчиком довгого числа на коротке і на довге?
3. Наведіть основні кроки алгоритму ділення довгих чисел.
4. Як відбувається пошук цілої частини частки при діленні довгих чисел?
5. Які алгоритми дозволяють прискорити виконання операції множення довгих чисел?
6. В чому суть алгоритму швидкого множення?
7. Як використати швидке перетворення Фур’є для реалізації множення довгих чисел?
СПИСОК ЛІТЕРАТУРИ
О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000
Ященко В.В. Введение в криптологию. – Сбп. Питер, 2000.
Ноден П., Китте К. Алгебраическая алгоритмика. – М.: Мир, 1999.
Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі: Навч. посібник.- К.: Либідь, 1993.
Сайт algolist.ru.
Навчальне видання
Дослідження швидкодії виконання мультиплікативних операцій з довгими числами: Методичні вказівки до лабораторної роботи №2 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою”
Укладачі:
Лагун Андрій Едуардович
Іванюк Віталій Миколайович
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора