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

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

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

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

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

• Алфавіт , елементи якого називаються вхідними змінними.

• Алфавіт , елементи якого називаються службовими змінними.

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

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

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

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

Функцію  розглядаємо як набір  функцій-проекцій ,де . Пря­молінійна програма обчислює функцію , якщо кожна з функцій , де 1 < j < k, визначається деякою командою цієї про­грами. Складністю обчислення функції  прямолінійними програмами називається найменша довжина прямолінійної програми, що обчислює . Подібно означуються мультиплікативна та адитивна складності функції.

приклад  2.1. Функція  в будь-якому кільці обчислю­ється такою програмою:

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