2. Если для составного

брать

, то при достаточно большом

быстро находится

как в

-методе Полларда. Я глубоко не вникал, но там, кажется, функция

как раз исключена. Хоть похож на Монте-Карло, только всё ж не Монте-Карло. При

вроде бы

всегда попадает в период. Количество проверок при таком подходе на порядок меньше, но находятся, конечно, "плохие числа", в частности квазипростые Мерсена.
Если же отслеживать начало периода при произвольном

, то появляются иные возможности. Для

, к примеру,

. Из периода

информации о делимости

не извлечь, но при

имеем

, откуда

и

. В узелке

-петли содержится пара сравнимых по модулю нетривиальных квадратов, о чем упоминания не встречал. Как бы довести всё это до совершенства?
Оценки асимптотики у Вас нет, правильно я понимаю?
Вообще, Вас все это интересует в плане эффективной факторизации, правильно?
Я тут почитал Вику (
https://ru.wikipedia.org/wiki/%D0%A0%D0 ... 0%B4%D0%B0), Германа с Нестеренко и статью
http://www.cs.cmu.edu/~avrim/451f11/lec ... ollard.pdfОценки там такие: если

, то

и вдобавок для последовательности

длина предпериода

и длина периода

тоже, что в итоге дает время работы
![$O(\sqrt{\sqrt{p}+\sqrt{p}+O(\ln ^k p)})=O(\sqrt[4]{m})$ $O(\sqrt{\sqrt{p}+\sqrt{p}+O(\ln ^k p)})=O(\sqrt[4]{m})$](https://dxdy-01.korotkov.co.uk/f/8/2/4/824344d572d0d18703ad72de853f035182.png)
. С оценкой предпериода они не заморачиваются - видимо, проблема не в ней. Легко может оказаться, что предпериоды и так сильно короче.
Оценка

- вероятностная, похожая на оценку в парадоксе дня рождений (есть и в Нестеренко, и в Вики).
(причем по ссылка народу многочлен

не нравится за впадание в цикл
![$[2]$ $[2]$](https://dxdy-03.korotkov.co.uk/f/a/5/1/a51017f136e558ba29a2faebc9e2787682.png)
длины 1. Неясно, почему, например отображение

тоже порождает циклы длины 1 для

, например)
У Вас

. Если это верно, то это хорошо, но еще нужна оценка длины периода

. Если по-прежнему

, то результат не сильно радует (а если длина предпериода реально мала, то совсем не радует).
Хотелось бы , конечно, обо всем этом спросить спецов, которые пытались улучшить ро-метод Полларда или читали о таких попытках (только если найти чье-нибудь мыло и написать ему). Нужно вообще знать статистику величины

- насколько длины циклов разные, насколько можно отгадать цикл покороче по

и

, насколько это помогает факторизации. проверить последнее, видимо, сложно, пока можно без него - пособирать статистику

для разных

(интересно, помогает ли варьирование

). Поскольку отображение итеративно, теоретически анализировать все это будет сложно.
Если чисто статистически обнаружится, что оценка

не улучшаема, то увы. В Вики пишут, что факторизация на эллиптических кривых это мегакруто (субэкспоненциальная скорость - это, конечно, действительно круто). С другой стороны, для меня она, например, пока что запредельна.
Можно также посмотреть эмпирически оценку

для других отображений

- может оказаться, что длины предпериода тоже на самом деле короткие.
Andrey A, Вы наверняка искали эмпирически. У Вас есть какая-нибудь статистика? Чтобы лишних вычислений не делать.