67751

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

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

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

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

Русский

2014-09-14

524 KB

7 чел.

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


 

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

77397. Геотермальная энергия и методы ее преобразования 94 KB
  Одна скважина в зависимости от параметров пара или воды может обеспечить электрическую мощность от 2 до 7 МВт. Основным условием существования водяных геотермальных источников является наличие непроницаемого для воды слоя горных пород который передает тепло от мантии или магмы к формациям содержащим в больших количествах воду. Температура воды или пара в гидротермальных источниках может составлять от 30 до 300350 С и зависит от их расстояния до мантии Земли а также от близости к раскаленной или расплавленной магме. Температуры...
77398. Энергия биомассы и методы ее преобразования 102.5 KB
  Энергия биомассы и методы ее преобразования Биомасса как источник энергии. Энергетическое использование биомассы реализуется по трем основным направлениям: непосредственное сжигание биомассы древесины водорослей растений в атмосфере воздуха; извлечение из биомассы таких энергоносителей как биогаз и спирты; использование теплоты выделяемой при брожении органическими отходами навоз помет опилки и...
77399. Актуальность использования нетрадиционных и возобновляемых источников энергии 103 KB
  Актуальность использования нетрадиционных и возобновляемых источников энергии Понятие традиционной энергетики. Традиционная энергетика совокупность технических устройств использующих хорошо освоенные в технологическом отношении энергетические источники и способы преобразования получаемой от них энергии в первую очередь в электрическую. Их отличительные особенности: значительная единичная мощность; работа в общей электросети возможна работа и в тепловой сети; единый...
77400. Определение токсичных выбросов в атмосферу от объектов традиционной энергетики 142 KB
  Определяется полное количество тепла полезно использованное в паровом котле кВт 1. Значения удельной энтальпии энергоносителя определяется при известных его параметрах по таблицам теплофизических свойств воды и водяного пара. Определяется расход топлива на каждый котел установленный в тепловом источнике г с 1. Определяется расход топлива на все котлы установленные в тепловом источнике г с 1.
77401. Признание брака недействительным 44 KB
  Понятие и основания признания брака недействительным. Под признанием брака недействительным понимается аннулирование брака и всех его правовых последствий с момента его заключения. Признание брака недействительным по правовой природе санкция за нарушение требований установленных семейным законодательством.
77402. Правоотношения супругов 135.5 KB
  Личные неимущественные права и обязанности супругов. Каждый из супругов вправе выбирать место жительства место пребывания профессию и род занятий. СК не обязывает супругов проживать совместно но это более благоприятно устанавливая свободу в выборе место пребывания и места жительства предоставляет выбор и свободу жить раздельно может быть даже и весь период супружеской жизни.
77404. Правоотношение родителей и детей 168 KB
  В данном случае это происхождение ребёнка от конкретных лиц удостоверенное в установленном законом порядке. Установление происхождения ребёнка рождённого в браке. Происхождение ребёнка рождённого в браке установить довольно проще чем рождённого вне брака. Установление происхождения ребёнка рождённого в браке происходит в административном порядке.
77405. Алиментные обязательства членов семьи 75.5 KB
  Алиментное обязательство является имущественным правоотношением и средства предоставляющиеся в качестве алиментов представляют собой товар. В настоящее время алиментные обязательства могут возникать не только на основании закона но и на основании соглашения об уплате алиментов. Взаимность и возмездность в том что если родитель в своё время уклонялся от выполнения обязанности по содержанию ребёнка суд может освободить ребёнка от уплаты алиментов. Плательщик алиментов выплачивает алименты не предполагая получить какое-либо имущественное...