Алгебра в программе Mathematica


Квадратный корень по модулю — функции SqrtMod и SqrtModList



Квадратный корень по модулю — функции SqrtMod и SqrtModList



Конечно, квадратных корней в системе остаточных классов — решений сравнения х =d (mod n) — может быть более одного. Поэтому в системе Mathematica предусмотрено две функции для нахождения таких решений. Функция SqrtMod находит наименьший вычет, а функция SqrtModList — Список всех вычетов.

Наименьший квадратный корень по модулю — функция SqrtMod

Выражение SqrtMod[d, n] представляет собой наименьший неотрицательный квадратный корень из d по модулю n, т.е. такой наименьший неотрицательный вычет m, что m2sd(modn). Но это, конечно, в том случае, если такое т существует. Для этого d, понятно, должно быть полным квадратом по модулю и, т.е. символ Якоби .jacobiSymbol [d, n] должен быть равным 1. Это условие также достаточно, если и является простым числом. Для простых n система Mathematica использует алгоритм Шенкса (Shanks). Для примера найдем самое маленькое неотрицательное целое число, такое, что его квадрат равен 3 по модулю 11.
SqrtMod[3,11] 5
Этот результат легко проверить.

Mod[Range[11]^2,11]

{1,4,9,5,3,3,5,9,4,1,0}

Как видите, только квадраты чисел 5 и 6 по модулю 11 равны 3. Если квадратный корень из d по модулю п не существует, SqrtMod [d, n] останется невычисленным.









Начало  Назад  Вперед