Иллюстрированный самоучитель по Mathematica 5

Корни в системе остаточных классов. Квадратный корень по модулю (функции SqrtMod и SqrtModList).

Задача о корзинке с яйцами представляет собой задачу о решении системы сравнений вида u=u_i(modm_i) с попарно взаимно простыми модулями mt. Конечно, она допускает дальнейшие обобщения. Если не считать линейных сравнений и их систем, то наиболее простой из таких задач окажется задача об извлечении квадратного корня в системе остаточных классов, т.е. задача о решении сравнения хr = d (modn).

Конечно, квадратных корней в системе остаточных классов – решений сравнения х =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.

Этот результат легко проверить.

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

Убедимся, например, что квадратный корень из 3 по модулю 5 не существует.

Ну и, конечно, нельзя не пройти мимо вычисления квадратного корня из 2.

Функция SqrtMod может вычислять квадратные корни не только по простому модулю, но и по составному.

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