Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Управління інформацією
Кафедра:
Захист інформації
Інформація про роботу
Рік:
2008
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Алгоритмічні основи криптології
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
АЛГОРИТМИ ДЛЯ ВИКОНАННЯ ОПЕРАЦІЙ З ДОВГИМИ ЧИСЛАМИ
МЕТОДИЧНІ ВКАЗІВКИ ДО ЛАБОРАТОРНОЇ РОБОТИ № 1
З ДИСЦИПЛІНИ “АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ”
для студентів базових напрямів
6.170101 “Безпека інформаційних і комунікаційних систем”,
6.170102 “Системи технічного захисту інформації”,
6.170103 “Управління інформаційною безпекою”
Затверджено на засiданнi кафедри “Захист інформації”,
протокол № від 2008 р.
Львів – 2008
Алгоритми для виконання операцій з довгими числами: Методичні вказівки до лабораторної роботи №1 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою” /Укл.: А.Е.Лагун, В.М.Іванюк - Львів: НУЛП 2008. - 00 с.
Укладачі: А.Е.Лагун, к.т.н., доцент
В.М.Іванюк, асистент
Відповідальний за випуск:
І.Я. Тишик, старший викладач.
Рецензент: В.В.Максимович, д.т.н., професор.
Мета роботи - вивчити способи представлення та алгоритми для виконання операцій введення-виведення, порівняння, підсумовування, віднімання довгих чисел та навчитися розробляти програмне забезпечення для реалізації перерахованих алгоритмів на комп’ютері.
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1. Розміщення в пам’яті комп’ютера довгих чисел та аналіз типів даних для виконання арифметичних операцій з ними.
Арифметичні дії, що виконуються комп’ютером в обмеженій кількості розрядів не завжди дозволяють одержати точний результат. Також існують обмеження на розмір (величину) чисел, з якими можна працювати. Прикладом може бути виконання дій з дуже великими числами, наприклад 30! = 265252859812191058636308480000000.
В таких випадках необхідно певним чином представити числа в машині та точно виконати арифметичні операції з ними.
Число 30! можна представити у вигляді: 30!=2•(104)8+6525•(104)7+2859• (104)+8121•(104)5+9105•(104)4+8636•(104)3+3084•(104)2+8000•(104)1+0000•(104)0.
Таке представлення записується у вигляді масиву (таблиця 1). Можна вважати, що наведене "довге" число представлене в 10000–10 системі числення, а "цифрами" числа є чотиризначні числа.
Таблиця 1.
Номер элементу в масиві А
0
1
2
3
4
5
6
7
8
9
Значення
9
0
8000
3084
8636
9105
8121
2859
6525
2
Числа, для представлення яких в стандартних комп’ютерних типах даних не вистачає кількості двійкових розрядів, називаються довгими, а алгоритми реалізації арифметичних операцій з довгими числами – довгою арифметикою.
Алгоритми роботи з довгими числами залежать від представлення користувачем цих чисел в комп’ютері. Довге число можна записати, наприклад, за допомогою масиву десяткових цифр. Кількість елементів такого масиву дорівнює кількості значущих цифр в довгому числі. Проте, якщо реалізувати арифметичні операції з цим числом, то розмір масиву має бути достатнім, щоб розмістити в ньому і результат, наприклад множення.
В десятковій та інших позиційних системах числення декілька записаних поруч цифр формують число. Множина можливих значень кожної цифри обмежена, проте за рахунок позиційної ваги, яка залежить від положення цифри, за допомогою короткого запису представляються достатньо великі числа. Цей алгоритм можна використати для побудови довгих чисел.
Якщо взяти масив звичайних цілих і вважати його позиційним записом довгого числа у системі числення з деякою основою, наприклад B, то кожен елемент масиву набуває значення з діапазону від 0 до В-1, а N таких елементів дозволять представити числа від 0 до ВN-1.
Наступним кроком алгоритму є виділення місця для запису довгого числа. В першу чергу потрібно визначитися із типом запису довгого числа в масив, а саме як записати довге число в масив: з початку чи з кінця масиву, з початку чи з кінця числа. Наприклад, для N=6, B=10 розмістимо число 2000. Можливі чотири варіанти (таблиця 2):
Таблиця 2.
№ варіанту
Тип запису
1
2
0
0
0
2
0
0
0
2
3
2
0
0
0
4
0
0
0
2
Ще однією проблемою є заповнення невикористаних розрядів. Під час кодування цих розрядів, як правило, використовується один з таких підходів:
кожному довгому числу відповідає змінна цілого типу – лічильник, що показує скільки елементів масиву реально використане;
невикористані розряди заповнюються значенням, яке наперед не може зустрітися в числі, наприклад –1;
невикористані розряди заповнюються нулями і обробляються так само, як і ті, що використовуються.
Останній підхід можливий лише для першого та четвертого варіантів розміщення довгого числа.
При написанні програм на основі алгоритмів роботи з довгими цілими числами, необхідно враховувати виконання операцій з цілими числами в різних мовах програмування.
В список допустимих операцій для цілих чисел входять 5 арифметичних операцій, 6 порівнянь і присвоєння.
Включення присвоєння в список операцій є звичним для мови СІ, проте незвичне на Паскалі та Бейсіку. Операції порівняння для цілих чисел відомі – це порівняння на рівність, нерівність, менше, більше, менше рівне, більше рівне. Синтаксис операцій порівняння в різних мовах може відрізнятися, наприклад “не дорівнює” в Паскалі записується “<>”, в СІ – “!=”, у Фортрані – “.NE.”, проте суть від запису не залежить. Порівняння – це операція, яка так само як і звичні арифметичні операції має операнди, лише результатом порівняння є не цілий, а логічний тип.
При виконанні арифметичних операцій підсумовування, віднімання і множення в різних мовах проблем не виникає, за виключенням ситуації переповнення.
Набагато складніше з операцією ділення. Звичайне математичне ділення двох цілих може дати дробовий результат. Для того, щоб залишитися в діапазоні множини цілих чисел, потрібно використати цілочисельне ділення, а саме вважати часткою цілу частину результату, а дробову відкидати.
В багатьох мовах ціле ділення є окремою операцією, для якої існує спеціальне позначення. Наприклад, в багатьох версіях Бейсіку для цього використовується зворотна похила лінія, а в Паскалі – службове слово div. Запис операції ділення за допомогою похилої лінії недопустимий, оскільки він дає результат дійсного типу.
В мові СІ використовується інший підхід. Спеціальної операції цілочисельного ділення тут немає, проте звичайне ділення виконується як цілочисельне, якщо обидва операнди цілого типу.
Для операції остачі цілочисельного ділення в різних мовах також існують свої позначення, наприклад в Бейсіку та Паскалі – службове слово mod, а в мові СІ – знак %.
1.2. Алгоритми введення-виведення довгих чисел.
Спочатку потрібно описати дані. Позначимо основу системи числення для представлення довгого числа Osn і приймаємо це значення рівним 10000; максимальну кількість цифр довгого числа (MaxDig) беремо 1000.
Розглянемо приклад.
А[0]
А[1]
А[2]
А[3]
ch
Примітка
3
0124
7498
516
-
Кінцевий стан
0
0
0
0
5
Початковий стан
1
5
0
0
1
1-й крок
1
51
0
0
6
2-й крок
1
516
0
0
7
3-й крок
1
5167
0
0
4
4-й крок
2
1674
5
0
9
5-й крок: старша цифра елемента А [1] перейшла в поки "порожній елемент" А[2]
2
6749
51
0
8
6-й крок
2
7498
516
0
0
7-й крок
2
4980
5167
0
1
8-й крок
3
9801
1674
5
2
9-й крок
3
8012
6749
51
4
10-й крок
0124
7498
516
-
11-й крок
Нехай у файлі записане число 51674980124 і основою (Osn) є 10000 (зберігаємо по чотири цифри в елементі масиву А). Зміна значень елементів масиву А під час введення (посимвольного в змінну ch) показана в таблиці 3.
Таблиця 3.
Проаналізуємо таблицю.
1. В А[0] зберігаємо кількість задіяних (ненульових) елементів масиву А.
2. При обробці кожної чергової цифри вхідного числа старша цифра елемента масиву з номером i стає молодшою цифрою числа в елементі i+1, а цифра, що вводиться, буде молодшою цифрою числа з А[1]. В результаті роботи алгоритму отримали число, записане ззаду наперед.
Нехай ми вводимо число 51674980124 і перші 8 цифр вже розмістили ззаду наперед в масиві А. В символьну змінну ch зчитали чергову цифру "довгого числа" – "1". Ця цифра "1" повинна бути розміщена молодшою цифрою в А[1]. В таблиці 4 відображені результати роботи цього фрагменту алгоритму, який звільняє місце для цієї цифри.
Таблиця 4.
i
А[1]
А[2]
А[3]
ch
2
4980
5167
0
1
2
4980
1670
5
1
9800
1674
5
Після цього залишається тільки додати поточну (зчитану в ch) цифру "довгого числа" до А[1] і змінити значення А[0].
Блок-схема алгоритму введення довгих чисел наведена на рис.1.
Для розроблення алгоритму виведення необхідно врахувати, що в кожному елементі масиву зберігається не послідовність цифр "довгого числа", а значення числа, записаного цими цифрами. Нехай в елементах масиву зберігаються чотиризначні числа. Тоді "довге число", наприклад, 128400583274 буде в масиві А представлено таким чином:
А[0]
А[1]
А[2]
А[3]
3
3274
58
1284
Під час виведення "довгого числа" з масиву необхідно вивести 0058, інакше буде втрата цифр. Тому незначущі нулі також необхідно виводити. Розроблений алгоритм виведення представлений на рис.2.
рис.1. Блок-схема алгоритму введення довгого числа.
Під час виведення "довгого числа" з масиву необхідно вивести 0058, інакше буде втрата цифр. Тому незначущі нулі також необхідно виводити. Один з варіантів алгоритму виведення довгого числа представлений на рис.2.
На рисунку введені позначення: NN – прапорець, що визначає чи розряд числа дорівнює нулю (тоді необхідно виводити чотири нулі); N_Osn=4 – кількість цифр в основі числення.
Спочатку виводяться кількість цифр довгого числа та старший розряд. Потім – наступні старші розряди. Крім того, перевіряється кількість цифр в розряді, і якщо вона менша N_Osn, то число доповнюється незначущими нулями.
рис.2. Алгоритм виведення довгого числа.
1.3. Виконання операцій порівняння довгих чисел.
Операціями порівняння є порівняння на рівність, більше, менше, більше або дорівнює, менше або дорівнює.
Для виконання операцій порівняння довгих чисел використовується нульовий розряд масиву, в якому записана кількість розрядів довгого числа. Якщо кількість розрядів першого числа більша за кількість розрядів другого, то алгоритм визначення, наприклад більшого з двох чисел, повертає логічне значення true, що означає перше число є більшим. У випадку не рівності кількості розрядів відбувається порозрядна перевірка вмісту відповідних розрядів.
Блок-схеми алгоритмів порівняння довгих чисел наведені на рис.3 (а-д).
а)
б)
в) г) д)
рис.3. Блок-схеми алгоритмів порівняння довгих чисел.
1.4. Реалізація алгоритмів додавання та віднімання довгих чисел.
Розроблені алгоритми імітують додавання стовпчиком, починаючи з молодших розрядів. Для простоти реалізації операцій додавання та множення
довгих чисел використовується машинне представлення ззаду наперед.
Числа підсумовуються порозрядно. Якщо сума в будь-якому розряді виявиться більшою за основу системи числення, то у відповідний розряд результату записується остача від ділення суми на цю основу, а в наступний розряд переноситься одиниця.
Блок-схема алгоритму додавання наведена на рис.4.
рис.4. Блок-схема алгоритму додавання довгих чисел.
Числа, які додаються, позначено a і b. Результат додавання в змінній c. Спочатку визначається довжина більшого з чисел. Потім формуються розряди результату додавання. Перенесення в наступний розряд формується як результат цілочисельного ділення на основу суми поточних розрядів доданків та перенесення з попереднього, а поточний розряд – як остача від ділення цієї суми на основу системи числення.
На останньому кроці формується нульовий розряд результату додавання, в якому знаходиться кількість розрядів довгого числа. Якщо під час формування старшого розряду відбулося перенесення, то попередня кількість розрядів збільшується на 1, інакше залишається без змін.
Для реалізації операції віднімання введемо обмеження: число, від якого віднімають, більше числа, яке віднімається. Якщо ця умова не виконується, то числа переставляються, а в знаковий розряд довгого числа записується 1.
Алгоритм був би схожий на алгоритм додавання, якби не позичання одиниці зі старшого розряду замість перенесення одиниці в старший розряд. Наприклад, в звичайній системі числення ми віднімаємо 9 від 11 – позичається 1 з розряду десятків, а якщо від 10000 віднімаємо 9, то процес позичання складніший. Блок-схема алгоритму віднімання двох довгих чисел наведена на рис.5.
Алгоритм віднімання довгих чисел працює так. Перш за все необхідно визначити, яке з двох чисел більше. Порівняння відбувається за допомогою підпрограм More та Eq наведеними вище. Оскільки віднімання відбувається від більшого з чисел, то в допоміжну змінну, яка визначає число від якого віднімають записується більше з цих чисел, а в іншу тимчасову змінну – менше. Також використовується додаткова змінна minus, яка визначає знак результату (1 – число від’ємне, 0 – додатне).
Якщо два довгих числа рівні, то в нульовий елемент масиву результату записується значення 1, що відповідає одному розряду довгого числа, а в перший елемент – 0, оскільки різниця однакових чисел дорівнює нулю.
На наступному кроці відбувається порозрядне віднімання довгих чисел. Як було зазначено вище, можлива ситуація, коли значення поточного розряду більшого числа є меншим за значення розряду меншого числа. Тоді необхідно здійснити позичання 1 зі старшого розряду.
В розробленому алгоритмі необхідність позичання визначається від’ємним значенням поточного розряду результату. Якщо така ситуація виникає, то до цього розряду додається основа системи числення Osn, а вміст
рис.5. Блок-схема алгоритму віднімання довгих чисел.
наступного розряду зменшується на 1. Цей процес продовжується, доки в поточному розряді результату будуть траплятися від’ємні числа.
Останнім кроком алгоритму віднімання є визначення кількості розрядів результату довгого числа. Це значення записується в нульовий елемент масиву, в якому зберігається результат віднімання довгих чисел. В алгоритмі цей фрагмент реалізований таким чином, що перебираються всі елементи масиву результату, починаючи з молодшого, доки в якомусь із них не зустрінуться нулі.
2. ЗАВДАННЯ
2.1. Домашня підготовка до роботи
1) Вивчити основні способи представлення довгих чисел та алгоритми для реалізації операцій введення, виведення, порівняння, а також арифметичних операцій додавання-віднімання довгих чисел.
2) Скласти блок-схеми алгоритмів та підпрограми для реалізації операцій введення та виведення довгих чисел. Варіанти представлення довгих чисел та способи заповнення невикористаних розрядів беруться за вказівкою викладача з таблиці 5.
3) Скласти блок-схеми алгоритмів, підпрограми та програму для реалізації адитивних операцій та операцій порівняння для роботи з довгими числами. Дані для роботи беруться з таблиці 5 за вказівкою викладача.
Таблиця 5.
№
з/п
Варіант представлення числа
Заповнення невикористаних розрядів
Операції з довгими числами
1
1
використати лічильник
Додавання, більше
2
2
-1
Віднімання, менше
3
3
використати лічильник
Додавання, менше або рівно
4
4
0
Віднімання, більше або рівно
5
1
0
Додавання, рівно
6
2
використати лічильник
Віднімання, не рівно
7
3
-1
Додавання, менше
8
4
використати лічильник
Віднімання, більше
9
1
-1
Додавання, більше або рівно
10
2
-1
Віднімання, менше або рівно
11
3
використати лічильник
Додавання, не рівно
12
4
0
Віднімання, рівно
13
1
0
Додавання, більше
14
2
-1
Віднімання, менше
15
3
використати лічильник
Додавання, менше або рівно
16
4
-1
Віднімання, більше або рівно
17
1
0
Додавання, рівно
18
2
-1
Віднімання, не рівно
19
3
-1
Додавання, менше
20
4
використати лічильник
Віднімання, більше
21
1
0
Додавання, більше або рівно
22
2
використати лічильник
Віднімання, менше або рівно
23
3
-1
Додавання, не рівно
24
4
використати лічильник
Віднімання, рівно
2.2. Робота в лабораторії
1) Ввести в комп'ютер програми згідно з отриманим завданням.
2) Відлагодити програми. При необхідності скоригувати блок-схеми алгоритмів та програми у відповідності з виявленими логічними та синтаксичними помилками.
3) Остаточні версії блок-схем, програм та отримані результати занести у звіт з лабораторної роботи.
4) Здати звіт з лабораторної роботи.
3. ЗМІСТ ЗВІТУ
1) Номер і назва лабораторної роботи.
2) Повний текст завдання.
3) Остаточні версії блок-схем алгоритмів.
4) Список ідентифікаторів констант, змінних, процедур і функцій, використаних у блок-схемах алгоритмів і програм, та їх пояснення.
5) Остаточні версії програм.
6) Результати роботи програм.
4. КОНТРОЛЬНІ ЗАПИТАННЯ
1. Що таке довга арифметика?
2. Наведіть способи представлення довгих чисел в пам’яті комп’ютера.
3. Як відбувається кодування невикористаних розрядів довгих чисел?
4. Поясніть алгоритми введення-виведення довгих чисел. Яка між ними різниця?
5. Як відбувається порівняння довгих чисел?
6. В чому суть алгоритмів додавання та віднімання довгих чисел? Яка між ними різниця?
СПИСОК ЛІТЕРАТУРИ
О.Н.Василенко, Теоретико-числовые алгоритмы в криптографии. – М.: Изд-во МГУ, 2000
Ященко В.В. Введение в криптологию. – Сбп. Питер, 2000.
Ноден П., Китте К. Алгебраическая алгоритмика. – М.: Мир, 1999.
Проценко В.С., Чаленко П.Й., Ставровський А.Б. Техніка програмування мовою Сі: Навч. посібник.- К.: Либідь, 1993.
Сайт algolist.ru.
Навчальне видання
Алгоритми для виконання операцій з довгими числами: Методичні вказівки до лабораторної роботи №1 з дисципліни “Алгоритмічні основи криптології” для студентів базових напрямів 6.170101 “Безпека інформаційних і комунікаційних систем”, 6.170102 “Системи технічного захисту інформації”, 6.170103 “Управління інформаційною безпекою”
Укладачі:
Лагун Андрій Едуардович
Іванюк Віталій Миколайович.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора