67751

АРИФМЕТИКА ОСТАТКОВ

Лабораторная работа

Математика и математический анализ

Для произвольного приведённого многочлена ненулевой степени над полем кольцом многочленов по модулю называется множество всех многочленов над этим полем, степени которых не превышают степень самого многочлена, с операциями сложения и умножения многочленов по модулю.

Русский

2014-09-14

524 KB

6 чел.

PAGE   \* MERGEFORMAT 4

Лабораторная работа № 5

Тема: АРИФМЕТИКА ОСТАТКОВ

Цель работы – освоение методики исследования сравнений, исходя из сравнений по делителям модуля.

Краткие теоретические сведения.

1. Сравнения. Кольцо классов вычетов по данному модулю.

Целое число  называется сравнимым с целым числом  по модулю , если разность  делится на . Этот факт обозначают так: .

Следующие утверждения эквивалентны:

  1.  целые числа  и  сравнимы по модулю : ;
  2.  целые числа  и  при делении их на натуральное число  дают один и тот же остаток ;
  3.  целые числа  и  связаны соотношением: , где , .

Сравнения по одному модулю можно почленно складывать, вычитать и перемножать.

Множество чисел с одинаковым остатком при делении на  образует класс вычетов по модулю

Число  называется представителем данного класса вычетов, произвольный элемент  из  называется вычетом.

Классы вычетов по данному модулю образуют разбиение множества .

Если взять по одному представителю из каждого класса вычетов по модулю , то эти  чисел образуют полную систему вычетов по модулю . Чаще всего используется полная система наименьших неотрицательных вычетов: . Чтобы получить такую систему вычетов, нужно выписать все остатки от деления целых чисел на .

Множество классов вычетов по модулю  образует коммутативное кольцо с единицей. Обозначается . Если модуль  – простое число, то – поле, а если число  – составное, то  не является полем.

Для нахождения обратных элементов в кольце  используется расширенный алгоритм Евклида.

2. Кольцо классов вычетов многочленов над полем

Для многочленов над полем, как и для чисел, можно ввести понятие сравнения.

Пусть , ,  – многочлены из . Многочлен  называется сравнимым с многочленом  по модулю многочлена , если разность  делится на . Этот факт обозначают так:

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

Для произвольного приведённого многочлена  ненулевой степени над полем  кольцом многочленов по модулю  называется множество всех многочленов над этим полем, степени которых не превышают степень самого многочлена , с операциями сложения и умножения многочленов по модулю . Обозначают . Кольцо многочленов  по модулю  будет полем тогда и только тогда, когда многочлен  – нормированный и неприводимый.

Если многочлен  неприводим, то остатки от деления всех многочленов из  на  образуют поле  относительно операций сложения и умножения многочленов с коэффициентами из . Поле  является расширением . Количество его элементов равно . Чтобы это подчеркнуть, иногда такие поля обозначают . Равенство в поле  является сравнением вида . Элемент, обратный  вычисляется как многочлен  из уравнения , поскольку все многочлены степени меньшей  взаимно просты с .

3. Функция Эйлера и её свойства

Функция Эйлера  ставит в соответствие любому натуральному числу  количество натуральных чисел, меньших  и взаимно простых с .

Общая формула для вычисления значения функции Эйлера от произвольного аргумента: если , где  – простое число, , то

.

Если  – простое число, то .

Если – каноническое разложение натурального числа , то

.

Теорема Эйлера. Если , то .

Теорема Ферма. Если  – простое число и , то .

4. Линейные сравнения с одним неизвестным.

Линейной сравнением или сравнением первой степени с одним неизвестным называется сравнение вида .

Решить сравнение – значит найти все те , которые удовлетворяют данному сравнению, при этом весь класс вычетов  считается одним решением. Сравнения вида  могут иметь несколько решений, иметь единственное решение или не иметь решений вовсе. Если , то решение единственно: .

Заметим, что если модуль и коэффициенты сравнения разделить или умножить как целые числа на одно и то же число, то полученное сравнение будет истинным. Это следует из того, что если  делится на , а делится на , то  делится на .

Теорема. Сравнение  разрешимо тогда и только тогда, когда  (НОД  делит ). При этом существует  классов решений .

В частности, если – простое число, то сравнение всегда имеет единственное решение (кроме случая ).

Алгоритм решения линейного сравнения

  1.  Решаем соответствующее диофантово уравнение  с помощью расширенного алгоритма Евклида.

