Содержание
- 2. На X может быть задано, вообще говоря, много различных операций. Желая выделить одну из них, используют
- 3. Наряду с бинарными алгебраическими операциями не лишены интереса гораздно более общие n-арные операции: унарные при n=1,
- 4. ПОЛУГРУППЫ И МОНОИДЫ Бинарная операция * на множестве X называется ассоциативной, если (a*b)*c=a*(b*c) для всех a,b,c∈X
- 5. Некоторые свойства операций имеют специальные названия. Пусть задана алгебра (M, Σ) и a,b,c ∈ M, ”•“,”*”
- 6. Ассоциативные операции: сложение и умножение чисел, объединение и пересечение множеств, композиция отношений. Неассоциативные операции: возведение числа
- 7. Элемент e∈X называется единичным (или нейтральным) относительно рассматриваемой бинарной операции *, если e*x = x*e =
- 8. Элемент a моноида (M,×,e) называется обратимым, если найдется элемент b∈ M, для которого a×b=b×a=e (понятно, что
- 9. Группой называется непустое множество G с бинарной операцией * на нем, для которой выполнены следующие аксиомы:
- 10. Множество Z целых чисел образует абелеву группу относительно операции сложения. То же самое можно сказать относительно
- 11. Кольцом называется множество R с двумя бинарными операциями, обозначаемыми «+»и «•», такими, что: Простейшими примерами колец
- 14. Кольцо называется областью целостности, если оно является коммутативным кольцом с единицей и без делителя нуля. Коммутативное
- 15. Пусть область целостности R содержит единичный элемент e. Рассмотрим элемент Возможны два случая. А) не существует
- 17. Поля Основные понятия
- 18. Полем называется множество с операциями сложения и умножения, которые удовлетворяют ассоциативному, коммутативному и дистрибутивному законам, причём
- 19. Примерами являются Q - поле рациональных чисел, R - поле действительных чисел, С - поле комплексных
- 20. Число к элементов поля называется порядком поля. Различают бесконечные поля (например, множество рациональных чисел) и конечные
- 22. Отношение конгруэнтности (сравнимости) по модулю данного числа т на расширенном (включающем число 0) множестве натуральных чисел
- 23. Множество смежных классов по модулю m (или их обозначений ) с операциями сложения и умножения по
- 24. Элемент g поля называется примитивным, или образующим, если для любого другого ненулевого элемента а поля найдется
- 26. ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ Модулярная арифметика
- 27. Запись в модулярной арифметике a ≡ b (mod n) читается так: "a сравнимо с b по
- 28. Набор целых чисел от 0 до (n –1) называют полным набором вычетов по модулю n. Это
- 29. Обычно предпочитают использовать вычеты r ∈ {0, 1, 2, …, n –1}, но иногда полезны вычеты
- 30. Целые числа по модулю n с использованием операций сложения и умножения образуют коммутативное кольцо при соблюдении
- 31. Вычисление степени числа a по модулю n ax mod n можно выполнить как ряд умножений и
- 32. Вместо этого выполняют три малых умножения и три малых приведения по модулю: ((a2 mod n)2 mod
- 33. Тогда a25 mod n = (a*a24) mod n = (a*a8 *a16) mod n = = a
- 34. Алгоритм Евклида для нахождения наибольшего общего делителя Целое число a делит без остатка другое целое число
- 35. Любое целое n >1 может быть представлено единственным образом с точностью до порядка сомножителей как произведение
- 36. Наибольший общий делитель чисел a и b, обозначаемый как НОД (a,b) или просто (a,b), – это
- 37. Опишем алгоритм Евклида для нахождения НОД (a,b). Введем обозначения: qi – частное; ri – остаток. Тогда
- 38. Остановка гарантируется, поскольку остатки ri от делений образуют строго убывающую последовательность натуральных чисел. Таким образом, rn
- 39. Алгоритм Евклида для вычисления наибольшего общего делителя begin g[0]: = b; g[1]: = a; i :
- 40. Вычисление обратного элемента по заданному модулю Если целые числа а и n взаимно просты, то существует
- 41. Расширенный алгоритм Евклида При заданных неотрицательных целых числах a и b этот алгоритм определяет вектор (u1,
- 42. Для вычисления обратной величины a–1 (mod n) используется частный режим работы расширенного алгоритма Евклида, при котором
- 43. Шаги алгоритма: 1. Начальная установка. Установить (u1, u2, u3) : = (0, 1, n), (v1, v2,
- 44. Пример. Заданы модуль n = 23 и число a = 5. Найти обратное число a–1 (mod
- 45. При u3 =1, u1 = –9, u2 = 2 (a * u1 + n * u2
- 46. Малая теорема Ферма Если m – простое число, и a не кратно m ,то малая теорема
- 47. Функция Эйлера Приведенной системой вычетов по модулю п называют подмножество полной системы вычетов, члены которого взаимно
- 48. Функция Эйлера, которую иногда называют функцией «фи» Эйлера и записывают как φ(п), указывает число элементов в
- 49. В соответствии с обобщением Эйлера малой теоремы Ферма, если НОД(а,п) = 1,то: Теперь нетрудно вычислить а-1
- 50. Основные способы нахождения обратных величин a–1 (mod n). Проверить поочередно значения 1, 2, ..., n –
- 51. 2. Если известна функция Эйлера ϕ(n), то можно вычислить a–1 (mod n) ≡ aϕ(n)–1 (mod n),
- 52. Если функция Эйлера ϕ(n) не известна, можно использовать расширенный алгоритм Евклида. n=23 a=5 ExtendedGCD[n,a]
- 53. Если функция Эйлера ϕ(n) не известна, можно использовать расширенный алгоритм Евклида. n=23 a=5 ExtendedGCD[n,a] {1,{2,-9}} u3
- 54. Для решения более сложных сравнений a * x ≡ b (mod n), т.е. b ≠1, x
- 56. Скачать презентацию