Новый эвристический алгоритм получения x^2<sqrt(p) mod p

[RomanM]

Добрый день.
Пусть $p-x>x>\sqrt{p}$ где $p$- составное число, $x\in Z$- уберем тривиальные случаи.
Задача - найти такие $x$, для котрых $ x^2<\sqrt{p} \; \pmod p$

Есть несколько способов решения. Притом все они численные!
Вот способ, который найден мной - не знаю, новый они или нет. Но в книжках не находил подобного.

$(A+x)^2 \equiv A^2+2Ax+x^2 \; \pmod p \;(1)$
Пусть $A^2 \equiv C \; \pmod p$ подставим в (1) и приравняем к нулю
$C+2Ax+x^2 \equiv 0 \; \pmod p$
Решим то, что получилось относительно $х$, результат округлим вверх $x=A \pm \lceil(\sqrt{A^2-C})\rceil$
Подставим $x$ в (1), $( \pm \lceil\sqrt{A^2-C}\rceil)^2 \equiv Y\; \pmod p$. Проверим не меньше ли $Y $ квадратного корня из $p$.
А теперь внимание - вот тут вся соль
Положим $A \equiv Y^2 \;\pmod p$ и повторим все вычисления
Как ни странно, цикл часто сходится к величине, меньшей $\sqrt{p}$
Вот Pari/GP код

\p300
{p=1234577*3001;
c=ceil(sqrt(p));
for(u=c,p,

b=lift(Mod(u^2,p));
c2=lift(Mod(b^2,p));

for(y=1,200, 

t=ceil(sqrt(b*b-c2));

b=lift(Mod(t^2,p));
c2=lift(Mod(b^2,p));

if(b<c, break()); \\break at sub sqrt residual
);
localprec(7);
z=b/c/1.;
if(z<1,print(z,"  ",t," ",issquare(b)));

);}

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы).

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Математика (общие вопросы)»

[RomanM]

Конкретно вопросы следующие
1) Это нечто новое или давно общеизвестное?
2) Почему данный алгоритм вообще работает?
3) Почему если построить график Начальные значения-Результат, он выглядит в точности как энегетические уровни в квантовой механике)
4) Почему при различных начальных данных получаем одинаковые конечные результаты -
и можно ли использовать это как решето?
5) Можно ли применить такой же трюк к степеням выше 2?
6) Есть ли особые свойства у получаемых значений?
7) Какое наименьшее значение можно получить данным методом для больших р?

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

[пианист]

С целью, простите за выражение, самообразования (с); позвольте вопрос: что есть

RomanM в сообщении #1543281 писал(а):

$ x^2<\sqrt{p} \; \pmod p$

Понятен смысл равенства по модулю, а вот это что значит?

[waxtep]

Можно ли попросить вас на простом примере для $p=16$ о следующем:
1. Подтвердить, что разыскивается $x=7$ и только оно ($7^2\bmod16=1<4$);
2. Кратко пояснить, как выдача приложенного куска кода помогает понять, что мы нашли требуемое значение $x$.
Спасибо!

[Dmitriy40]

Лучше спросить к какому значению из нескольких должен сходиться приведённый алгоритм и почему к нему:

? p=24; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
5,7,10,11,
? p=48; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
7,10,12,14,17,22,23,
? p=60; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
8,11,19,22,28,29,
? p=96; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
10,14,17,22,24,26,31,34,38,45,46,47,

пианист в сообщении #1543425 писал(а):

Понятен смысл равенства по модулю, а вот это что значит?

Это: $x^2 \bmod p < \sqrt{p}\bmod p = \sqrt{p}$.

[RomanM]

пианист в сообщении #1543425 писал(а):

С целью, простите за выражение, самообразования (с); позвольте вопрос: что есть

RomanM в сообщении #1543281 писал(а):

$ x^2<\sqrt{p} \; \pmod p$

Понятен смысл равенства по модулю, а вот это что значит?

это значит вот что $x^2=y \pmod p \; y<\sqrt{p}$

-- 19.12.2021, 19:07 --

Dmitriy40 в сообщении #1543443 писал(а):

Лучше спросить к какому значению из нескольких должен сходиться приведённый алгоритм и почему к нему:

