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


 

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

37926. Изучение явления термоэлектронной эмиссии и определение удельного заряда электрона 206.5 KB
  Благодаря пространственному заряду при малых анодных напряжениях анодный ток может быть значительно меньше возможного тока эмиссии катода и постепенно увеличивается при повышении анодного напряжения. Если поддерживать температуру накаленного катода постоянной и снять зависимость анодного тока Iа от анодного напряжения uа – вольт амперную характеристику рис.2 Вольт амперные характеристики диода при различных температурах T2  T1 Зависимость термоэлектронного тока Iа от анодного напряжения в области малых положительных значений uа...
37927. ИЗУЧЕНИЕ ТЕРМОЭЛЕКТРОННОЙ ЭМИССИИ МЕТАЛЛОВ. ОПРЕДЕЛЕНИЕ РАБОТЫ ВЫХОДА ЭЛЕКТРОНА 98 KB
  Сила термоэлектронного тока в диоде зависит от величины напряжения U рис. Отклонение зависимости анодного тока IА от анодного напряжения U от прямолинейной связано: а с наличием в промежутке между катодом и анодом неоднородной области пространственного заряда; б с отсутствием центров рассеяния в упомянутом промежутке. Зависимость тока диода IА от анодного напряжения U имеет вид: I=C U3 2 2.3 Is – величина тока насыщения три кривые относятся к трем разным...
37928. Изучение процессов заряда и разряда конденсатора 452 KB
  12 Лабораторная работа № 37 Изучение процессов заряда и разряда конденсатора 1. Цель работы Целью данной работы является изучение заряда и разряда конденсатора при различных параметрах электрической цепи и вычисление времени релаксации. В качестве примера квазистационарных токов рассмотрим процессы заряда и разряда конденсатора в электрической цепи содержащей последовательно соединенные конденсатор С сопротивление R включающие и внутреннее сопротивление источника и источник ЭДС ε рис. Пусть I q U – мгновенные значения тока заряда и...
37929. Изучение электрических свойств твердых диэлектриков 259.5 KB
  Типы диэлектриков Диэлектриками называются вещества которые при обычных условиях практически не проводят электрический ток. Согласно представлениям классической физики в диэлектриках в отличие от проводников нет свободных носителей заряда – заряженных частиц которые могли бы под действием электрического поля прийти в упорядоченное движение и образовать электрический ток проводимости. К диэлектрикам относятся все газы если они не подвергались ионизации некоторые жидкости дистиллированная вода бензол и др. Все молекулы диэлектрика...
37930. Определение электродвижущей силы 377 KB
  Эти частицы называют носителями тока. За положительное направление тока выбрано направление движения положительно заряженных частиц. Если бы в электрической цепи действовали только электростатические силы то положительные носители тока под действием этих сил перемещались бы от большего потенциала к меньшему и таким образом снижали больший и повышали меньший потенциал. Это привело бы к выравниванию потенциала во всех точках проводника и прекращению тока.
37931. ИЗУЧЕНИЕ ГАЗОВОГО РАЗРЯДА 946 KB
  Цель работы Изучение газового разряда измерение вольтамперной характеристики газонаполненной лампы изучение релаксационных колебаний.2 Газонаполненные лампы часто используют для получения релаксационных колебаний. Принципиальная схема генератора релаксационных колебаний полказана на рисунке 2. При нажатой кнопке режим получается схема генератора релаксационных колебаний смотри рисунок 2.
37932. ИЗУЧЕНИЕ ДИЭЛЕКТРИЧЕСКИХ СВОЙСТВ СЕГНЕТОЭЛЕКТРИКОВ 1.1 MB
  Цель работы Изучение поляризации сегнетоэлектриков в зависимости от напряженности электрического поля E получение кривой E = fE изучение диэлектрического гистерезиса определение диэлектрических потерь в сегнетоэлектриках. Это связано с тем что они не содержат зарядов способных направленно перемещаться под действием электрического поля. Внешнее электрическое поле либо упорядочивает ориентацию жестких диполей ориентационная поляризация в диэлектриках с полярными молекулами либо приводит к появлению полностью упорядоченных...
37933. ОПРЕДЕЛЕНИЕ ЭДС ИСТОЧНИКА ТОКА С ПОМОЩЬЮ ЗАКОНА ОМА 199 KB
  Контрольные вопросы 11 Список литературы 11 ЛАБОРАТОРНАЯ РАБОТА № 45 ОПРЕДЕЛЕНИЕ ЭДС ИСТОЧНИКА ТОКА С ПОМОЩЬЮ ЗАКОНА ОМА Цель работы.1 Закон Ома Количественной мерой электрического тока служит сила тока скалярная величина определяемая электрическим зарядом проходящим через поперечное сечение проводника в единицу времени: . Для постоянного тока . Единица силы тока ампер 1 А = Кл с.
37934. Движения заряженных частиц в магнитном поле. Определение удельного заряда электрона методом магнетрона 365 KB
  Действие магнитного поля на движущийся заряд. Действие магнитного поля на движущийся заряд. Процесс взаимодействия магнитных полей исследовался Лоренцем который вывел формулу для расчета силы действующей со стороны магнитного поля на движущуюся заряженную частицу.2 Тогда на n движущихся зарядов со стороны магнитного поля действует сила равная .