Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


Тлумачний словник






Прямолінійні програми

Алгоритми та їх складність

Розділ III.

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

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

2.1. Означення моделі. Поняття прямолінійної програми можна вводити для довільної алгебраїчної структури. Ми зробимо це для кільця з одиницею. Елементарними операціями будуть множення та додавання в кільці.

Нехай задані наступні об'єкти.

· Символ 1, який називається символом предметної константи і позначає одиницю кільця.

· Алфавіт X = {х1,...,хm}, елементи якого називаються вхідними змінними.

· Алфавіт Z = {z1,.. .,zl}, елементи якого називаються службовими змінними.

· Три символи операцій •, +, -, для множення, додавання та віднімання.

Прямолінійною програмою називається послідовність із l слів у алфавіті
XZ{1, •, +, —, =}, в якій i-те слово має вигляд zs = z'z", де є одним із символів операцій, a z', як і z", є або символом предметної константи, або вхідною змінною, або однією із службових змінних z1,..., zi-1.

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

Припустимо, що в нас є прямолінійна програма, і нехай R — деяке кільце з одиницею. Кожна команда прямолінійної програми визначає деяку функцію f : Rm R, яка, є поліномом від змінних х1,...,хm. Справді, перша команда задає поліном вигляду 1, xj ± 1, xj ± xi, або xj xi. Кожна наступна команда задає функцію, що є добутком, сумою або різницею функцій, визначених якимись із попередніх команд, функцію F : Rm Rk розглядаємо як набір k функцій-проекцій fj : Rm R, де F(х1,...,хm) = f11,...,хm),.., fk1,...,хm). Прямолінійна програми обчислює функцію fj, де 1 j k, визначається деякою командою цієї програми. Складністю обчислення функції F прямолінійними програмами називається найменша довжина прямолінійної програми, що обчислює F. Подібно означуються мультиплікативна та адитивна складності функції.

Приклад 2.1. Функція F(x) = х4 + x2 в будь-якому кільці обчислюється такою програмою:

z1 = xx

z2 = z1x

z3 = z2x

z4 = z3+z1

Отже, складність цієї функції не перевищує 4. Насправді вона менша, тому що для обчислення функції є коротша програма:

z1 = xx

z2 = z1+1

z3 = z1z2

2.2. Піднесення до степеня. Розглянемо задачу обчислення функції f(x) = xd у довільному кільці. Безхитрісна прямолінійна програма для цієї функції має складність d — 1:

z1 = xx

z2 = z1x

z3 = z2x

...

zd-1 = zd-2x

У подальших розділах неодноразово виникатиме задача

ПІДНЕСЕННЯ ДО СТЕПЕНЯ ЗА МОДУЛЕМ n

Задано: xZn, . dN

Обчислити: xd mod n.

Завжди можна вважати, що d < n. Інакше можна скористатися теоремою Ойлера, щоб понизити показник. Якщо ми використаємо для розв'язання цієї задачі наведену вище прямолінійну програму (з множенням в кільці Zn), то отримаємо експоненційний алгоритм. Справді коли d не набагато менше, ніж п, то довжина входу має порядок logn а кількість операцій множення має порядок п.

На щастя, є значно ощадніший алгоритм, який був відомий ще до нашої ери в Індії. Ми називатимемо його бінарним методом. Опишемо цей метод у вигляді прямолінійної програми для обчислення функції f(x) = хd.

Подамо показник d у двійковій системі числення: d = (di . . .d1d0)2 де di {0,1} і d = Для спрощення запису дозволимо одній команді програми виконувати до двох множень і покладемо z0 = 1. Тоді i-та команда задається так:

Всього команд l + 1. Результатом виконання останньої є

Всього витрачається l+2l21og2d множень (множення першої команди не є необхідним — вона включена для однорідності. Наведену прямолінійну програму можна легко конвертувати в алгоритм у сенсі пункту 1.2, чи в програму на будь-якій мові програмування, що розв'язує задачу піднесення до степеня за модулем п.

ВПРАВИ

2.1.Скласти прямолінійну програму для обчислення в будь-якому кільці загального многочлена степеня п:

f(x,x0, x1, . . . , xn) = xn xn + xn-1 xn-1 + ... + x1 x + x0.

a)Реалізувати обчислення безпосередньо за канонічною формою.

b)Реалізувати обчислення за схемою Горнера.

Порівняти складність програми в першому і другому випадках. (Доведення оптимальності схеми Горнера див. в [35] або [7, розділ 12].)

2.2.Довести, що функцію f : Z2 Z, задану співвідношенням f(x1, x2) = НСД(x1, x2), не можна обчислити ніякою прямолінійною програмою.

2.3.Використовуючи бінарний метод, написати прямолінійні програми для обчислення функцій а) х32 , b) х31 , с) х21 .

ЛЕКЦІЯ 9


Читайте також:

  1. II. Вимоги до складання паспорта бюджетної програми
  2. Алгоритм створення тренінгової програми
  3. Анімаційні програми
  4. Антивірусні програми
  5. Важливою складовою економічної політики 60-х рр. була реалізація програми “нових рубежів” президента Дж. Кенеді.
  6. Визначення змінних програми.
  7. Виконання програми - реалізація мови програмування
  8. Вікно програми КОМПАС-ГРАФІК
  9. Демо режим програми
  10. Державні молодіжні програми в Україні
  11. Державні програми щодо попередження бездоглядності та безпритульності дітей.
  12. Діагностика виробничої програми підприємства




Переглядів: 458

<== попередня сторінка | наступна сторінка ==>
 | Рандомізація

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.