Решение квадратного уравнения конгруэнции в Mathematica

Question

Чтобы решить

   x^2 == 123456 mod 1299709 

в Mathematica, я использовал:

  Reduce[x^2 == 123456 + 1299709 k, {x, k}, Integers]

, что дает правильный ответ.

Вопрос: Есть Уменьшить лучший способ (производительность, элегантность или иное) для решения квадратичных уравнений конгруэнции?

Answer 1

Очевидно, вы ищете вариант Modulus.

Reduce[x^2 == 123456, x, Modulus -> 1299709]

(*Out[]=  x == 427784 || x == 871925 *)

Цитирование документации:

Модуль ->n
- это опция, которая может быть задана в некоторых алгебраических функциях, чтобы указать, что целые числа должны обрабатываться по модулю n.

• Уравнения для модуля можно задавать в Solve и связанных с ним функциях.

• Модуль появляется как опция в Factor, PolynomialGCD и PolynomialLCM, а такжекак в функциях линейной алгебры, таких как Inverse, LinearSolve и Det.

• Арифметика обычно выполняется над полным кольцом ℤ целых чисел;установка параметра Modulus указывает, что вместо этого арифметика должна выполняться в конечном кольце ℤ _n .

• Параметр Modulus-> 0 указывает полное кольцо ℤ целых чисел.

• Некоторые функции требуют, чтобы модуль был установлен на простое число или степень простого числа.10 _n - конечное поле, когда n простое.

Answer 2

In[1]:= PowerModList[123456, 1/2, 1299709]
Out[1]= {427784, 871925}

Даниэль Лихтблау