Методы и средства защиты информации



              

Необходимые сведения из элементарной теории чисел - часть 2


= 5 х (427 - 3 х 133) — 1 х 13З = 5 х 427 – 16 х (560 - 1 х 427)=

= 21 х 427 - 16 х 560 = 21 х (1547 - 2 х 560) - 16 х 560 =

= 21 х 547 - 58 х 560

Решение: x = 21, y = -58

7.     Число a сравнимо с числом b по модулю n, если a – b делится на n. Запись данного утверждения имеет следующий вид: а = b(mod n). Наименьшее неотрицательное число а, такое, что а = A(mod n) называется вычетом числа A по модулю n. Если (a,n) = 1, то существует x, такое, что x = a-1 (mod n).

Действительно, (a,n) = 1 = d = ax + ny, поэтому ax = 1(mod n). Такое число x называется обратным к а по модулю n и записывается в виде a-1 (mod n).

8.     Пусть функция j(n), где n — натуральное число, равна количеству натуральных чисел, меньших n, для которых (а,n)=1. Такая функция называется функцией Эйлера. Для чисел n вида

n = (pi — простое) функция Эйлера определяется как ?(n) = .

9.     Теорема Эйлера. Пусть (а,n) = 1. Тогда a?(n) = 1(mod n).

Следствие. Если ed = 1(mod ?(n)) и (a, n) = 1, то (аe)d

= а(mod n).

10.  Для большинства вычетов по модулю n = pq показатель степени в соотношении a?(n) = 1(mod n) может быть уменьшен, но в этом случае он зависит от a. Наименьший показатель k(a), для которого ak(a) = 1(mod n), называется порядком числа a по модулю n и обозначается как оrdn(a). Для любого a значение оrdn(a) является делителем значения функции Эйлера ?(n).




Содержание  Назад  Вперед