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.  В чём суть китайской теоремы об остатках?


 

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

50600. Импульсные стабилизаторы напряжения 143 KB
  Цель работы Изучить назначение принцип действия свойства и возможные схемотехнические решения импульсных стабилизаторов напряжения. Задание Ознакомиться с принципами построения характеристиками и свойствами импульсных стабилизаторов напряжения. Исследовать свойства импульсных стабилизаторов напряжения построенного на биполярных транзисторах.
50601. Схемотехнические решения устройств на операционных усилителях 586 KB
  Принципиальная схема простого аналогового интегратора показана на рис. На этой схеме конденсатор в цепи обратной связи ОУ подсоединен между суммирующим входом и выходом интегратора. Для определения выходного напряжения интегратора при постоянном напряжении Ui на его входе воспользуемся формулой коэффициента передачи усилителя с параллельной отрицательной обратной связью Kip = Uo Ui = Kp [1 bp Kp] 1 в которой Кр = А...
50602. Генераторы электрических колебаний 488 KB
  Зарисовать осциллограммы на выходе RCгенератора при 3х и 4х звенной фазосдвигающей цепочки. Исследовать зависимость амплитуды и частоты выходного сигнала а также периода самовозбуждения генератора от величины R и С и занести полученные значения в таб.5 кОм С мкФ 5 10 20 40 80 Um В 355 327 273 207 143 Т С 026 03 034 037 038 Гц 385 333 294 27 263 Tcв сек Исследование генератора на операционном усилителе.
50603. Пуск-Autodesk-Autodesk 3d Max 8-3d Max 8 516.5 KB
  Находится в верхней части окна программы и обеспечивает доступ к основным командам 3ds Mx 7. Обычно находится под главным меню но может отображаться как плавающая панель или располагаться в других местах окна. Viewports Окна проекций. Расположены в центре окна и занимают его большую часть.
50604. Создание геометрических примитивов. Добавление освещения в сцену 278 KB
  Установив параметры нажмите кнопку Crete Создать. В окне проекции Top Вид сверху нажмите левую кнопку мыши и не отпуская левую клавишу передвиньте мышь определяя первый радиус конуса. Расположение объектов в окне проекции Top Создайте Тор для этого: Нажмите кнопку Torus Тор на панели Cret Создать Создайте тор в окне проекции Top Вид сверху. Создайте трубу для этого: Нажмите кнопку Tube Труба на панели Cret Создать Создайте в окне проекции Top...
50605. Создание интерьера кухни с помощью примитивов 3ds Max 677.5 KB
  Например все объекты сцены на рис. Сцена созданная из примитивов 3ds Mx Цель: Смоделировав подобную сцену вы ознакомитесь с интерфейсом программы научитесь создавать объекты и производить с ними основные операции: выравнивание перемещение вращение клонирование. Научиться производить над объектами основные операции.
50606. Проблемы реализации геополитической стратегии Российской Федерацией 99 KB
  Понятие “геополитика” в современном мире рассматривается, иногда чересчур широко, что, в конечном счете, размывает характерные особенности данного явления.
50607. Создание тел вращения по профилю сечения при помощи сплайнов 923.5 KB
  Сегмент segment это участок линии сплайна между двумя соседними вершинами. Криволинейные сегменты представляются набором прямолинейных отрезков часто незаметных для глаза число которых задается при создании сплайна. Вершины vertex сплайна различаются по типу и определяют степень кривизны сегментов сплайна прилегающих к этим вершинам.
50608. Создание объектов методом Editable Mesh (Редактируемая поверхность) 879 KB
  Переключитесь в режим редактирования Polygon Полигон. Выйдите из режима редактирования Polygon Полигон выделите объект перейдите на вкладку Modify Изменение командной панели выберите из списка Modifier List Список модификаторов модификатор MeshSmooth Сглаживание. Переключитесь в режим редактирования Edge Ребро. Переключитесь в режим редактирования Vertex Вершина.