вычет в теории чисел
Модульная арифметика
2.2. Модульная арифметика
Операции по модулю
Как показано на рис. 2.9, оператор по модулю ( mod ) выбирает целое число ( a ) из множества Z и положительный модуль ( n ). Оператор определяет неотрицательный остаток ( r ).
Мы можем сказать, что
Найти результат следующих операций:
Система вычетов: Zn
Сравнения
Рисунок 2.11 показывает принцип сравнения. Мы должны объяснить несколько положений.
Система вычетов
Круговая система обозначений
Операции в Zn
Выполните следующие операторы (поступающие от Zn ):
а. Сложение 7 и 14 в Z15
б. Вычитание 11 из 7 в Z13
в. Умножение 11 на 7 в Z20
Ниже показаны два шага для каждой операции:
Выполните следующие операции (поступающие от Zn ):
a. Сложение 17 и 27 в Z14
b. Вычитание 43 из 12 в Z13
Ниже показаны два шага для каждой операции:
Свойства
Первое свойство: (a + b) mod n = [(a mod n) + (b mod n)] mod n
Третье свойство: (a x b) mod n = [(a mod n) x (b mod n)] mod n
Рисунок 2.14 показывает процесс до и после применения указанных выше свойств. Хотя по рисунку видно, что процесс с применением этих свойств более длинен, мы должны помнить, что в криптографии мы имеем дело с очень большими целыми числами. Например, если мы умножаем очень большое целое число на другое очень большое целое число, которое настолько большое, что не может быть записано в компьютере, то применение вышеупомянутых свойств позволяет уменьшить первые два операнда прежде, чем начать умножение. Другими словами, перечисленные свойства позволяют нам работать с меньшими числами. Этот факт станет понятнее при обсуждении экспоненциальных операций в последующих лекциях.
Следующие примеры показывают приложение вышеупомянутых свойств.
ВЫЧЕТ
Смотреть что такое «ВЫЧЕТ» в других словарях:
ВЫЧЕТ — ВЫЧЕТ, вычета, муж. 1. Действие по гл. вычесть вычитать во 2 знач. Произвести вычет из зарплаты. 2. Вычтенная, удержанная при вычете сумма денег. Вычет составляет двадцать рублей. Большой вычет. Толковый словарь Ушакова. Д.Н. Ушаков. 1935 1940 … Толковый словарь Ушакова
вычет — за вычетом.. Словарь русских синонимов и сходных по смыслу выражений. под. ред. Н. Абрамова, М.: Русские словари, 1999. вычет удержание, вычитание, скидка, сбавка, остаток; дизажио Словарь русских синонимов … Словарь синонимов
ВЫЧЕТ — ВЫЧЕТ, вычетный, см. вычитывать. Толковый словарь Даля. В.И. Даль. 1863 1866 … Толковый словарь Даля
Вычет — изъятие финансовых средств из облагаемой налогом суммы. По английски: Deduction Синонимы английские: Charge off См. также: Объекты налогообложения Финансовый словарь Финам … Финансовый словарь
ВЫЧЕТ — ВЫЧЕТ, а, муж. 1. см. вычесть. 2. Вычтенная, удержанная сумма. Небольшие вычеты. • За вычетом кого (чего), предл. с род. за исключением, кроме кого чего н. Явились все за вычетом заболевших. Толковый словарь Ожегова. С.И. Ожегов, Н.Ю. Шведова.… … Толковый словарь Ожегова
вычет — остаток (от деления) — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации Синонимы остаток (от деления) EN residue … Справочник технического переводчика
ВЫЧЕТ — аналитической функции f(z) одного комплексного переменного в конечной изолированной особой точке аоднозначного характера коэффициент при в разложении Лорана функции f(z) (см. Лорана ряд).в окрестности точки а, или равный ему интеграл где… … Математическая энциклопедия
вычет — а; м. 1. к Вычесть вычитать (2 зн.). 2. Сумма, удержанная, вычтенная из денег, предназначенных к выдаче. ◊ За вычетом. За исключением. * * * вычет в теории чисел. Число а называется вычетом числа b по модулю m, если разность а b делится на m (а,… … Энциклопедический словарь
Вычет — (перевод лат. residuum, буквально: остаток) в математике имеет несколько значений: Вычет в теории чисел элемент кольца вычетов. Вычет функции в комплексном анализе коэффициент при степени в ряде Лорана для данной функции. Вычет в финансовых… … Википедия
Вычет — 1) в теории чисел. Число а называется вычетом числа b по модулю m, если разность а b делится на m (a, b, m > 0 целые числа). Например, число 24 есть В. числа 3 по модулю 7, так как 24 3 делится на 7. Совокупность m целых чисел, каждое из… … Большая советская энциклопедия
Полная система вычетов
Как известно из статьи «Сравнение чисел по модулю»), всякое число 1 ) a сравнимо со своим вычетом r по модулю p (p положительное целое число). Следовательно число a сравнимо с одним из чисел
и, притом, только с одним, потому что в противном случае между этими числами нашлось бы по крайней мере два числа, сравнимых по модулю p, что невозможно (Свойство 2 статья «Сравнение чисел по модулю»).
Разделим все числа на классы, относя к одному классу все те числа, которые сравнимы между собой по модулю p. Число таких классов равно p. Один из классов содержит числа сравнимые с 0 по mod p, т.е. все числа кратные p, другой − все числа сравнимые с 1 по mod p и т.д.
Возьмем по одному числу от каждого из этих классов. Тогда образуется система p чисел, имеющая то свойство, что каждое число сравнимо только с одним из этих p чисел по модулю p.
В качестве такой системы можно взять
или же любые последовательные p числа.
Данная система называется полною системою чисел, не сравнимых по модулю p или же полною системою вычетов по модулю p. Очевидно, что всякие p последовательных чисел образуют такую систему.
Все числа, принадлежащих к одному классу, имеют много общих свойств, следовательно по отношению к модулю их можно рассматривать как одно число. Каждое число, входящее в сравнение как слагаемое или множитель, может быть заменено, без нарушения сравнения, числом, сравнимым с ним, т.е. с числом, принадлежащим к одному и тому же классу.
Другой элемент, который является общим для всех чисел данного класса, является наибольший общий делитель каждого элемента этого класса и модуля p.
Пусть a и b сравнимы по модулю p, тогда
где s некоторое целое число. Тогда каждый делитель a и b должны быть делителями чисел b и p и обратно. Следовательно исходя из наибольшего общего делителя, эти классы можно разделить на группы, и т.к. числа
образуют полную систему чисел, не сравнимых по модулю p, то число классов, члены которых имеют с модулем p наибольший общий делитель λ (p=nλ) равно φ(n). В частном случае, при λ=1 число соответствующих классов равно φ(p) (см. статью «Функция Эйлера»).
Теорема 1. Если в ax+b вместо x подставим последовательно все p членов полной системы чисел
не сравнимых по модулю p, то при a и p взаимно простых чисел получим опять полную систему чисел, не сравнимых по модулю p.
но, т.к. a и p взаимно простые числа, то
Поэтому все числа ax+b, где x=1,2. p-1 не сравнимы по модулю p (в противном случае, числа 1,2. p-1 были бы сравнимы по модулю p.
Примечания
1 ) В данной статье под словом число будем понимать целое число.
ВЫЧЕТ
При m=1 (простой полюс) эта формула принимает вид
если регулярны в окрестности точки а, причем для точка аесть простой нуль, то
В. применяются к вычислению нек-рых определенных интегралов от действительных функций, таких, напр., как
т. е. к вычислению В.;
если f (z) удовлетворяет условиям Жордана леммы.
вычет-класс и формула В.
— разложение апо этой базе, то обобщение теоремы о В. имеет вид
Многомерные аналоги логарифмич. В. (см. [4], [12]) выражают число общих нулей (с учетом их кратностей) системы голоморфных функций в области через интегралы:
Лит.:[1]Маркушевич А. И., Теория аналитических функций, 2 изд., т. 1, М., 1967; [2] Евграфов М. А., Аналитические функции, 2 изд., М., 1968; [3] Привалов И. И., Введение в теорию функций комплексного переменного, 11 изд., М., 1967; [4] Шабат Б. В., Введение в комплексный анализ, М., 1969; [5] Спрингер Д., Введение в теорию римановых поверхностей, пер. с англ., М., 1960; [6] Роinсаre Н., «Acta math.», 1887, t. 9, 321-380; [7] Лере Ж., Дифференциальное и интегральное исчисления на комплексном аналитическом многообразии, пер. с франц., М., 1961; [8] Фукс Б. А., Введение в теорию аналитических функций многих переменных, М., 1962; [9] Южаков А. П., «Изв. ВУЗов. Матем.», 1964, М 5 (42), с. 149-61; [10] Gritfits P. A., «Ann. Math.», 1969, v. 90, № 3,p. 460-95; [11] Егорычев Г. П., Южаков А. П., «Сиб. матем. ж.», 1974, т. 15, № 5, 1049-60; [12] Южаков А. П., Элементы теории многомерных вычетов, Красноярск, 1975. А. П. Южаков.
ВЫЧЕТ Число
Смотреть что такое «ВЫЧЕТ Число» в других словарях:
СТЕПЕННОЙ ВЫЧЕТ Число — СТЕПЕННОЙ ВЫЧЕТ в теории чисел. Число a называется вычетом степени n?2 по модулю m (a n, m 0 целые числа), если существует целое число x, такое, что разность xn a делится на m. В противном случае a называется невычетом степени n. Напр., 2 и 3… … Большой Энциклопедический словарь
Вычет (комплексный анализ) — У этого термина существуют и другие значения, см. Вычет. В комплексном анализе вычетом заданного объекта (функции, формы) называется объект (число, форма или когомологический класс формы), характеризующий локальные свойства заданного. Содержание… … Википедия
вычет — а; м. 1. к Вычесть вычитать (2 зн.). 2. Сумма, удержанная, вычтенная из денег, предназначенных к выдаче. ◊ За вычетом. За исключением. * * * вычет в теории чисел. Число а называется вычетом числа b по модулю m, если разность а b делится на m (а,… … Энциклопедический словарь
ВЫЧЕТ — аналитической функции f(z) одного комплексного переменного в конечной изолированной особой точке аоднозначного характера коэффициент при в разложении Лорана функции f(z) (см. Лорана ряд).в окрестности точки а, или равный ему интеграл где… … Математическая энциклопедия
Вычет — 1) в теории чисел. Число а называется вычетом числа b по модулю m, если разность а b делится на m (a, b, m > 0 целые числа). Например, число 24 есть В. числа 3 по модулю 7, так как 24 3 делится на 7. Совокупность m целых чисел, каждое из… … Большая советская энциклопедия
ВЫЧЕТ — в теории чисел. Число а наз. вычетом числа b по модулю т, если разность а b делится на т (а, b, т > 0 целые числа). В противном случае а наз. невычетом. Напр., число 24 есть В. числа 3 (а число 25 невычет) по модулю 7, т.к. 24 3 = 21 делится на 7 … Естествознание. Энциклопедический словарь
степенной вычет — в теории чисел. Число а называют вычетом степени n≥2 по модулю т (а, n, m> 0 целые числа), если существует целое число х такое, что разность xn а делится на m. В противном случае а называют невычетом степени n. Например, 2 и 3 соответственно… … Энциклопедический словарь
Степенной вычет — или вычет степени n по модулю m (n целое число, большее единицы, m целое число). Такое число а, для которого Сравнение xn а (modm) разрешимо. В частности, при n = 2 С. в. называется квадратичным вычетом (См. Квадратичный вычет), при n = 3 … Большая советская энциклопедия