Если ,то сравнение не имеет решений.

  1.  В качестве  возьмем любое найденное на шаге 1 решение диофантова уравнения. Добавляя к  последовательно , получим все решения.

5. Китайская теорема об остатках.

Следующее утверждение называется китайской теоремой об остатках.

Если в системе линейных сравнений

модули  попарно взаимно просты, то система имеет единственное решение:

,

где  – наименьшее общее кратное модулей.  .

Действительно, в указанном выражении для  одно слагаемое сравнимо с  по модулю , а все прочие сравнимы с нулем.

Заметим, что коэффициенты  можно вычислить заранее и решать несколько систем, подставляя их правые части в линейную форму.

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

Таким образом, отдельное решение сравнения по факторизованному модулю можно свести к решению сравнений по меньшим модулям, которые решить легче, хотя бы  перебором.

6. Степенные сравнения.

Важной задачей, имеющей приложения в криптографии, является решение степенных сравнений вида .

Пусть  – первообразный элемент простого поля (образующий мультипликативной группы поля). Тогда существуют числа  и , такие что , , поэтому . Поскольку , то . Свойства последнего сравнения полностью характеризуют разрешимость исходного. Любое его решение  приводит к решению  сравнения .

Очевидно, при больших значения переменных, решению задачи препятствует необходимость явного представления числа  в виде .

Можно показать, что разрешимость сравнения  эквивалентна выполнению условия , где . Если сравнение разрешимо, то число решений равно

Кроме того, если  – простое, , , то сравнение  имеет решений.

Порядок выполнения работы.

1. Изучите краткие теоретические сведения.

2. Найдите класс вычетов, обратный классу:

1) ;  6) ;   11) ;   16) ;  21) ;

2) ;  7) ;   12) ;  17) ;  22)

3) ;  8) ;   13) ;  18) ;  23)

4) ;  9) ;   14) ;  19) ;  24) ;

5) ;  10) ;  15) ;  20) .  25) .

3. Постройте множество вычетов по модулю  для всех степеней вида  при .

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

7

8

5

6

3

5

7

8

7

4

6

3

5

7

6

8

6

7

4

8

5

3

4

1

2

1

2

2

3

2

3

1

2

4

2

5

4

6

1

1

21

22

23

24

25

7

6

4

8

5

1

5

3

4

3

4. Найдите все решения сравнения .

1

6

3

27

6

            

15

18

11

8

5

11

16

7

2

13

2

5

15

25

7

5

1

8

12

25

8

29

17

25

15

17

3

2

4

9

8

14

4

20

13

3

7

14

18

9

7

14

4

3

9

12

9

4

2

10

14

29

3

12

19

5

8

14

5

6

9

15

10

5

7

21

15

7

8

15

20

5

2

8

21

8

4

14

22

5

6

9

23

10

6

22

24

4

10

26

25

7

3

11

5. Решите сравнение  с помощью китайской теоремы об остатках, исходя из известной факторизации модуля.

1

11

3

105

6

9

15

65

11

8

3

187

16

6

11

95

2

2

15

35

7

5

1

78

12

9

4

91

17

12

5

102

3

7

4

66

8

14

4

93

13

2

5

161

18

4

9

58

4

11

9

133

9

7

2

80

14

7

2

66

19

10

7

51

5

6

5

77

10

2

7

16

15

3

6

145

20

7

3

209

21

5

8

143

22

9

4

231

23

7

13

165

24

11

6

30

25

3

9

70

6. Укажите число решений сравнения .

1

2

3

5

6

4

2

3

11

8

3

5

16

2

4

3

2

5

7

3

7

2

7

3

12

9

4

11

17

7

5

2

3

2

5

7

8

4

9

3

13

2

5

5

18

7

3

3

4

5

2

7

9

4

8

5

14

7

2

13

19

10

7

5

5

4

5

7

10

5

7

7

15

3

6

5

20

4

9

3

21

3

15

13

22

2

3

7

23

4

15

11

24

2

8

5

25

2

3

7

7. Составьте отчет, приобщив полученные результаты.

Требования к отчету.

В отчете должны быть приведены:

1. Краткие сведения об изученных свойствах сравнений.

2. Решения своего варианта с необходимыми пояснениями.

3. Ответы на контрольные вопросы.

