Функція Эйлера

Порядок числа за модулем позначається.

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

Мінімальне число із зазначеною властивістю називається порядком елемента.

Порядки чисел за модулем. Функція Ейлера.

Шифр Вернама (одноразовий шифр-блокнот).

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

У системі Г.Вернама потрібно, щоб джерело ключів виробляло випадкову равновероятную двоичную послідовність, знаки якої незалежні і щоб черговий біт відкритого тексту перешифровувався черговим бітом ключа (гами).

К.Шеннон показав, що система Г.Вернама не дешифрується навіть при повному переборі усіх варіантів послідовності гами, внаслідок відсутності критерію відкритого тексту.

На практиці застосовуються послідовності гами, з параметрами, що наближаються до вимог системи Г.Вернама.

Однак чисто випадкова послідовність (у принципі) може містити неякісні ділянки. Тому необхідно розробляти математичні алгоритми для її коректування, що призводить до необхідності формальної оцінки якості гами. Проте, криптосистемы, основані на подібному підході, існують.

У свій час використовувався ручний шифр гамування, для якого гама зберігалася у виглядіі блокнота з відривними аркушами. Після використання чергової сторінки блокнота вона знищувалася.

Можливо, з цієї причини шифр Вернама часто називають одноразовим шифр-блокнотом (one-time pad), хоча, по суті, він є шифром з одноразовою гамою.

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

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

Таким чином, у послідовності степенів елемента лише елементів різні:. Отже, порядок циклічної підгрупи дорівнює. Очевидно, цей порядок повинен ділити порядок всієї групи. Таким чином, порядок групи ділится на порядки її елементів.

Розглянемо степені числа за модулем, де і взаємно прості.

Нехай. Лишки степенів числа для показників такі:. Аналогічно, ті ж степені числа порівнянні відповідно з числами. У кожнім випадку є періодичність.

Найменша довжина періоду числа за модулем називається порядком (показником ) числа за модулем.

Порядок є найменшим позитивним числом, для якого виконується порівняння.

Порядки чисел за модулем різні. Існують числа, що є порядком одночасно для всіх чисел, взаємно простих с. Одне з них дорівнює значенню т.зв. функції Эйлера, що визначається як кількість чисел у послідовності, взаємно простих з.

Функція Эйлера є мультиплікативною: якщо, те і.

Нехай, тоді.

Дата добавления: 2014-10-15