? p=24; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
5,7,10,11,
? p=48; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
7,10,12,14,17,22,23,
? p=60; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
8,11,19,22,28,29,
? p=96; sq=sqrt(p); for(x=floor(sq)+1,p\2-1, if((x^2)%p<sq, print1(x,",")))
10,14,17,22,24,26,31,34,38,45,46,47,

пианист в сообщении #1543425 писал(а):

Понятен смысл равенства по модулю, а вот это что значит?

Это: $x^2 \bmod p < \sqrt{p}\bmod p = \sqrt{p}$.

тут то все понятно - этот алгоритм не эвристический, и выдаст ВСЕ значения, меньшие квадратного корня из р. А приведенный выше - не все.

-- 19.12.2021, 19:11 --

waxtep в сообщении #1543434 писал(а):

Можно ли попросить вас на простом примере для $p=16$ о следующем:
1. Подтвердить, что разыскивается $x=7$ и только оно ($7^2\bmod16=1<4$);
2. Кратко пояснить, как выдача приложенного куска кода помогает понять, что мы нашли требуемое значение $x$.
Спасибо!

Никак. Это эвристика - бог его знает как оно вообще сходится к чему-то. Тут и вопрос ведь в этом однако

[пианист]

RomanM в сообщении #1543584 писал(а):

это значит вот что $x^2=y \pmod p \; y<\sqrt{p}$

Видимо, $x^2 = y \pmod p \ \& \ y < \sqrt{p}$..
Но это (больше или меньше) же зависит от выбора $y$, можно выбрать и так, и так.
Впрочем, можете не отвечать, если уважаемые waxtep и Dmitriy40 понимают, о чем речь, не хочу отнимать Ваше внимание.

[waxtep]

RomanM в сообщении #1543584 писал(а):

Никак. Это эвристика - бог его знает как оно вообще сходится к чему-то. Тут и вопрос ведь в этом однако

Не, у меня более прикладной вопрос, не могу понять, что ваш код делает. Вот мы при $p=16$ дошли до $u=7$ (это ведь $x$?) во внешнем цикле; при первом же проходе цикла внутреннего ($y=1$) получили $t=b=c_2=0$ и напечатали $\texttt{0,0,1}$. Если я правильно понял ваш алгоритм - такая выдача, это хорошо, сигнал найденного $x$; но тогда его в выдачу бы добавить что ли (напечатать и значение $u$). Или все совсем не так?

[Dmitriy40]

пианист
$x^2$ по модулю $p$ (т.е. остаток от деления $x^2/p$) должен быть меньше $\sqrt{p}$: $x^2 \bmod p < \sqrt{p}$.
Если по модулю можно проверять на равенство, что Вам понятно, то можно и сравнивать на больше/меньше.

[RomanM]

Dmitriy40 там у меня некорректно чисто математически написано и это чистая правда. По смыслу можно понять, но математиков, настоящих - коробит.
waxtep
Все так, почти. Просто я тестировал тот код на значениях p ~10^300, а там такая ситуация, скажем так, редкая. Совсем редкая) Поэтому ее специально не прописывал.

Просьба посмотреть свежим взглядом на замкнутые циклы, в которые частенько сваливается алгоритм. Памятуя о $\rho-$ алгоритме Полларда)

[waxtep]

RomanM, давайте может быть тогда о смысле задачи поговорим: вы пытаетесь найти собственный делитель довольно крупного числа $p$? Величина $x$ - это искомый делитель, или какая-то заготовка для его нахождения?

[пианист]

(Оффтоп)

Dmitriy40 в сообщении #1543607 писал(а):

$x^2$ по модулю $p$ (т.е. остаток от деления $x^2/p$)

А, остаток. То есть $x^2 - [\frac{x^2}{p}]p < \sqrt{p}$.
Понятно, спасибо.

[RomanM]

Есть два спрособа найти малые остатки от деления после возведения числа x в квадрат по модулю некоего составного числа - первый и самый очевидный - алгоритм Dmitriy40. Просеивание набора полиномов - это всего лишь вариация данного способа. Второй - разложение в цепную дробь. А тут речь о третьем способе и он скажем так, несколько странный.
Смысл задачи - исследовать собственно сам способ.
Так как он, вероятнее всего, все же новый.
Сейчас трудно найти что-то новое в таком перекопанном огороде, как
остатки от деления) И тем не менее.