Решение квадратичных сравнений по простому модулю

[Stensen]

Решение квадратичных сравнений

Доброго времени суток. При попытке разобраться в методах решения квадратичных сравнений по простому модулю $p$, находил в литературе, например такой: модуль раскладывается по модулю степени двойки: $p=q\cdot2^m + r$ и в зависимости от остатков приводится вариант решения. Почему именно так, почему не по степеням тройки или другого числа? И где об этом можно почитать, где попроще написано, с примерами? Читал Виноградова "Основы Теории чисел", там об этом не очень.

[yk2ru]

Если модуль простое число Мерсенна, то как его разложить по модулю степени двойки, допускают ли $r$ быть отрицательным в той литературе?
Или только так: $31 = 2^4 + 15$ . А можно и так: $31 = 3\cdot{2^3} + 7$ , что лучше тогда для $x^2 = 5 \mod 31$ , чтобы получить $x=6$ ?

[Stensen]

yk2ru в сообщении #1302898 писал(а):

Или только так: $31 = 2^4 + 15$ . А можно и так: $31 = 3\cdot{2^3} + 7$ , что лучше тогда для $x^2 = 5 \mod 31$ , чтобы получить $x=6$ ?

Я вот и хочу понять, что препятствует такому разложению: $31 = 3^3 + 4$ ? Я пока не пытался решить с таким разложением, только подбираюсь.

yk2ru в сообщении #1302898 писал(а):

Если модуль простое число Мерсенна, то как его разложить по модулю степени двойки, допускают ли $r$ быть отрицательным?

число Мерсенна: $M_n=2^n-1$, а почему именно число Мерсенна Вы привели в пример? Ведь в Вашем верхнем примере это другое число?

[yk2ru]

$31 = 2^5 - 1$ - это число Мерсенна.
Если бы допускалось отрицательное число, то двойка была бы в максимальной степени при разложении, а добавка была бы наименьшей по абсолютному значению.
Привели бы пример решения какой-то из той литературы.

[Stensen]

yk2ru в сообщении #1302927 писал(а):

$31 = 2^5 - 1$ - это число Мерсенна.
Если бы допускалось отрицательное число, то двойка была бы в максимальной степени при разложении, а добавка была бы наименьшей по абсолютному значению.
Привели бы пример решения какой-то из той литературы.

Видел только с плюсом.

[yk2ru]

Дайте название книги/статьи, где можно про этот метод с разложением глянуть.

[Stensen]

yk2ru в сообщении #1302936 писал(а):

Дайте название книги/статьи, где можно про этот метод с разложением глянуть.

http://helpiks.org/6-5780.html
http://textarchive.ru/c-1341299-p6.html

Там качество печати плохое, поэтому спросил про книгу

[Stensen]

Правильно ли я понимаю, что идея построения этих методов вытекает из критерия Эйлера:

$\binom{a}{p}\equiv a^\frac{p-1}{2} \mod p$, в предположении, что $a$ квадратичный вычет по $\bmod p$ можно получить: $ a^\frac{p+1}{2} \equiv a \mod p$, тогда: $ (a^\frac{p+1}{4})^2 \equiv a \mod p$, отсюда: $x\equiv a^\frac{p+1}{4} \bmod p$ и далее рассматриваем возможные варианты разложения $p$ по различным модулям, чтобы сократить знаменатель? Верна ли логика рассуждений?

Подскажите где можно найти статьи в хорошем качестве, указанные в ссылках: http://helpiks.org/6-5780.html, http://textarchive.ru/c-1341299-p6.html, или др. об том же?

[Sonic86]

Stensen в сообщении #1302947 писал(а):

http://helpiks.org/6-5780.html

Я никогда не знал этот метод, я его 1-й раз в жизни прочел здесь.
И я все понял.
Здесь есть ответы на все Ваши вопросы.
Формально метод умещается в 1 абзац, а откуда что берется - расписано подробно с самого начала

Stensen в сообщении #1302897 писал(а):

Почему именно так, почему не по степеням тройки или другого числа?

Потому что мы хотим извлекать корень - корень степени 2.

Stensen в сообщении #1302897 писал(а):

И где об этом можно почитать, где попроще написано, с примерами?

Не знаю такой книжки, м.б. в Василенко, но, ИМХО, приведенных Вами ссылок для понимания вполне достаточно.

Stensen в сообщении #1303213 писал(а):

$ a^\frac{p+1}{2} \equiv a \mod p$, тогда: $ (a^\frac{p+1}{4})^2 \equiv a \mod p$,

Это только в случае $p\equiv 3\pmod 4$. Для $p\equiv 1\pmod 4$ нужно привлекать некоторый квадратичный невычет.

Stensen в сообщении #1303213 писал(а):

и далее рассматриваем возможные варианты разложения $p$ по различным модулям, чтобы сократить знаменатель?

Ну не по различным, а только по степеням двойки $2^r$. Причем всякий раз разбираются случаи $p\not\equiv 1\pmod {2^r}$, а случай $p\equiv 1\pmod {2^r}$ всякий раз разбивается на 2 подслучая: $p\equiv 1\pmod {2^{r+1}}$ и $p\equiv 1+2^r\pmod {2^{r+1}}$.

Stensen в сообщении #1303213 писал(а):

идея построения этих методов вытекает из критерия Эйлера:

критерий Эйлера в рассуждениях используется. "Вытекает" - я бы так не сказал.
Просто прочтите целиком, медленно.

Числа Мерсенна не при чем.