2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Новый эвристический алгоритм получения x^2<sqrt(p) mod p
Сообщение19.12.2021, 21:42 
Аватара пользователя


07/01/16
1714
Аязьма
RomanM в сообщении #1543613 писал(а):
А тут речь о третьем способе и он скажем так, несколько странный.
Смысл задачи - исследовать собственно сам способ.
Окей, алгоритм ищет некоторые $x: x^2\bmod p<\sqrt{p}$, необязательно являющиеся делителями $p$; выдает он их на печать в значении переменной $t$, это мне удалось установить опытным путем. Ну и вы тоже делаете полный перебор, с некоторым колдунством внутри. Честно говоря, зачем оно нужно не очень ясно, вы же все равно во внешнем цикле вычисляете $x^2\bmod{p}$ первым же шагом, почему бы его просто не сравнить с $\sqrt{p}$, да и вывести на печать?

 Профиль  
                  
 
 Re: Новый эвристический алгоритм получения x^2<sqrt(p) mod p
Сообщение19.12.2021, 21:50 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Новый эвристический алгоритм получения x^2<sqrt(p) mod p
Сообщение19.12.2021, 22:08 
Аватара пользователя


07/01/16
1714
Аязьма
Видимо, вот что утверждается :idea: : стартуя с любого (?) $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$ итераций не получилось, заканчиваем с неудачей).

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

 Профиль  
                  
 
 Re: Новый эвристический алгоритм получения x^2<sqrt(p) mod p
Сообщение19.12.2021, 23:19 
Аватара пользователя


07/01/16
1714
Аязьма
Вот, для примера, возьмем $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$) будут найдены все подходящие делители

 Профиль  
                  
 
 Re: Новый эвристический алгоритм получения x^2<sqrt(p) mod p
Сообщение20.12.2021, 00:22 
Аватара пользователя


07/01/16
1714
Аязьма
Поправка: вот все неудачные начальные $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$$

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: YandexBot [bot]


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group