Подскажите, есть-ли какие-то методы решения сравнения вида x^2≡n mod 2^b? Для b=1 проблем нет, там только два варианта: или 0 или 1. А вот что делать при других b ума не приложу.

задан 2 Апр '18 11:38

Вообще, для полей характеристики 2 даже обычные квадратные уравнения решаются трудно, так как не действует обычная формула. То же касается колец, в которых элемент 2 необратим. Тем не менее, мультипликативная группа по модулю степени двойки имеет известную структуру, поэтому на уровне теории здесь всё сравнительно просто. Что касается конкретных вычислительных алгоритмов, то там вопрос стоит только о степени их вычислительной сложности. Но там в принципе понятно, что надо делать.

(2 Апр '18 14:11) falcao

Для b=1 корень один: либо 0 либо 1. А вот дальше корень может быть как один так и два. Причем он может быть единственным и для 2 и для 3, а только потом появятся два корня. Вообще мне интересно решение для полинома вида xx+qx-а по степеням b от 2 до некоторого k. Для начала хотелось бы просто понять как решается пример xx+3x-2(mod 4). Там решения 2 и 3. Но, какова методика?

(2 Апр '18 18:37) Андрей13neo

То есть, другими словами, на входе есть q=3, a=2, b=2 и полином xx+qx-а=0(mod 2^b). Какими арифметическими действиями можно получить x1=2, x2=3? Только не надо шуток, что x1=a, x2=q :)) Я так понимаю, что каким-то образом должны быть получены числа -5 и 6 (коэффициенты квадратного уравнения x*x-5x+6=0). Сразу напрашивается какая-то смутная аналогия на теорему Виета, но это просто совпадение чисел.

(2 Апр '18 18:46) Андрей13neo

@Андрей13neo: я чуть позже мог бы изложить это дело в более общем виде (можно для квадратных уравнений), с разными примерами. Но надо иметь в виду, что при невозможности деления на 2, нет общих формул. Основная идея там -- использовать индукцию. Когда уравнение решается по модулю p^k, то сначала решаем по модулю p. находим возможные значения остатков, и записываем x=py+r. Подставляем, упрощаем, и сводим задачу к сравнениям по модулю p^{k-1}. Плохо там только то, что процесс может "ветвиться", но эту трудность можно попытаться обойти.

Ещё одна идея -- решать по принципу "числового ребуса".

(2 Апр '18 23:31) falcao

Для случая квадратичных сравнений вот эта ссылка может быть полезна. Там указан явный способ нахождения решений по индукции (если знаем решение x0 mod 2^k, то быстро подбираем решение mod 2^{k+1}, проверяя само x0 и x0+2^k.

(3 Апр '18 0:07) falcao

Спасибо за ссылку. Сейчас буду перекладывать ее в код. О результатах потом напишу. А индукция для моей цели - идеальный вариант, так как надо найти решение для всех степеней от 2 и до определенного значения. Я сейчас пытаюсь для решения этой задачи приспособить формулу x1≡f(x0)/(p^b*f '(x0))(mod p). Там еще есть один неудобный момент: неизвестно при каком b появляются два корня. При некоторых полиномах до b=5 только один корень и только потом появляются два, в других при 3 или 4. В общем, есть над чем подумать.

(3 Апр '18 1:01) Андрей13neo

К сожалению, все что там написано не соответствует действительности. Там утверждается, что при n>2 уравнение имеет 4 решения. Уравнение х^2=280 (mod 2^3) имеет два решения: 0 и 4. Также там утверждается, что индукционные корни либо такие же, либо отличаются на фиксированную величину. Первый же взятый мною полином это опровергает. Уравнение x^2+454x-280=0 (mod 2^3) имеет корни 0,2,4,6. А уравнение x^2+454x-280=0 (mod 2^4) имеет корни 4,6,12,14. То есть, и одинаковых нет и отличаются на разные величины. Откуда автор взял все это???

(4 Апр '18 11:07) Андрей13neo

Там же русским языком написано: Let a be an odd integer. (Since we are assuming m and a are relatively prime, if m has a power of 2 as a factor, a must be odd.)

(4 Апр '18 11:29) spades

@Андрей13neo: там по ссылке всё правильно. Если мы решаем квадратичное сравнение x^2=a(mod 2^k) с чётным a, то x также чётно, и тогда при k>=2 число a делится на 4. Тогда сокращаем на 4, рассматривая (x/2)^2=a/4(mod 2^{k-2}). Это позволяет свести рассмотрение к случаю нечётного a, что там и делается, и о чём явно сказано.

При рассмотрении сравнений по модулю 8 имеет смысл избавляться от больших чисел, сразу заменяя их остатками. Тогда проще следить.

(4 Апр '18 15:02) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×73
×48

задан
2 Апр '18 11:38

показан
214 раз

обновлен
4 Апр '18 15:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru