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

[waxtep]

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

А тут речь о третьем способе и он скажем так, несколько странный.
Смысл задачи - исследовать собственно сам способ.

Окей, алгоритм ищет некоторые $x: x^2\bmod p<\sqrt{p}$, необязательно являющиеся делителями $p$; выдает он их на печать в значении переменной $t$, это мне удалось установить опытным путем. Ну и вы тоже делаете полный перебор, с некоторым колдунством внутри. Честно говоря, зачем оно нужно не очень ясно, вы же все равно во внешнем цикле вычисляете $x^2\bmod{p}$ первым же шагом, почему бы его просто не сравнить с $\sqrt{p}$, да и вывести на печать?

[zykov]

Да, непонятно, какой $x$ нужно?
Например чем $x=1$ не подходит?

[waxtep]

Видимо, вот что утверждается : стартуя с любого (?) $u$, можно с некоторой вероятностью получить в $t$ одно из подходящих $x$

-- 19.12.2021, 22:47 --

В общем, если я правильно расшифровал алгоритм, речь о следующем:
- для данного $p$ берем некоторое $x: p>x>\sqrt p$;
- если $b=x^2\bmod p<\sqrt p$, ура, мы закончили;
- иначе берем следующее значение $x=\left\lceil\sqrt{b^2-b^2\bmod{p}}\right\rceil$ и возвращаемся на предыдущий шаг (не более двухсот раз в предложенном куске кода; если за $200$ итераций не получилось, заканчиваем с неудачей).

Вопрос, видимо, в том, почему и при каких условиях это работает.

[waxtep]

Вот, для примера, возьмем $p=55$; стартуя с $x=9$ мы удачно пройдем по цепочке $9\rightarrow26\rightarrow15$; а, скажем, старт с $x=10$ приведет к зацикливанию $10\rightarrow45\rightarrow45\rightarrow\ldots$. Или еще такой вариант неудачи при старте с $x=13$: $13\rightarrow0$.

-- 19.12.2021, 23:43 --

Хм, хотя, $x=13$ это удача, уже сам запутался

-- 20.12.2021, 00:06 --

Вот все неудачные начальные $x:1\leqslant{x}\leqslant{p}$, приводящие к зацикливанию для $p=55$:

$$\align3,8,47,52\rightarrow8\rightarrow\ldots\\ 10,45\rightarrow45\rightarrow\ldots\\ 11,22,33,44\rightarrow11\rightarrow\ldots\end$$

При старте с любого другого $x$ будет найден какой-нибудь подходящий делитель, причем в совокупности (для всех начальных $x$) будут найдены все подходящие делители

[waxtep]

Поправка: вот все неудачные начальные $x:1\leqslant{x}\leqslant{p}$, приводящие к зацикливанию для $p=55$:

$$\align3,8,47,52\rightarrow8\rightarrow\ldots\\ 10,45\rightarrow45\rightarrow\ldots\\ 22,33\rightarrow44\rightarrow11\rightarrow11\rightarrow\ldots\end$$