Документация

Частные и остатки

Вычисление частного и остатка от деления двух целых чисел является общей операцией в теории чисел. Библиотека стандарта MuPAD^® обеспечивает функцию div для вычисления частного деления. Стандартная библиотека также предоставляет оператору по модулю mod для вычисления остатка от деления:

17 div 3, 17 mod 3

MuPAD поддерживает два определения остатка от деления. Первое определение утверждает, что остаток всегда является неотрицательным номером. Чтобы вычислить остаток по этому определению, используйте положительный функциональный modp по модулю или оператор по модулю по умолчанию mod:

123 mod 5, modp(123, 5)

Симметричный функциональный mods по модулю реализует альтернативное определение остатка от деления. Это определение позволяет остатку быть отрицательным. Симметричная функция по модулю сравнивает абсолютные значения отрицания и положительных остатков, и возвращает остаток, который имеет наименее абсолютное значение:

mods(122, 5), mods(123, 5)

Можно переопределить оператор по модулю mod путем присвоения mods или modp к mod:

123 mod 5;
_mod := mods:
123 mod 5

Переопределение оператора по модулю, mod не влияет на функцию div, которая вычисляет частное. Функция div всегда вычисляет частное путем предположения, что остаток должен быть неотрицательным:

123 div 5, 123 mod 5

Для дальнейших вычислений восстановите поведение по умолчанию оператора по модулю:

_mod := modp:

Теперь, предположите, что номер представлен как a ^b, где a и b являются целыми числами. Предположим, вы хотите вычислить модульную степень a ^b по c, который является остатком от деления a ^b целочисленным c. Можно вычислить модульную степень при помощи оператора по модулю mod:

987^124 mod 12

Когда вы используете оператор mod, чтобы вычислить модульную степень, MuPAD выполняет вычисления на двух шагах. Во-первых, система вычисляет степень целого числа, и затем это делит результат и находит остаток. Этот подход работает, если и номер и его степень являются маленькими. Однако, если числа являются большими, первый шаг (вычисляющий степень целого числа) может быть чрезвычайно медленным. Чтобы избежать этого шага, используйте функцию powermod. Эта функция вычисляет модульную степень более эффективно, специально для больших количеств:

powermod(987, 124, 12),
powermod(987, 123456789, 12)

Общие операции арифметики в остаточных классах

MuPAD реализует большое количество алгоритмов, которые позволяют вам выполнить различные операции арифметики в остаточных классах. Например, можно быстро вычислить первообразные корни, порядки классов вычетов и функцию тотиента Эйлера.

Если g является первообразным корнем n по модулю, то для любого целочисленного a там существует целочисленный k, таким образом что ^{gk≡ a(mod n)}. Эта конгруэтность имеет решения (первообразные корни существуют), только если igcd(a, n) = 1. Чтобы вычислить наименее первообразный корень n по модулю, используйте функцию numlib::primroot. Например, вычислите первообразные корни по модулю 19, 23, 191, и 311:

numlib::primroot(19),
numlib::primroot(23),
numlib::primroot(191),
numlib::primroot(311)

Функция numlib::order вычисляет порядок класса вычетов. Для целочисленного a и положительного целочисленного n, эта функция возвращает наименьшее количество номера k, такой что ^{ak≡ 1(mod n)}. Например, вычислите порядок класса вычетов 3 в модульной группе по модулю 7:

numlib::order(3, 7)

Функция тотиента Эйлера целочисленного n считает все положительные целые числа, которые удовлетворяют следующие два условия:

Функция тотиента Эйлера возвращает количество таких целых чисел. Чтобы вычислить функцию тотиента Эйлера в MuPAD, используйте функцию numlib::phi:

numlib::phi(i) $ i = 1..20

Для других функций арифметики в остаточных классах, доступных в MuPAD, смотрите numlib библиотеку.

Кольца классов вычетов и поля

Для этих двух целых чисел a и m, все целые числа b, такой, что a ≡ b(mod m), создают класс вычетов. Dom::IntegerMod области MuPAD позволяет вам создать звонок, который состоит из всех классов вычетов по модулю некоторый целочисленный m. Например, создайте кольцо классов вычетов целых чисел по модулю 11:

Z11:= Dom::IntegerMod(11)

Теперь, создайте элементы a и b этого звонка. Затем вычислите сумму a и b:

a:= Z11(1); b:= Z11(6); a + b

Можно использовать Dom::IntegerMod, чтобы задать полиномы по содействующему звонку. При вычислении коэффициентов полинома Dom::IntegerMod (7) использует положительный функциональный modp по модулю:

poly([[9, 3], [13, 1]], [x], Dom::IntegerMod(11))

Для определения полиномов по кольцу классов вычетов ℤ _n функция poly также предоставляет возможность IntMod. Эта опция позволяет вам создать полином с коэффициентами, которые принадлежат звонку (n) IntMod. Здесь n является целым числом, больше, чем 1. Математически, этот звонок совпадает с Dom::IntegerMod (n). Однако MuPAD управляет по-другому на полиномах, созданных по IntMod (n) и полиномами, созданными по Dom::IntegerMod (n). В частности, MuPAD выполняет арифметические операции для полиномов по звонку IntMod быстрее. Кроме того, если вы используете IntMod (n), MuPAD использует симметричный функциональный mods по модулю:

poly([[9, 3], [13, 1]], [x], IntMod(11))

Доменный Dom::GaloisField позволяет вам создать поле класса вычетов, которое является конечным полем с p элементы ⁿ. Если вы не задаете f, MuPAD случайным образом выбирает f из всех неприводимых полиномов степени n. Для получения дополнительной информации смотрите страницу справки Dom::GaloisField.