Визначення 4.1.8. Якщо багаторазове додавання 1 не дозволяє одержати 0, то поле називається полем характеристики нуль, у цьому випадку воно містить копію поля раціональних чисел.
Визначення 4.1.9. Якщо існує просте число p таке, що p-кратне додавання 1 дає 0, число p називається характеристикою поля. У цьому випадку поле містить копію поля Z/р.
Кільце поліномів над полем F у множині змінних X={X1,…,Хт}, позначається F[X], утворюється як суми добутків ступенів цих змінних з коефіцієнтами з F. (Нагадаємо, що на відміну від поля, не кожен відмінний від 0 елемент кільця має зворотний елемент по множенню). Поліноми в F[X] складаються і збільшуються по тим же правилам, що і поліноми над дійсними змінними. [14]
Визначення 4.2.1. Говорять, що поліном g поділяє поліном f, якщо існує поліном h такий, що f = g ´ h, f, g, h Î F[X]
Визначення 4.2.2. Найбільшим загальним дільником (н.з.д.) двох поліномів g, f кільця F[Х] називається нормований поліном найбільшого ступеня, що поділяє кожний з цих поліномів. [14]
Визначення 4.2.3. Поліном f Î F[X] називається неприводимим, якщо f = g ´ h тільки у випадку, коли або g або h є константою.
Неприводимі поліноми серед поліномів грають ту ж роль, що прості числа серед цілих чисел. Далі будуть розглядатися тільки поліноми однієї зміної (випадок т = 1, X = Х1).
Визначення 4.2.4. Ступенем полінома називається найбільший ступінь d змінної X, що є присутнім у поліномі з ненульовим коефіцієнтом аd.
Визначення 4.2.5. Поліном називається нормованим, якщо аd = 1.
Обчислення в GF(2n) можуть бути швидко реалізовані апаратно за допомогою регістрів зсуву з лінійним зворотним зв'язком. З цієї причини обчислення над GF(2n) часто швидше, ніж обчислення над GF(p). Через те, що зведення в ступінь у GF(2n) набагато ефективніше, то ефективніше й обчислення дискретних логарифмів.
Для поля Галуа GF(2n) криптографи полюбляють використовувати як модулі тричлени р(х)=хn+х+1, тому що довгий рядок нулів між коефіцієнтами при хn дозволяє просто реалізувати швидке множення по модулю. Поліном повинний бути примітивним, у противному випадку математика не буде працювати, хn+х+1 примітивний для наступних значень n, менших чим 1000:
1, 3, 4, 6, 9, 15, 22, 28, 30,46, 60, 63, 127, 153, 172, 303,471, 532, 865, 900
Існують апаратні реалізації GF(2127), де р(х)=х127+х+1. [1]
Будь-яке кільце поліномів однієї або більш змінних має єдину факторизацію, у тім змісті, що кожен поліном з кільця може бути представлений у вигляді добутку неприводимих поліномів єдиним з точністю до порядку множників чином.
Похідна полінома f ступеня d однієї змінної X визначається за правилом пХп-1 для складаючих поліном ступенів Xn змінної X, а не через поняття межі через те, що відсутнє поняття відстані або топології в F.
Поліном f одного змінного ступеня d може мати або не мати корінь у F, тобто елемент rÎ F, такий, що f(r) = 0. У першому випадку поліном першого ступеня X – r поділяє f; якщо (X – r)m є вищий ступінь від (X – r), що поділяє f, говорять, що r – корінь кратності m. Через одиничність факторизації загальне число коренів полінома f у F з урахуванням кратності не перевищує d. Якщо поліном f Î F має кратний корінь r, то r буде і коренем похідної f¢, і, отже, н.з.д. поліномів f і f¢
Нехай даний поліном f (X) Î F[X] однієї змінної і мається розширення K, поля F таке, що f (X) Î K[X] розкладається в добуток лінійних множників (або, що еквівалентно) має d коренів у К с обліком кратностей, де d – ступінь полінома f (X), і таке, що K, є найменшим розширенням поля, що містить ці корені. [14]
Визначення 4.2.6. K називається полем розкладання полінома f над полем F . Таке поле єдине з точністю до ізоморфізму.
Визначення 4.2.7. Якщо поле F володіє тією властивістю, що всякий поліном з коефіцієнтами з F розкладається на лінійні множники, тобто всякий такий поліном має корені з F тоді воно називається алгебраїчно замкнутим.
Визначення 4.2.8. Найменше замкнуте поле, що містить F,
називається алгебраїчним замиканням поля F і позначається 
. Наприклад,
алгебраїчним замиканням поля R дійсних чисел є поле C комплексних
чисел. [14]
В даному розділі автори подають деякі відомості по генерації псевдовипадкових послідовностей, які використовуються при розробці потокових шифрів. Більше інформації на цю тему можна знайти в [1, 2, 4, 6, 7, 10, 13]
Визначення 5.1.1. Лінійними конгруентними генераторами називаютьсягенератори наступної форми
Xп = (aXп-1 + b) mod m
у яких Хn – це n-ий член послідовності, а Хn-1 – попередній член послідовності. Параметри a, b і m – постійні: a – множник, b – інкремент, і m – модуль. Ключем, або початковим значенням, служить значення Х0. [7]
Період такого генератора не більше, ніж m. Якщо а, b і mобрані правильно, то генератор буде генератором з максимальним періодом(іноді називаним максимальною довжиною), і його період буде дорівнює т. (Наприклад, b повинне бути взаємно простим з m.) [4]
У таблиці 5.1 перелічуються деякі константи для лінійних конгруентних генераторів. Усі вони забезпечують генератори з максимальним періодом і, що навіть більш важливо, задовольняють спектральному тесту на випадковість для розмірностей 2, 3, 4, 5 і 6. Таблиця організована по максимальному добутку, що не викликає переповнення в слові зазначеної довжини.
Перевагою лінійних конгруентних генераторів є їхня швидкість за рахунок малої кількості операцій на біт. [2]
Лінійні конгруентні генератори не можна використовувати в криптографії, тому що вони передбачувані. Уперше лінійні конгруентні генератори були зламані Джимом Рідсом (Jim Reeds), а потім Джоан Бояр (Joan Boyar). Їй удалося також розкрити квадратичні генератори:
Xn = (аХn-12 + bXn-2 + с) mod m
і кубічні генератори:
Xn = (аXn-13 + bXn-22 + cХn-3+ d) mod m
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.