Контрольные вопросы.

  1.  Что такое сравнение?
  2.  Что такое вычет?
  3.  Какая система вычетов называется полной?
  4.  Если обе части сравнения и модуль сравнения разделить на число большее единицы, то является ли полученное сравнение эквивалентным исходному?
  5.  Как построить поле на базе кольца вычетов целых чисел по данному модулю?
  6.  Как построить поле на базе кольца многочленов?
  7.  Что такое линейное сравнение? Как его решить?
  8.  В чём суть китайской теоремы об остатках?


 

А также другие работы, которые могут Вас заинтересовать

32430. Направления в области ЗИ от НСД , Показатели защищенности СВТ, порядок оценки класса защищенности СВТ, понятие и подсистемы АС , Классификация СВТ и АС по уровню защищенности от НСД 1.07 MB
  Первое связано с СВТ второе с АС. СВТ средства вычислительной техники. СВТ совокупность программ и технических элементов систем обработки данных способная функционировать как самостоятельно так и в составе других систем.
32431. Классификация СЗИ по уровню контроля отсутствия недекларируемых воздействий 20.5 KB
  Классификация распространяется на ПО предназначенное для защиты информации ограниченного доступа. Для ПО используемого при защите информации отнесенной к государственной тайне должен быть обеспечен уровень контроля не ниже третьего. Самый высокий уровень контроля первый достаточен для ПО используемого при защите информации с грифом ОВ. Второй уровень контроля достаточен для ПО используемого при защите информации с грифом CC.
32432. Биометрические методы идентификации 19.11 KB
  Располагается на расстоянии 50 см и сравнивает ткани вокруг зрачка Стандарты биометрической аутентификации можно разделить на несколько иерархических категорий: I Стандарты определяющие требования для систем использующих биометрические технологии II Стандарты определяющие требования к процедуре использования биометрического распознавания в различных областях III Стандарты определяющие программный интерфейс PI для разработки биометрических систем IV Стандарты определяющие единый формат биометрических данных V Стандарты представления и...
32433. Электронные идентификаторы iButton 21.32 KB
  Все iButton имеют ПЗУ где хранится информация в виде поликремниевых проводников что не требует энергии для хранения. Это ПЗУ содержит 6 байтовый серийный номер уникальный. Таблетки DS 2404S01 двухпортовая память содержит 64битную память ПЗУ. Группы: Для работы с содержимым ПЗУ.
32434. Secret Net5.0-C, архитектура СЗИ НСД, состав семейства, администрирование системы и пользователей, организация разграничения доступа, контроль целостности, аудит 4.13 MB
  0C архитектура СЗИ НСД состав семейства администрирование системы и пользователей организация разграничения доступа контроль целостности аудит.Разграничение доступа и зашиты ресурсов.Разграничение доступа к устройствам компьютера. Механизм разграничения доступа к устройствам РДУ предназначен для разграничения доступа к устройствам с целью предотвращения несанкционированной утечки информации с защищаемого компьютера.
32435. Электронные ключи 16.58 KB
  На базе программируемых логических матриц Реализуют функцию x и y могут представлять последовательность чисел Электронные ключи энергозависимой программируемой памятью имеется возможность дистанционного перепрограммирования ключей. Возможность усиленной защиты за счет встраиваемой функции. Возможность защиты от НСД к данным за счет их шифрования с использованием параметров электронного ключа. Возможность выбирать схему защиты.
32437. НЕПРЕРЫВНЫЕ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ 157.5 KB
  Пусть Х случайная величина с функцией распределения Fx. Если функция распределения дифференцируема то ее производная Fx = fx называется плотностью распределения а сама случайная величина Х непрерывно распределенной случайной величиной. Отсюда следует что функция распределения непрерывной случайной величины является первообразной от плотности распределения: Утверждение 8. Вероятность того что случайная величина Х принимает значения из отрезка [а b] равна интегралу по этому отрезку от плотности распределения случайной величины Х.
32438. CИCТЕМЫ СЛУЧАЙНЫХ ВЕЛИЧИН 144.5 KB
  CИCТЕМЫ СЛУЧАЙНЫХ ВЕЛИЧИН. РАСПРЕДЕЛЕНИЕ СИСТЕМЫ СЛУЧАЙНЫХ ВЕЛИЧИН. Пусть Х = Х1 Х2Хn совокупность или система случайных величин. Функцией распределения системы случайных величин называется вероятность совместного выполнения неравенств k = 1 2 .