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

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

Вычисление частного и остатка от деления двух целых чисел является общей операцией в теории чисел. Библиотека стандарта 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), создайте класс вычетов. Область MuPAD Dom::IntegerMod позволяет вам создать звонок, который состоит из всех классов вычетов по модулю некоторый целочисленный 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 опция. Эта опция позволяет вам создать полином с коэффициентами, которые принадлежат IntMod(n) звонок. Здесь 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 страница справки.