Функции для решения квадратичных сравнений. Реализация в MATLAB

[halyavin]

А почему возвращаются только два корня? У 1 по модулю 8 есть 4 квадратных корня. А если a и p не взаимнопросты, их может быть астрономически много.

После разложения на множители, нужно искать квадратный корень не по модулю простых чисел, а по модулю степеней простых чисел. Для этого после нахождения квадратного корня по модулю простого числа нужно выполнить подъем Гензеля.

[Sany_KENT]

С 1 по модулю 8 действительно неувязка вышла, не учтен такой вариант в функции. Также не учел случай, когда а и р не взаимно простые числа — виноват, но поясните пожалуйста, к какому случаю относятся упомянутые вами действия:

После разложения на множители, нужно искать квадратный корень не по модулю простых чисел, а по модулю степеней простых чисел. Для этого после нахождения квадратного корня по модулю простого числа нужно выполнить подъем Гензеля.

Также благодарю, за конструктивную критику, и постараюсь исправить свои ошибки.

[halyavin]

Если вам нужно найти корень по модулю p², где p — простое число, то не достаточно два раза найти корень по модулю p и воспользоваться китайской теоремой об остатках. Вместо этого, нужно найти корень по модулю p, а затем корень по модулю p² в виде x+c*p, где x — корень по модулю p. Для это нужно решить линейное уравнение на c. Эта процедура (переход от решения по модулю p к решению по модулю p²) называется подъемом Гензеля. Аналогично для p³ и.т.д.

[winger]

Подъем Гензеля не будет работать для p=2, этот случай необходимо разбирать отдельно (линейное уравнение на c либо не будет иметь решений, либо их будет 2).

[Mrrl]

Если начинать с b=x+c*4 (x — нечётно, а a=8*k+1), то все цифры, кроме старшей, восстанавливаются однозначно. Так что подъём работать будет. Но разбирать его отдельно в самом деле придётся.

[halyavin]

В случае не взаимно простых a и p возможно имеет смысл просто возвращать ошибку или какую-либо структуру данных, которая описывает все решения.

[Sany_KENT]

Вспомнил, точно, было такое на лекциях. Придется произвести модернизацию этих функций и исправить указанные Вами ошибки.

[hardex]

mne vashi peremenyi ne ochen' nravyatsya…

[iroln]

Думаю, что зря у нас в большинстве университетов студентов подсаживают на Matlab, при этом даже толком не учат им пользоваться, внушая мысль, что это какой-то калькулятор-переросток. Во-первых, Matlab — это закрытое ПО, за которое просят десятки тысяч долларов, но которое этих денег, на мой взгляд, не стоит. Во-вторых, для решения этой конкретной задачи лучше подходит Python, так как поддерживает длинные целые из коробки (можно проверить работу алгоритма на действительно больших числах).

ostatok
chastnoe

Так писать не надо, никогда. :)

[Mrrl]

Думаю, что символ Лежандра будет проще вычислить не с помощью разложения на множители, а возведением в степень: a^((p-1)/2) mod p. Всё-таки, факторизация — очень дорогой процесс.
Само решение уравнения x^2=a я бы делал, перебирая b от 1 по порядку, и считая GCD((x-b)^((p-1)/2)-1,x^2-a). Если получится многочлен u*x-v, имеющий степень 1, то ответом будет x=v/u (и x=-v/u). А рано или поздно он должен получиться — когда одно из чисел b+x, b-x будет квадратичным вычетом, а другое нет. Не уверен, впрочем, что это будет быстрее предложенного алгоритма — время работы K*log(p)^2, где K — число попыток.