Лекции по криптологии / Y18_M02_L10
.doc
Лекция 10. Теоремы Эйлера и Ферма.
10.1.Порядки чисел по модулю.
Пусть конечная группа, и . Последовательность степеней элемента образует подгруппу группы . Эта подгруппа является конечной и называется циклической. Элемент называется ее порождающим элементом.
В последовательности степеней элемента , рано или поздно, возникнут равные элементы:, т.е. возникнет случай, когда , .
Минимальное число с указанным свойством называется порядком элемента .
Таким образом, в последовательности степеней элемента лишь элементов различны: . Следовательно, порядок циклической подгруппы равен . Очевидно, этот порядок должен делить порядок всей группы.
Таким образом, порядок группы делится на порядки ее элементов.
В кольце числа, взаимно простые с модулем, образуют группу по умножению.
Рассмотрим степени числа по модулю , где и взаимно просты.
Пусть . Вычеты степеней числа для показателей таковы: . Аналогично, те же степени числа сравнимы соответственно с числами .
В каждом случае имеется периодичность. Наименьшая длина периода числа по модулю называется порядком (показателем) числа по модулю .
Порядок числа по модулю обозначается .
10.2 Функция Эйлера.
Порядки чисел по модулю различны. Существуют числа, являющееся порядком одновременно для всех чисел, взаимно простых с . Одно из них равно значению т.н. функции Эйлера , определяемой как количество чисел в последовательности , взаимно простых с .
Функция Эйлера является мультипликативной: если , то и .
Пусть , тогда .
Определение. Число называется первообразным корнем (первообразным элементом) по модулю , если его порядок по модулю равен .
При первообразные корни всегда существуют.
Известно, что в каждом конечном поле также существует первообразный элемент (генератор поля). Степени первообразного элемента представляют все ненулевые элементы поля.
В частности, если первообразный элемент поля , то сравнение разрешимо для ненулевых вычетов по модулю .
Показатель в этом сравнении называется дискретным логарифмом числа по основанию . Дискретные логарифмы часто называют индексами и обозначают или .
10.3. Теоремы Эйлера и Ферма.
Теорема Эйлера. Если , то .
Доказательство теоремы Эйлера.
Пусть все различные числа, взаимно простые с , не превосходящие . Очевидно, .
Поскольку, , в последовательности любые два члена с разными индексами несравнимы по модулю . Поэтому последовательности и совпадают с точностью до перестановки.
Следовательно, произведение всех членов одной последовательности сравнимо с произведением всех членов другой последовательности, откуда, после сокращения на , получаем .
Из теоремы Эйлера следует малая теорема Ферма: , где - простое, .
Эти теоремы интенсивно используются в асимметричной криптографии и, кроме того, очень полезны для сокращения вычислений.
Как следствие, из теоремы Эйлера вытекает, что элемент является первообразным корнем по модулю тогда и только тогда, когда выполняются соотношения: , где .
Заметим, что в каждом конечном поле , при , , выполняется соотношение . Это связано с тем, что число является порядком мультипликативной группы поля.
Чтобы учесть значение , умножим части указанного соотношения на . В итоге получим, что для любого элемента конечного поля верно соотношение .
Напомним, что расширение конечного поля может быть построено как кольцо вычетов многочленов по модулю неприводимого над простым полем многочлена : .
Для некоторых неприводимых многочленов последовательность пробегает все возможные вычеты, т.е. все элементы поля. Такие многочлены называются примитивными.