Comments 10
А почему возвращаются только два корня? У 1 по модулю 8 есть 4 квадратных корня. А если a и p не взаимнопросты, их может быть астрономически много.
После разложения на множители, нужно искать квадратный корень не по модулю простых чисел, а по модулю степеней простых чисел. Для этого после нахождения квадратного корня по модулю простого числа нужно выполнить подъем Гензеля.
После разложения на множители, нужно искать квадратный корень не по модулю простых чисел, а по модулю степеней простых чисел. Для этого после нахождения квадратного корня по модулю простого числа нужно выполнить подъем Гензеля.
С 1 по модулю 8 действительно неувязка вышла, не учтен такой вариант в функции. Также не учел случай, когда а и р не взаимно простые числа — виноват, но поясните пожалуйста, к какому случаю относятся упомянутые вами действия:
Также благодарю, за конструктивную критику, и постараюсь исправить свои ошибки.
После разложения на множители, нужно искать квадратный корень не по модулю простых чисел, а по модулю степеней простых чисел. Для этого после нахождения квадратного корня по модулю простого числа нужно выполнить подъем Гензеля.
Также благодарю, за конструктивную критику, и постараюсь исправить свои ошибки.
Если вам нужно найти корень по модулю p2, где p — простое число, то не достаточно два раза найти корень по модулю p и воспользоваться китайской теоремой об остатках. Вместо этого, нужно найти корень по модулю p, а затем корень по модулю p2 в виде x+c*p, где x — корень по модулю p. Для это нужно решить линейное уравнение на c. Эта процедура (переход от решения по модулю p к решению по модулю p2) называется подъемом Гензеля. Аналогично для p3 и.т.д.
В случае не взаимно простых a и p возможно имеет смысл просто возвращать ошибку или какую-либо структуру данных, которая описывает все решения.
mne vashi peremenyi ne ochen' nravyatsya…
Думаю, что зря у нас в большинстве университетов студентов подсаживают на Matlab, при этом даже толком не учат им пользоваться, внушая мысль, что это какой-то калькулятор-переросток. Во-первых, Matlab — это закрытое ПО, за которое просят десятки тысяч долларов, но которое этих денег, на мой взгляд, не стоит. Во-вторых, для решения этой конкретной задачи лучше подходит Python, так как поддерживает длинные целые из коробки (можно проверить работу алгоритма на действительно больших числах).
ostatokТак писать не надо, никогда. :)
chastnoe
Думаю, что символ Лежандра будет проще вычислить не с помощью разложения на множители, а возведением в степень: 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 — число попыток.
Само решение уравнения 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 — число попыток.
Sign up to leave a comment.
Функции для решения квадратичных сравнений. Реализация в MATLAB