Разработка и реализация математической модели двухключевой криптосистемы - Программирование, компьютеры и кибернетика дипломная работа

Главная

Программирование, компьютеры и кибернетика
Разработка и реализация математической модели двухключевой криптосистемы

Разложение на простые сомножители. Понятия теории сравнений. Вычисление мультипликативного обратного. Существование конечного поля. Шифрование потока данных. Принцип работы RSA-криптосистемы. Криптографический анализ асимметричных систем шифрования.


посмотреть текст работы


скачать работу можно здесь


полная информация о работе


весь список подобных работ


Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Факультет прикладной математики и механики
Кафедра технической кибернетики и автоматического регулирования
Тема: «Разработка и реализация математической модели двухключевой криптосистемы»
2. Математические основы построения RSA-криптосистемы
2.2 Простые числа. Разложение на простые сомножители
2.5 Основные понятия теории сравнений
2.5.2 Вычеты. Полная и приведенная системы вычетов
2.6 Сравнения с одним неизвестным. Вычисление мультипликативного обратного
2.7.3 Мультипликативная группа конечного поля
3.1 Принцип работы RSA-криптосистемы
4. Криптографический анализ асимметричных систем шифрования
5.2 Требования к техническим средствам и шифруемым файлам
Проблема защиты информации путем её преобразования, исключающего её прочтение посторонним лицом, волновала человеческий ум с давних времен. Данная проблема в значительной степени решается использованием криптографии.
С широким распространением письменности криптография стала формироваться как самостоятельная наука. Криптография - наука о методах преобразования информации в целях ее защиты от незаконных пользователей [7]. Почти одновременно с криптографией возникла также наука о методах раскрытия зашифрованной информации - криптоанализ. Криптография занимается поиском и исследованием математических методов преобразования информации. Сфера интересов криптоанализа - исследование возможности расшифровывания информации без знания ключей [4].
Основные направления использования криптографических методов - передача конфиденциальной информации по каналам связи (например, электронная почта), установление подлинности передаваемых сообщений, хранение информации (документов, баз данных) на носителях в зашифрованном виде.
С развитием информационных технологий проблемы защиты информации начинают интересовать все большее число людей. Это утверждение справедливо как в отношении рядовых пользователей, работающих за домашним компьютером, так и компаний, использующих корпоративные сети. Особенно остро вопрос защиты и безопасного использования компьютеров встает при подключении к Internet. Для многих компаний важно не только защитить свои локальные сети от вторжения извне, но и организовать надежные и безопасные каналы связи с филиалами через общедоступную сеть Internet. Кроме того, перед корпоративными заказчиками весьма остро стоит проблема гарантированной доставки сообщений по электронной почте таким образом, чтобы посторонние лица не могли перехватить, подделать или использовать в своих интересах передаваемую информацию. Своего решения ждут также задачи, связанные с электронной коммерцией, так как ее широкомасштабное внедрение невозможно без принятия особых мер по обеспечению безопасности и конфиденциальности сообщений [9].
Для шифрования информации и организации защиты сетей в России активно используются западные продукты. Это разного рода программы защиты от несанкционированного доступа, а также шифрования файлов, -- начиная от Norton Utilities и архиваторов типа PKZIP и заканчивая серьезными приложениями уровня PGP (Pretty Good Private). Даже обычные текстовые редакторы и электронные таблицы содержат те или иные криптографические средства. Широкое распространение получили также межсетевые экраны, средства построения виртуальных частных сетей (Virtual Private Network), организация закрытых каналов обмена информацией и т. д. [9].
Комплекс криптографических методов должен сочетать как удобство, гибкость и оперативность использования, так и надежную защиту от злоумышленников циркулирующей в ИС информации [4].
Наиболее популярна криптосистема RSA, разработанная в 1977 г. и получившая название в честь её создателей: Рона Ривеста, Ади Шамира и Леонарда Эйдельмана. Возможность гарантированно оценить защищенность алгоритма RSA стала одной из причин его популярности на фоне десятков других схем. Поэтому алгоритм RSA используется в банковских компьютерных сетях, особенно для работы с удаленными клиентами (обслуживание кредитных карточек).
Безопасность RSA обусловлена сложностью разложения большого числа на простые сомножители. На сегодняшний день не существует эффективных алгоритмов разложения числа на сомножители [1]. С помощью длины ключа можно регулировать время разложения числа на простые сомножители, которое с увеличением длины ключа будет расти и при определенной длине выйдет за пределы реального. В то же время произведение двух больших простых чисел или возведение большого числа в степень при использовании «быстрых» алгоритмов - несложная задача, занимающая несколько минут машинного времени при достаточно большой величине ключа [1].
Целью данной дипломной работы является разработка алгоритма и реализация математической модели шифра RSA, с оценкой количества итераций, необходимых для разложения большого числа на простые сомножители (скорость «взлома» шифра) и ограничением в зависимости от этого на длину ключа при заданном уровне технических характеристик компьютера; обеспечение возможности работы как с ранее сгенерированными ключами, хранящимися в файле, так и со сгенерированными непосредственно при работе.
Описать криптографическую систему с открытым ключом Р. Ривеста, А. Шамира, Л. Эйдельмана RSA.
Оценить ее криптостойкость, основанную на сложности разложения числа на простые сомножители.
Оценить количество операций, необходимых для шифрации и дешифрации информации; в зависимости от этого и от криптостойкости системы дать рекомендацию на длину ключа.
Написать алгоритм, реализующий криптосистему RSA. Использовать сгенерированные ранее ключи, хранящиеся в файле.
Написать алгоритм дешифрования итерациями для криптосистемы RSA, используя готовые ключи небольшой длины.
2. Математические основы построения RSA - криптосистемы [3]
Создатели криптографической системы RSA воспользовались тем фактом, что нахождение больших простых чисел в вычислительном отношении осуществляется легко, но разложение на множители произведения двух таких чисел практически невыполнимо.
Рассмотрим математические результаты, положенные в основу этого алгоритма.
Здесь и далее будем рассматривать целые числа, обозначая их малыми латинскими буквами (a, b, c, d и т. д.).
Сумма, разность и произведение двух целых чисел также является числом целым, но частное от деления a на b может быть как целым, так и не целым.
В случае, когда частное от деления a на b - целое, обозначим его q, имеем a = bq, т. е. a равно произведению b на целое. Мы говорим тогда, что a делится на b или что b делит a. При этом a называем кратным числа b и b - делителем числа a. В дальнейшем будем рассматривать лишь положительные делители чисел.
Всякое целое a представляется единственным способом через положительное целое b в виде
Число q называется неполным частным, а число r - остатком от деления a на b.
Всякое целое, делящее одновременно целые a и b, называется их общим делителем. Наибольший из общих делителей называется общим наибольшим делителем и обозначается символом НОД (a, b), или просто (a, b). Если (a, b) = 1, то a и b называются взаимно простыми.
Для разыскания общего наибольшего делителя применяется алгоритм Евклида.
Пусть a и b - положительные целые. Согласно (*) находим ряд равенств:
b = r 2 q 2 + r 3 , 0 < r 3 < r 2 ,
r 2 = r 3 q 3 + r 4 , 0 < r 4 < r 3 , (**)
r n -2 = r n -1 q n -1 + r n , 0 < r n < r n -1 ,
заканчивающийся, когда получаем некоторое r n +1 = 0 . Последнее неизбежно, так как ряд b, r 2 , r 3 , … как ряд убывающих целых не может содержать более чем b положительных. Рассматривая равенства (**) сверху вниз, убеждаемся, что общие делители чисел a и b одинаковы с общими делителями чисел r 2 и r 3 , чисел r 3 и r 4 , …, чисел r n -1 и r n , наконец, с делителями одного числа r n . Одновременно с этим имеем:
(a, b) = (b, r 2 ) = (r 2 , r 3 ) = … = (r n -1 , r n ) = r n .
Совокупность общих делителей чисел a и b совпадает с совокупностью делителей их общего наибольшего делителя.
Этот общий наибольший делитель равен r n , т. е. последнему не равному нулю остатку алгоритма Евклида.
Пример. Применим алгоритм Евклида к отысканию (525, 231). Находим
Здесь последний положительный остаток r 4 = 21. Значит, (525, 231) = 21.
2.2 Простые числа. Разложение на простые сомножители
Число 1 имеет только один положительный делитель, именно 1. В этом отношении число 1 в ряде натуральных чисел стоит особо.
Всякое целое, большее единицы, имеет не менее двух делителей, именно 1 и самого себя; если этими делителями исчерпываются все положительные делители целого числа, то оно называется простым. Целое, большее 1, имеющее кроме 1 и себя самого другие положительные делители, называется составным.
Наименьший отличный от единицы делитель целого, большего единицы, есть число простое.
Наименьший отличный от единицы делитель составного числа a (он будет простым) не превосходит .
Число простых чисел бесконечно велико. Справедливость этой теоремы следует из того, что каковы бы ни были различные простые p 1 , p 2 , …, p k , можно получить новое простое, среди них не заключающееся. Таковым будет простой делитель суммы p 1 p 2 … p k +1, который, деля всю сумму, не может совпадать ни с одним из простых p 1 , p 2 , …, p k .
Всякое целое а или взаимно просто с данным простым p, или же делится на p. Действительно, (a, p), будучи делителем p, может быть равно 1, или p. В первом случае a взаимно просто с p, во втором a делится на p.
Если произведение нескольких сомножителей делится на p, то, по крайней мере, один из сомножителей делится на p.
Всякое целое, большее единицы, разлагается на произведение простых сомножителей и притом единственным способом, если отвлечься от порядка следования сомножителей.
Действительно, пусть а - целое, большее единицы; обозначив буквой p 1 его наименьший простой делитель, имеем a = p 1 a 1 . Если a 1 >1, то, обозначив буквой p 2 его наименьший простой делитель, имеем a 1 = p 2 a 2 . Если a 2 >1, то подобно этому находим a 2 = p 3 a 3 и т. д., пока не придем к какому-либо a n , равному единице. Тогда a n -1 = p n . Перемножая все найденные равенства и производя сокращение, получим следующее разложение а на простые сомножители:
Допустим, что для того же самого а существует и второе разложение на простые сомножители a = q 1 q 2 … q s . Тогда
Правая часть этого равенства делится на q 1 . Следовательно, по крайней мере, один из сомножителей левой части должен делиться на q 1 . Пусть, например, p 1 делится на q 1 (порядок нумерации сомножителей не важен). Тогда p 1 = q 1 (p 1 кроме 1 делится только на p 1 ). Сокращая обе части равенств на p 1 = q 1 , имеем p 2 p 3 …p n = q 2 q 3 …q s . Повторяя прежнее рассуждение применительно к этому равенству, получим p 3 … p n = q 3 … q s и т. д., пока, наконец, в одной части равенства, например в левой, не сократятся все сомножители. Но одновременно должны сократиться и все сомножители правой части, так как равенство 1 = q n +1 … q s при q n +1 , …, q s , превосходящих 1, невозможно. Таким образом, второе разложение на простые сомножители тождественно первому.
Функция Эйлера (а) определяется для всех целых положительных а и представляет собою число чисел ряда 0, 1, ..., а-1, взаимно простых с a.
В частности, будем иметь (p a ) = p a - p a -1 , (p) = p-1.
Функция (а) называется мультипликативной, если она удовлетворяет двум следующим условиям:
Эта функция определена для всех целых положительных a и не равна нулю по меньшей мере при одном таком a.
Для любых положительных взаимно простых a 1 и a 2 имеем:
2.5 Основные понятия теории сравнений
Мы будем рассматривать целые числа в связи с остатками от деления их на данное целое положительное m, которое назовём модулем.
Каждому целому числу отвечает определённый остаток от деления его на m. Если двум целым a и b отвечает один и тот же остаток r, то они называются равноостаточными по модулю m.
Сравнимость чисел a и b по модулю m записывается:
Сравнимость чисел a и b по модулю m равносильна:
Возможности представить a в виде a = b + mt, где t - целое.
Действительно, из a b (mod m) следует
a = mq + r, b = mq 1 + r, 0<= r 1 и (a, m) = 1 имеем a ( m ) 1 (mod m).
Доказательство. Действительно, если x пробегает приведённую систему вычетов
x = r 1 , r 2 , ..., r c ; c = (m),
составленную из наименьших неотрицательных вычетов, то наименьшие неотрицательные вычеты 1 , 2 , ..., с чисел ax будут пробегать ту же систему, но расположенную, вообще говоря, в ином порядке (1).
ar 1 1 (mod m), ar 2 2 (mod m), ..., ar c c (mod m),
При p простом и а, не делящимся на p, имеем
Доказательство. Эта теорема является следствием теоремы Эйлера при m = p. Теореме Ферма можно придать более удобную форму, умножая обе части сравнения (2) на а, получим сравнение a p a (mod p), справедливое уже при всех целых а, так как оно верно и при а, кратном p. Теорема доказана.
Теорема (2. 5. 3. 3). Если n = pq, (p и q - отличные друг от друга простые числа), то (n) = (p-1)(q-1).
Теорема (2. 5. 3. 4). Если n = pq, (p и q отличные друг от друга простые числа) и x простое относительно p и q, то x ( n ) = 1 (mod n).
2.6 Сравнения с одним неизвестным. Вычисление мультипликативного обратного [6]
Чтобы вычислить мультипликативную обратную величину а -1 для ненулевого а, необходимо решить сравнение
Это эквивалентно нахождению таких значений x и k, что
где x и k - целые числа. Решение этой задачи иногда существует, а иногда его нет.
Например, обратная величина для числа 5 по модулю 14 равна 3, поскольку 5 *3 = 15 1(mod 14). С другой стороны число 2 не имеет обратной величины по модулю 14.
имеет единственное решение, если a и n - взаимно простые числа.
Если числа a и n не являются взаимно простыми, тогда сравнение
Сформулируем основные способы нахождения обратных величин.
1. Проверить поочередно значения 1, 2, …, n-1, пока не будет найден a -1 такой, что a * a -1 1 (mod n).
Пусть n=7, a=5. Требуется найти x a -1 (mod n)
Подставляя вместо x значения от 1 до n - 1 = 7 - 1 = 6 и вычисляя a * x(mod n), получаем при x=3, a * x = 5 * 3 = 15 1 (mod 7). Следовательно, a -1 = 3.
2. Если известна функция Эйлера (n), то можно вычислить
используя алгоритм быстрого возведения в степень.
Пусть n=7, a=5. Найти x a -1 (mod n) = 5 -1 (mod 7).
Модуль n=7 -простое число. Поэтому функция Эйлера (n) = (7) = n-1 = 6. a -1 = a ( n ) - 1 (mod n) = 5 6-1 (mod 7) = 3.
3. Если функция Эйлера не известна, то можно использовать расширенный алгоритм Евклида.
В этом случае при решении сравнения a * x 1 (mod m), где (a, m) =1 алгоритм Евклида позволяет найти x (-1) k -1 Q k -1 (mod m), где Q k -1 - знаменатель предпоследней подходящей дроби разложения в цепную дробь.
Введем обозначения q i - частное, r i - остаток, тогда алгоритм нахождения q i можно представить в виде следующей цепочки равенств:
r 1 = r 2 q 2 + r 3 , 0 < r 3 < r 2 ,
r 2 = r 3 q 3 + r 4 , 0 < r 4 < r 3 ,
r k-2 = r k-1 q k-1 + r k , 0 < r k < r k-1 ,
Поскольку остатки r i от делений в алгоритме Евклида образуют строго убывающую последовательность натуральных чисел, то обеспечивается сходимость алгоритма. При этом получаем, что r k - есть общий делитель чисел a и m делит и r k = (a, m).
Последовательности {P n } и {Q n } числителей и знаменателей подходящих дробей к цепной дроби определяются рекуррентно
P -2 = 0, P -1 = 1, P n = q n P n -1 + P n -2 , для n>=0,
Q -2 = 1, Q -1 = 0, Q n = q n Q n -1 + Q n -2 , для n>=0. [6]
Пример . Решить сравнение: 1181x 1(mod 1290816). Имеем
k = 5, x = (-1) 4 * 1151925 = 1151925.
В самом деле 1181 * 151925 1 (mod 1290816).
Для решения более сложный сравнений
используется следующий прием. Сначала решают уравнение
x a -1 b (mod n) y * b (mod n). [6]
Получаем y = 5 -1 14 (mod 23), затем находим
x = 14 * 9 (mod 23) = 126 (mod 23) = 11,
Определение. Поле F= < F, +, x, 0, 1 > называют конечным, если F- множество его элементов - конечно.
Обозначение. F, - символ для обозначения конечного поля из q элементов, F* - мультипликативная группа не равных нулю элементов поля F. Если а - элемент некоторого кольца, а n - неотрицательное целое число, то n*а - n-кратное элемента a.
1. Если. p - простое число, то Z/(p) - кольцо классов вычетов по модулю p - конечное поле из p элементов:
{0} P , {1} P , {2} P , ..., {p -1} P . (*)
Если a, b Z, то {a} p = {b} p a b (mod p).
Для краткости при указанном p элементы ряда (*) обозначаем знаками
2. Пусть p = 5, тогда таблицы сложения и умножения элементов поля Fs
Определение. Число элементов конечной группы называют ее порядком. Порядком элемента g G=<=G, *, e> называют наименьшее натуральное число n с условием
Если m - порядок группы G=, g - элемент группы G, то
Если n - порядок элемента g группы , m N, то
Если g 1 , g 2 , …, g m - все элементы группы G, g - элемент группы G, то g*g 1 , g*g 2 , …, g*g m - также все элементы той же группы. Поэтому
отсюда легко выводится первое утверждение.
Это и доказывает второе утверждение.
Теорема 2.7.1.1. Если F q = < F, +, х, 0, 1 > - конечное поле из q элементов,1 - единица поля, то для любого элемента а из F
Доказательство. Равенство (2.7.1.1) следует из теоремы Лагранжа, так как q (число элементов) - порядок аддитивной группы поля F q .
Определение. Пусть F = < F, +, х, 0, 1 > - поле. Если для любого натурального m
то характеристикой поля F называют число 0, а поле F называют полем нулевой характеристики. Если для какого-либо натурального числа m m * 1= 0, то наименьшее число т с таким свойством называют характеристикой поля F.
Пример. Любое числовое поле - поле нулевой характеристики. Кольцо классов вычетов кольца Z целых чисел по простому модулю p - поле характеристики р.
Теорема 2.7.1.2. Если F - подполе поля Н, то характеристики полей F и Н равны.
Доказательство. Утверждение теоремы следует из того, что единица поля является единицей своего подполя.
Пример бесконечного поля конечной характеристики
Пусть p - простое число и F - поле; поле Н рациональных дробей над полем F является расширением поля F и, следовательно, имеет ту же характеристику, что и само поле F.
В частности, если характеристика поля F равна p, то и характеристика поля Н равна p.
Теорема 2.7.1.3. Характеристика поля F ненулевой характеристики есть число простое.
Доказательство. Предположим, что характеристика т конечного поля F есть число составное:
с другой стороны, m * 1 = 0. А так как поле не имеет делителей нуля, то или a * 1 = 0, или b * 1 = 0, что невозможно при а <т и b < т..
Теорема 2.7.1.4. Если p - характеристика конечного поля F= < F, +, х, 0, 1 > и m, n, k, l - натуральные числа, то
(2) (m * 1) + (n * 1) = k * 1 m + n k (mod p),
(3) (m * 1) x (n * 1) = l * 1 m * n = l (mod p).
(1) Так как p - характеристика поля F, то по теореме Лагранжа
Отсюда и из (1) следует (2). Аналогично доказывается утверждение (3).
Теорема 2.7.1.5. Всякое конечное простое поле F = < F, +, х, 0, 1 > характеристики p изоморфно кольцу классов вычетов кольца Z целых чисел по простому модулю р.
Доказательство. Любое подполе поля F содержит элементы
0 = 0 * 1, 1 = 1 * 1, 2 * 1, ..., (p - 1) * 1 (2.7.1.5)
В силу теоремы 2.7.1.4 сумма, разность, произведение любых элементов ряда (2.7.1.5) и обратный элемент к любому ненулевому элементу этого множества принадлежат тому же множеству. Поэтому множество элементов (2.7.1.5) относительно операций "+" и "х" образует подполе поля F, а так как F простое поле (т. е. поле, не содержащее других подполей, кроме самого поля F), то это подполе совпадает с полем F.
Определим отображение , множества (2.7.1.5) на множество классов вычетов кольца целых чисел Z по простому модулю p условием:
Легко проверить, что - взаимно однозначное отображение, которое сумму и произведение элементов поля F переводит в сумму и произведение образов этого отображения.
Теорема 2.7.1.6. Всякое конечное поле F характеристики p содержит простое подполе из p элементов и является его конечным расширением.
Доказательство. По теореме 2.7.1.2 характеристика простого подполя поля F равна р. Но конечное поле заведомо является конечным расширением любого своего подполя.
Теорема 2.7.1.7. Число элементов конечного поля Н = Fq характеристики p есть степень его характеристики.
Доказательство. Пусть F p - простое подполе поля H. По теореме 2.7.1.6 поле Н содержит элементы h 1 , h 2 , …, h n (базис), такие, что любой элемент h поля Н однозначно представляется в виде
h = a 1 * h 1 + a 2 * h 2 + … + a n * h n ,
где a 1 , a 2 , …, a n - элементы поля Fp. Но число разных наборов < a 1 , a 2 , …, a n > элементов поля Fp равно p n . Поэтому q = p n .
Теорема 2.7.1.8. Пусть Н - поле характеристики p; k N; a, b Н. Тогда
Доказательство. Докажем первое утверждение теоремы индукцией по k. При k = 1 имеем
А так как p - простое число, то при 1 n р-1
Так как (a - b) p = (a + (-b)) p = a p + (-b) p , то второе утверждение теоремы для нечетного p очевидно, а для p = 2 легко выводится, поскольку 1 = -1. Остальные утверждения теоремы проверяются непосредственно.
Теорема 2.7.2.1. Если p - простое число, n - натуральное число, q = p n , то поле разложения Н над полем Fp многочлена х q - х есть конечное поле из q элементов.
Доказательство. Полагаем f = x q - x. Если x и y - корни многочлена f, то, как легко проверить, пользуясь теоремой 2.7.1.8, сумма, разность, произведение и частное (при y0 ) также являются корнями того же многочлена. Поэтому множество корней многочлена f является подполем поля Н. В силу теоремы 2.7.1.1 Поэтому производная многочлена f и сам многочлен f взаимно просты. Отсюда следует, что его корни все различны.
Теорема 2.7.2.2. Для любого натурального n и простого p существует конечное поле из p n элементов.
Доказательство. Следует из теоремы 2.7.2.1.
2.7.3 Мультипликативная группа конечного поля
Теорема 2.7.3.1. Если F q =- конечное поле, a F q , a 0, то
Доказательство. Равенство следует из теоремы Лагранжа, так как q-1 - число элементов мультипликативной группы поля F q .
Определение. Пусть F q = < F q , +, x, 0, 1 > - конечное поле; a F q , a 0.
Наименьшее натуральное число с условием
называют порядком элемента а поля F p .
Обозначение. ord а - порядок элемента а.
Теорема 2.7.3.2. Если а - элемент мультипликативной группы поля F q , то:
ord а q - l и, более того, ord a | q - 1,
другими словами, порядок ненулевого элемента поля F q - делитель числа q - 1;
б) в тех же предположениях, если n - натуральное число, то
в) если n - натуральное число и а - любой элемент поля F q , то
б) Любой делитель числа q - 1 делит число q n - 1.
Замечание. Если q = p - простое число, то элемент а поля F q можно рассматривать как класс вычетов кольца Z по простому модулю p с представителем а:
Условие (2.7.3.1) в этом случае равносильно условию:
Поэтому порядок любого элемента a мультипликативной группы поля F q есть вместе с тем показатель, которому принадлежит целое число а по простому модулю р.
Теорема 2.7.3.3. Пусть а -- ненулевой элемент порядка поля F q ; n, m N. Тогда
Доказательство. В самом деле, по теореме Лагранжа
Теорема 2.7.3.4. Пусть а - ненулевой элемент порядка поля F q . Тогда элементы
Доказательство. Следует из теоремы 2.7.3.3.
Теорема 2.7.3.5. Пусть а - ненулевой элемент порядка поля F q . Тогда элементы (2.7.3.4) - суть все корни многочлена x- 1. (2.7.3.5)
Доказательство. При любом натуральном k
поэтому все элементы ряда (2.7.3.4) - корни многочлена (2.7.3.5). Но многочлен степени над полем имеет в поле не более корней.
Замечание. Утверждение теоремы 2.7.3.5, справедливое для элементов конечных полей, может быть несправедливо для элементов некоторых колец.
Пример. Рассмотрим Z/ 8 . Элемент 3 кольца классов вычетов целых чисел Z по модулю 8 имеет порядок 2. Элементы 1,2,3,7 все различны и все они корни многочлена x 2 -1 в этом кольце.
Ведем обозначение: (x y ) z будем записывать в виде (x y ) z.
Теорема 2.7.3.6. Пусть а - ненулевой элемент поля F q порядка ; k N. Тогда
Доказательство. Введем обозначение: m = ord а k . Тогда
Теорема 2.7.3.7. Если а - элемент поля F q порядка , то число всех элементов поля F, порядка равно .
Доказательство. Всякий элемент порядка поля F q есть корень многочлена x- 1. По теореме 2.7.3.5 элементы (2.7.3.4) - все корни этого многочлена. По теореме 2.7.3.6 среди них элементов порядка столько, сколько чисел, взаимно простых с среди чисел ряда 0, 1, 2, ..., - 1.
По определению функции Эйлера это число равно .
Теорема 2.7.3.8. Если - натуральный делитель числа q -1, то число элементов поля F q порядка равно , в частности, число элементов порядка q - 1 поля F q равно (q-1).
Доказательство. Обозначим символом число элементов порядка поля F q . По теореме 2.7.3.2 имеем
Но в силу тождества Гаусса для функции Эйлера
Из соотношений (2.7.3.8.1) и (2.7.3.8.3) следует, что
Теорема 2.7.3.9. Мультипликативная группа ненулевых элементов конечного поля F q циклично.
Доказательство. В самом деле, порядок такой группы равен q - 1. А по теореме 2.7.3.8
Разработка и реализация математической модели двухключевой криптосистемы дипломная работа. Программирование, компьютеры и кибернетика.
Курсовая Работа На Тему Безработица И Ее Проблемы В Рб
Сочинения Н Крымов Зимний Вечер
Реферат: Стратегия инвестиционной деятельности на Украине. Скачать бесплатно и без регистрации
Дипломная работа по теме Анализ и оценка эффективности коммерческой деятельности розничного торгового предприятия "Орбита"
Отчет По Практике Стажировке Учителя Дефектолога Рб
Дипломная работа по теме Оценка автозаправочной станции №443
Контрольная работа по теме Товароведение как научная дисциплина
Курсовая Работа На Тему Понятие, Признаки И Виды Совокупности Преступлений
Реферат: Stereotyping The Followers Of Islam Essay Research
Контрольная Работа По Морфемике 6 Класс
Курсовая работа: Использование нейросетей для построения системы распознавания речи
Ссудная Задолженность В Банковской Системе Реферат
Реферат: Инвестиционные компании Великобритании
Курсовая работа: Ответственность аудитора по рассмотрению мошенничества и ошибок в ходе аудита финансовой отчетности. Аудиторская проверка операций с нематериальными активами
Реферат: Понятие, сущность, цели, задачи и основные функции менеджмента
Дипломная работа по теме Формирование познавательного интереса у младших школьников во внеучебной воспитательной работе
Поль Эссе
Учет Бухгалтерской Прибыли Курсовая
Сочинение Репортаж Мой Город
Немое Кино Диссертация
Защищенность выборки символов - Программирование, компьютеры и кибернетика курсовая работа
Акционерные общества в Республике Беларусь - Государство и право дипломная работа
Замена судьи в гражданском процессе РФ - Государство и право курсовая работа