Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма.
Одна из центральных задач арифметики остатков - решение сравнения: a · x º b (mod n) - Если НОД (a, n) = 1, то существует ровно одно решение, и оно находится с помощью a -1: так как a · a -1 º 1 (mod n), то, домножив обе части сравнения на a -1, получим x º b · a -1 (mod n). - Если НОД (a, n) = g ¹ 1 и g | b, то сравнение имеет g решений. Чтобы их найти нужно разделить исходное сравнение на g: a’ · x’ º b’ (mod n’), где a’ = a / g, b’ = b / g, n’ = n / g. Если x’ – решение полученного сравнения, то решение исходного сравнения - любое число вида x = x’ + i · n’, где i = 0, 1,..., g – 1. - В других случаях решений нет.
Пример: 7 · x º 3 (mod 143) – одно решение, 11 · x º 3 (mod 143) – решений нет, 11 · x º 22 (mod 143) – 11 решений. Ситуация с единственным решением наиболее интересна для криптологии, поэтому важно знать количество элементов кольца, взаимно простых с его модулем. Оно дается функцией Эйлера j и равно j (n). Значение j (n) можно легко найти по разложению числа n на простые множители. Если
где pi – различные простые числа, то Функция Эйлера для любого n > 2 имеет четное значение.
Особый интерес представляют частные случаи: 1. Если p простое, то j (p) = p – 1. 2. Если p и q – простые и p ¹ q, то j (p · q) = (p – 1)(q – 1). Если p - простое число, то любой элемент в Z p (или Z / p Z) обладает мультипликативным обратным. Кольца с такими свойствами называются полями. Определение. Полем называется множество (F, ·, +) с двумя операциями, обладающее свойствами: - (F, +) – абелева группа с нейтральным элементом 0, - (F \ {0}, ·) – абелева группа с нейтральным элементом 1,
- (F, ·, +) удовлетворяет закону дистрибутивности (умножение дистрибутивно относительно сложения). Поле – коммутативное кольцо, в котором каждый ненулевой элемент обратим. Каждый ненулевой элемент кольца Z p взаимно прост с p, так как p простое и, следовательно, обратим. Значит Z p – конечное поле, которое обычно называют полем вычетов по модулю p и обозначают F p = {0, 1,..., p – 1}. Мультипликативная группа Теорема Лагранжа. Обобщение Эйлера для малой теоремы Ферма. Малая теорема Ферма. Конечные поля. Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосистем, на основе эллиптических кривых. Рассмотрим множество многочленов от переменной x с коэффициентами из F p. Это множество обозначается через F p [ x ] и образует кольцо относительно естественных операций суммы и умножения многочленов. Особый интерес представляет случай p = 2. Пример. В кольце F 2[ x ] выполнены равенства: Зафиксируем многочлен f (x) и будем рассматривать остальные элементы кольца F p [ x ] по модулю f (x). Как и натуральные числа по модулю n, возможные остатки от деления на многочлен f (x), будут образовывать кольцо. Оно обозначается через F p [ x ]/ f (x) F p [ x ] (по аналогии с Z / n Z). Пример. f (x) = x 4 + 1 и p = 2. Тогда так как По аналогии с целыми числами по модулю n, где рассматривалось сравнение a · x º b (mod n) можно поставить аналогичный вопрос и для многочленов. Пусть a, b и f – многочлены из F p [ x ]. Существование решения уравнения a · a º b (mod f) также зависит от НОД (a, f) и также возможны три ситуации. Наиболее интересна ситуация, когда НОД (a, f) = 1. Многочлен называется неприводимым, если у него нет делителей, отличных от него самого и констант. Неприводимость многочленов - то же самое, что и простота целых чисел. Кольцо F p [ x ]/ f (x) F p [ x ] является конечным полем тогда и только тогда, когда многочлен f (x) неприводим.
Рассмотрим два неприводимых многочлена над полем F2
Возникают два конечных поля F1 = F p [ x ]/ f 1(x) F p [ x ] и F2 = F p [ x ]/ f 2(x) F p [ x ], каждое состоит из 27 двоичных многочленов (каждый имеет ровно 7 коэффициентов равных 1 или 0), степень которых не превосходит 6. Сложение в обоих полях выглядит одинаково, поскольку при вычислении суммы складываются коэффициенты многочленов по модулю 2. А вот умножаются элементы этих полей по разному: Действительно ли различны поля F1 и F2 или это только кажущееся различие? Изоморфны ли поля F1 и F2? Изоморфизм: отображение j: F1 ® F2, удовлетворяющее двум требованиям: Для построения изоморфизма между F1 и F2 достаточно показать как выражается корень f 2(x) в виде многочлена от корня f 1(x). Изоморфизм существует между любыми двумя конечными полями с одинаковым числом элементов. Все конечные поля совпадают либо с целыми числами по простому модулю, либо с многочленами по модулю неприводимого многочлена. Теорема. Существует единственное (с точностью до изоморфизма) конечное поле с числом элементов равным степени простого числа. Конечное поле из q = pd элементов обозначается символом F q или GF(q) (поле Галуа из q элементов). Любое конечное поле K содержит в себе экземпляр поля целых чисел по некоторому простому модулю p, который называется простым подполем поля K. Число элементов простого подполя называется характеристикой поля и обозначается через char K. В частности char F p = p. На конечном поле характеристики p можно определить отображение Фробениуса: Ф: F q ® F q, Ф(a) = (a p) которое является автоморфизмом (изоморфизмом поля с самим собой). Множество элементов из F q, остающихся неподвижными при действии Ф, совпадает с его простым подполем: {a Î F q | a p = a} = F p. Это утверждение – обобщение малой теоремы Ферма на случай любых конечных полей. Ненулевые элементы конечного поля составляют конечную абелеву циклическую группу
a = gx при некотором целом показателе x. Пример. В поле из восьми многочленов
В нем существует 7 ненулевых элементов, а именно 1, a, a + 1, a2, a2 + 1, a2 + a, a2 + a + 1, где a - корень многочлена x 3 + x + 1 (искусственно введенный элемент, удовлетворяющий соотношению a3 + a + 1 = 0, в котором все действия выполняются по модулю 2). Тогда: a1 = a, a2 = a2, a3 = a + 1, a4 = a2 + a, a5 = a2 + 1, a6 = a2 + a + 1, a7 = 1
и a - примитивный элемент поля Основные алгоритмы. Нахождение НОД не составляет проблем, если известно разложение чисел на простые множители или многочленов на неприводимые многочлены, но разложение на простые множители или неприводимые многочлены (факторизация) – очень трудоемкая операция.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|