Функция Эйлера. Поле. Теоремы Эйлера - Лагранжа и Ферма.

Одна из центральных задач арифметики остатков - решение сравнения:

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 имеет четное значение.

- наибольшее подмножество элементов, образующих группу по умножению # = j(n). (количество элементов мультипликативной группы кольца вычетов по модулю n равно j(n)).

Особый интерес представляют частные случаи:

1. Если p простое, то j(p) = p – 1.

2. Если p и q – простые и p ¹ q, то j(p · q) = (p – 1)(q – 1).

Если p - простое число, то любой элемент в Zp (или Z/pZ) обладает мультипликативным обратным. Кольца с такими свойствами называются полями.

Определение. Полем называется множество (F, ·, +) с двумя операциями, обладающее свойствами:

- (F, +) – абелева группа с нейтральным элементом 0,

- (F \ {0}, ·) – абелева группа с нейтральным элементом 1,

- (F, ·, +) удовлетворяет закону дистрибутивности (умножение дистрибутивно относительно сложения).

Поле – коммутативное кольцо, в котором каждый ненулевой элемент обратим. Каждый ненулевой элемент кольца Zp взаимно прост с p, так как p простое и, следовательно, обратим. Значит Zp – конечное поле, которое обычно называют полем вычетов по модулю p и обозначают Fp = {0, 1, ..., p – 1}. Мультипликативная группа = {1, ..., p – 1} поля вычетов содержит все ненулевые элементы Fp.

Теорема Лагранжа. .

Обобщение Эйлера для малой теоремы Ферма. , при НОД(x, n) = 1.

Малая теорема Ферма. .

Конечные поля.

Целые числа по простому модулю – не единственный пример конечных полей. Более общий тип полей используется при рассмотрении таких криптосистем как AES, поточных шифров на основе РСЛОС и криптосистем, на основе эллиптических кривых.

Рассмотрим множество многочленов от переменной x с коэффициентами из Fp. Это множество обозначается через Fp[x] и образует кольцо относительно естественных операций суммы и умножения многочленов. Особый интерес представляет случай p = 2.

Пример. В кольце F2[x] выполнены равенства:

Зафиксируем многочлен f(x) и будем рассматривать остальные элементы кольца Fp[x] по модулю f(x). Как и натуральные числа по модулю n, возможные остатки от деления на многочлен f(x), будут образовывать кольцо. Оно обозначается через Fp[x]/f(x)Fp[x] (по аналогии с Z/nZ).

Пример. f(x) = x4 + 1 и p = 2. Тогда

так как

По аналогии с целыми числами по модулю n, где рассматривалось сравнение

a · x º b (mod n)

можно поставить аналогичный вопрос и для многочленов. Пусть a, b и f – многочлены из Fp[x]. Существование решения уравнения

a · a º b (mod f)

также зависит от НОД (a, f) и также возможны три ситуации. Наиболее интересна ситуация, когда НОД (a, f) = 1.

Многочлен называется неприводимым, если у него нет делителей, отличных от него самого и констант. Неприводимость многочленов - то же самое, что и простота целых чисел. Кольцо Fp[x]/f(x)Fp[x] является конечным полем тогда и только тогда, когда многочлен f(x) неприводим.

Рассмотрим два неприводимых многочлена над полем F2

и .

Возникают два конечных поля

F1 = Fp[x]/f1(x)Fp[x] и F2 = Fp[x]/f2(x)Fp[x],

каждое состоит из 27 двоичных многочленов (каждый имеет ровно 7 коэффициентов равных 1 или 0), степень которых не превосходит 6. Сложение в обоих полях выглядит одинаково, поскольку при вычислении суммы складываются коэффициенты многочленов по модулю 2. А вот умножаются элементы этих полей по разному:

Действительно ли различны поля F1 и F2 или это только кажущееся различие?

Изоморфны ли поля F1 и F2?

Изоморфизм: отображение j: F1 ® F2, удовлетворяющее двум требованиям:

Для построения изоморфизма между F1 и F2 достаточно показать как выражается корень f2(x) в виде многочлена от корня f1(x).

Изоморфизм существует между любыми двумя конечными полями с одинаковым числом элементов. Все конечные поля совпадают либо с целыми числами по простому модулю, либо с многочленами по модулю неприводимого многочлена.

Теорема. Существует единственное (с точностью до изоморфизма) конечное поле с числом элементов равным степени простого числа.

Конечное поле из q = pd элементов обозначается символом Fq или GF(q) (поле Галуа из q элементов).

Любое конечное поле K содержит в себе экземпляр поля целых чисел по некоторому простому модулю p, который называется простым подполем поля K. Число элементов простого подполя называется характеристикой поля и обозначается через char K. В частности char Fp = p. На конечном поле характеристики p можно определить отображение Фробениуса:

Ф: Fq ®Fq, Ф(a) = (ap)

которое является автоморфизмом (изоморфизмом поля с самим собой). Множество элементов из Fq, остающихся неподвижными при действии Ф, совпадает с его простым подполем:

{a Î Fq| ap = a} = Fp.

Это утверждение – обобщение малой теоремы Ферма на случай любых конечных полей.

Ненулевые элементы конечного поля составляют конечную абелеву циклическую группу . Образующая этой группы называется примитивным элементом конечного поля. Примитивный элемент есть в любом конечном поле, их может быть и несколько. Всегда можно найти такой элемент g Î Fq, что любой ненулевой элемент a Î Fq будет представляться в виде

a = gx

при некотором целом показателе x.

Пример. В поле из восьми многочленов

.

В нем существует 7 ненулевых элементов, а именно

1, a, a + 1, a2, a2 + 1, a2 + a, a2 + a + 1,

где a - корень многочлена x3 + 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 - примитивный элемент поля . Целые числа по модулю p также имеют примитивный элемент, так как Fp – конечное поле.








Дата добавления: 2016-02-13; просмотров: 1484;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.016 сек.