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


 

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

39581. Связь политически активной студенческой молодёжи как формальность и неформальность с уровнем социальной зрелости 415 KB
  От уровня социальной зрелости зависит нравственнополитический климат и культура нынешнего и будущего общества. не гарантирует высокий уровень социальной зрелости. Эти приписываемые социальнопсихологические признаки по праву можно считать признаками социальной зрелости. Экспериментальные исследования в области социальной зрелости как правило сводятся к изучению школьников и выпускников школ.
39582. Проект электрификации телятника на 25 голов с разработкой навозоудаления в ЗАО «Красный холм» РМО 578.63 KB
  В последнее время принят ряд указов, законов, нормативных актов, которые создают благоприятные условия для развития всех форм хозяйствования на селе в условиях рыночных отношений. Реализация этих решений по выходу с/х из кризиса основана на введении новых форм организации производства
39583. Организация водоохладительной установки АВ-30 1.38 MB
  Повышение производительности труда в сельском хозяйстве а следовательно и эффективности производства возможно лишь при условии максимальной механизации и автоматизации при неуклонном сокращении доли ручного труда. Сокращение доли тяжёлого и малоквалифицированного физического труда непременное условие экономического роста. Рост технической и энергетической вооруженности сельскохозяйственного труда развитие научных исследований с использованием современной научной аппаратуры достижений полупроводниковой микроэлектроники и...
39584. Политическая социализация личности 273.14 KB
  Личность —одновременно и субъект и объект политики. Но одни люди в большей степени проявляют политическую активность, другие — в меньшей, а третьи вообще стараются «убежать» от политики. Одни стремятся к утверждению существующего политического строя и проявляют конструктивное политическое поведение, другие, напротив, предпринимают меры, направленные на его ниспровержение и демонстрируют деструктивную позицию.
39585. Социальная зрелость личности 79 KB
  Ницше Проблематикой социальной зрелости личности занимаются различные науки. И потому ее роль в исследовании социализации личности очень велика: вклад криминологии в данную проблематику состоит в том что эта наука создает модель социально НЕзрелой личности прогнозирует возможные ошибки воспитания и их последствия. Многие науки не обходят стороной социальную зрелость личности а для такой относительно новой области человекознания как акмеология от греч.
39586. Модернизация систем автоматизации контроля электрических машин 1.96 MB
  Программное обеспечение системы адаптировано для целей обучения основам спектрального анализа и ознакомления с обучающимися алгоритмами искусственного интеллекта. Программа проста в освоении и не требует специальных навыков.
39587. Барабаны ленточных конвейеров 16.6 KB
  Тяговые свойства приводного барабана повышают путем увеличения натяжения ленты или угла обхвата лентой приводного барабана использования высокофрикционных футеровок с продольными или шевронными ребрами что способствует самоочищению.Футеровки устанавливаются при помощи специальных клеев на барабаны конвейеров футеровочные пластины значительно уменьшают сход ленты и ее проскальзывание а также попадание груза на поверхность барабана что существенно улучшает работу конвейеров и повышает их техникоэкономические показатели.Рифленая...
39588. Лента конвейерная 109.87 KB
  Тяговым каркасом резинотканевой ленты рис. Резинотросовые ленты рис. имеют тяговый каркас состоящий из стальных тросов уложенных в один ряд параллельно друг другу вдоль ленты с обеих сторон покрытый резиной. Количество прокладок может быть от 3 до 10 в зависимости от условий эксплуатации свойств транспортируемого груза ширины прочности и жесткости ленты.
39589. Натяжные устройства ленточного конвейера 34.2 KB
  Грузовые натяжные устройства делятся на грузовые тележечные и грузовые вертикальные рамные. Каждое из названных натяжных устройств состоит из натяжной тележки или натяжной рамы и грузового устройства. Грузовые устройства могут быть без полиспаста с полиспастом или грузолебедочные.