Эпиграф: До «решета» ещё далеко, пока изучаю методы попроще. https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Кстати, неплохая книга для изучения факторизации.

Очень интересный метод (р – 1)-метод Полларда:
перемножаем несколько степеней минимальных простых чисел (по модулю n) и
с помощью н.о.д. сразу определяется минимальный множитель.
Данный метод годится только для чисел, у которых один из множителей мал. А другой сколь угодно большой.

Пробные расчеты показали, что можно проводить следующие исследования:
- зависимость количества базовых простых чисел от величины малого множителя;
- зависимость предела степеней каждого базового простого числа от величины малого множителя.
Получается, что можно построить некоторую функцию по двум переменным,
отражающую предел по определению множителей.

Пример:
n = 1427*23456234562345623461
Кстати, второй множитель может быть сколь угодно большим.
Первый множитель определяется, если имеем более 10 первых простых чисел , и
если предел степеней больше 30 (добавляется простое число 31).

Далее, из перечня базовых простых чисел от 2 до 31 нельзя убирать числа 2, 23, 31,
а все остальные можно: останутся только числа 2, 23, 31.
И так далее…

Получается, что этот метод может соперничать с методом предварительного деления исследуемого числа
(до определённого простого числа):
для проверки делимости на 225 простых чисел (до 1427 - простое число) достаточно от 3 до 11 простых чисел

Согласен, немного поторопился.

В результате:

"перемножаем несколько степеней минимальных простых чисел,
возводим некоторое начальное число (например, 2) в степень, равную полученному произведению (по модулю n) и
с помощью н.о.д. сразу определяется минимальный множитель."

Кстати, ещё можно "поиграть" этими основаниями степеней.
(в предыдущий раз это помогло)

В продолжение рассмотрения темы (р – 1)-метода Полларда попробовал составить программу:
перебор всех простых чисел, начиная с 3, до некоторого числа,
и для каждого из этих чисел увеличивал В - предел Полларда.
И при этом данные числа умножал на очень большое простое число.

Оказалось, что для того, чтобы определить множители большого числа,
равные от 3 до 101 (простые числа), достаточно применить В = 27.
Для определения множителей, равных от 3 до 1000, достаточно применить В = 882.
Для определения множителей, равных от 3 до 2000, достаточно применить В = 1902.
Для определения множителей, равных от 3 до 5000, достаточно применить В = 8732.

Причем, для определения множителя 4931 достаточно В = 27,
а для определения множителя 4919 достаточно В = 2453.

При этом, если (р-1)-метод определяет число, это не значит, что получен окончательный ответ.
Этот метод может "зацепить" сразу несколько малых простых чисел.
Причём, некоторые числа могут быть и достаточно большими.

Поэтому необходимо ещё одно применение (р-1)-метода к полученному числу
(при этом число В будет намного меньше).

А самый плохой вариант для (р-1)-метода:
проверяемое число есть произведение очень большого числа простых небольших чисел.

Тогда (р-1)-метод выдаст это самое число
(если в проверяемом числе есть степень простого числа, то в "ответе" будет это число, но без степени).
..., начинай с начала.

Barlone,

в задачах факторизации числа n применяется mod(n).

А если применять mod (а), где а = целое(n^1/2)?

И было ли такое применение?

При этом существенно уменьшается база квадратов чисел.

вот интересно, а как пробежаться по этим же числам в модуле n^2В статье дано некоректное определение числа а:

"то для любого целого a такого, что ..."

Надо добавить:

а < n.

Главное - это соотношение чисел n и g.

Число а - это "проверочный материал".
Проверяется от 0 до n - 1.
А далее - просто:
(а + v*n) (mod n) = a.

Зачем усложнять условие?

А в вики
https://ru.wikipedia.org/wiki/Первообразный_корень_(теория_чисел)
по другому определяются эти корни.

И без всяких "для всех а".

Если я правильно понял, то имеем 2^k, 1=<k=<n. (mod n)

Если n = 11, то получаются числа от 1 до 10, причем 1 - два раза.

Если n = 11^2, то нет чисел, кратных 11.

Уравнение
((g^k) mod n^2) mod n
"превращается" в уравнение
((g^k) mod n )

Непонятно, что нужно.

Ранее я говорил, что по модулю n^2 имеем в остатке все числа до n^2, кроме кратных n.

kealon(Ruslan,

что непонятно в моих ответах?

В кольце n^2 (по mod n^2) получаются все числа от 1 до n^2, кроме чисел, кратных n.

Если для этого кольца применить (mod n), то данное кольцо "разбивается" на n колец (mod n),
в каждом из которых все числа от 1 до n-1.

g = 3, n = 11, цикл чисел, 1, 3, 9, 27, 81.
По остальным g (2, 5,7) получается очень много чисел в кольце.
Кстати, проверил, другие варианты (небольшие). И везде много чисел.

Вариант 3 и 11 - пока единственный, где мало чисел!

И что?