Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Арифметика великих чисел

Сучасні ЕОМ працюють з числами обмеженої точності і діапазону значень, які вони можуть приймати. Наприклад, здійснити точний розрахунок 40! уже неможливо, якщо розрахунок здійснюється з використанням стандартних типів даних.

Рисунок 9.2 – Результат розрахунку факторіалу

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

Крім того, якщо для представлення дійсних чисел використовується плаваюча кома, то під “великими числами” розуміють, насамперед великі цілі числа (big integers).

Існує група задач, що вимагають використання чисел, розрядність яких перевищує стандартні типи даних ЕОМ:

– Цілочисельні розрахунки з використанням функцій, результат яких швидко зростає (факторіал, числа Фібоначчі і т.д.)

– Точні наукові розрахунки

– Криптографічні алгоритми

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

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

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

У чому проблема використання байтів для представлення великих чисел у десятковій системі числення?

Проблема нераціональності використання простору: один байт – 256 можливих значень, число у десятковій формі – 10 можливих значень.

Зайві витрати простору: (256-10)/256*100% = 99,7% (!!!)

Якщо використовується 32-бітний тип даних, то витрати пам’яті становлять (65536 – 10) / 65536 * 100% = 99,98% (!!!)

Яким чином можна вирішити проблему?

Реалізація великих чисел

Масив:

int[] digit = new int[10000];

Приклад програми розрахунку факторіалу довільної розмірності:

static void Main(string[] args)

{

const int Limit = 1000;

const int Base = 10;

int[] digit = new int[Limit+1];

int carry, d;

int last;

char[] text = new char[Limit+1];

char[] tdigit = new char[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

digit[1] = 1;

last = 1;

for (int n = 1; n <= 365; n++)

{

carry = 0;

for (int i = 1; i <= last; i++)

{

d = digit[i] * n + carry;

digit[i] = d % Base;

carry = d / Base;

}

while (carry > 0)

{

if (last >= Limit)

throw new Exception("Overflow!");

last++;

digit[last] = carry % Base;

carry = carry / Base;

}

}

for (int i = 1; i <= last; i++)

{

text[Limit - i + 1] = tdigit[digit[i]];

}

string s = new String(text);

s = s.TrimStart('\0');

Console.WriteLine(s);

}

Рисунок 9.4 - Розрахунок для n = 365

 

Лекція 10. Алгоритми криптографії та хешування

Перелік питань:

1. Значення випадкових чисел у програмуванні.

2. Алгоритми генерації рівномірно розподілених псевдовипадкових чисел.

3. Перевірка якості випадкових чисел.

4. Кодування з виправленням помилок.

5. Стиснення даних.

6. Стиснення даних зі словником.

7. Алгоритм стиснення Лемпела-Зіва.

8. Введення до криптографії.

9. Елементи теорії порівнянь.

10. Шифрування за допомогою випадкових чисел.

11. Створення таємного ключа по Діффі-Хеллману.

12. Система RSA.

13. Алгоритми цифрового підпису.

14. Введення до хешування.

15. Функції хешування.

16. Проста функція хешування рядків.

17. Хеш-таблиці

18. Функції хешування з використанням рандомізації.

19. Вирішення конфліктів за допомогою лінійного зондування.

20. Видалення елементів із хеш-таблиці з лінійним зондуванням.

21. Клас хеш-таблиць з лінійним зондуванням.

22. Інші схеми відкритої адресації.

23. Квадратичне зондування.

24. Псевдовипадкове зондування.

25. Подвійне хешування.

26. Вирішення конфліктів за допомогою зв’язування.

27. Вирішення конфліктів за допомогою групування.

28. Розширююче хешування.

 

10.1. Значення випадкових чисел у програмуванні

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

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

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

Випадкові числа розподілені за різними законами: біноміальним, нормальним, законом Пуассона і т.д.

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

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

Поширені способи генерації випадкових чисел

Використання системних значень дати, часу, різноманітних таймерів, лічильника тактів процесора

Зчитування пристроїв введення інформації (клавіатури, миші)

Використання сенсорів температури, сигналів аудіоканалів, зображення веб-камер

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

Використання спеціальних пристроїв, наприклад, лічильників радіації Гейгера

Використання таблиць заздалегідь згенерованих чисел

Використання спеціалізованих сервісів, які надають можливість отримувати випадкові числа через Інтернет

 

Алгоритм генерації псевдовипадкових чисел на основі системного часу

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

 

namespace RandomGenerator

{

class Program

{

static void Main(string[] args)

{

for (int i = 0; i < 10; i++)

{

int Rand = DateTime.Now.Millisecond % 100;

Console.WriteLine(Rand);

Thread.Sleep(100 + Rand * 10);

}

Console.ReadKey();

}

}

}

 

Використання стандартного класу Random в C#

10.2. Алгоритми генерації рівномірно розподілених псевдовипадкових чисел

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

I(n+1)=(a*I(n)+c)(mod m)

де число a називається мультиплікатором;

число c – інкрементом;

число m - модулем

 

Приклад генератора рівномірно розподілених псевдовипадкових чисел

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading;

namespace RandomGenerator

{

class Program

{

static int next = 1;

static int GetRand() {

next = next * 1103515245 + 12345;

return((int)(next/65536)%32768);

}

 

static void Main(string[] args)

{

 

for (int i = 0; i < 10; i++)

{

int Rand = Math.Abs(GetRand() % 100);

Console.WriteLine(Rand);

}

Console.ReadKey();

}

}

}

Генератор рівномірно розподілених випадкових чисел на основі алгоритму Парка-Міллера

10.3. Перевірка якості випадкових чисел

Якість випадкових чисел визначається їх відповідністю певному закону розподілу

Для перевірки якості необхідно обрати статистичний крітерій (Пірсона, Ст’юдента та ін.) і перевірити гіпотезу про відповідність розподілу

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

Для перевірки якості можна застосовувати спеціальне програмне забезпечення, наприклад вільно доступний пакет Національного інституту стандартів і технології США: http://csrc.nist.gov/groups/ST/toolkit/rng/documentation_software.html

<== предыдущая лекция | следующая лекция ==>
Арифметика чисел з плаваючою комою | Кодування з виправленням помилок
Поделиться с друзьями:


Дата добавления: 2014-01-04; Просмотров: 831; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.009 сек.