Эпиграф: До «решета» ещё далеко, пока изучаю методы попроще. 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 - пока единственный, где мало чисел!

И что?

Чтобы такой результат получился (всего 5 или очень немного чисел на большое кольцо),
необходимо решить следующее уравнение:

найти g, n, b для

g^b =1 mod (n^2)

Пока это всё тяжело для меня.

Есть n' и n. Или это одно число?

И из какого уравнения они (оно) определяются?
Ведь известны (?) пока v1, v2, р.

Как я понял, расширенный алгоритм Евклида находит коэффициенты для двух чисел, у которых есть общий делитель.

Но р - число простое, а n < р.
Следовательно, у n и р не может быть общих делителей.

Или я что-то не так понял...

Хотя, есть общий делитель - 1. И поэтому можно найти коэффициенты.
Хорошо.

А что у нас известно: n и p. А что ещё?

Тогда можно получить некоторые числа а и b.
Почему эти числа будут v1 и n', которые определены по формулам?

Попробую "перевести" на циферки. Так проще.

n = 45, p = 61

Тогда n' = 45, v1 = 14.

g(1) = 2 и g(-1) = 2197...

Пока всё верно?

тороплюсь:

Тогда n' = 19, v1 = 14.

Здесь необходимо уточнение насчёт исходного уравнения, для которого справедливо правило
Допустим.

Но если следовать этой логике:
для p = 11 быстро найдем (что-то), хотя n должно быть меньше р.
а для р = 2^3217-1 будем искать очень долго.

А что должно получиться, если применить mod p для этой формулы?
У меня получилось, что достаточно проверить i от 1 до 23, далее повтор.
Какие числа "выберем" из этих 23-х чисел?

Как известно, делители (множители) числа 45 - числа 5 и 9.

Повторно вопрос: какие числа должны получиться (конкретно)?

А ошибка в главном: в начальной постановке вопроса Какое может иметь отношение данная формула к ситуации, когда n < p?

Эта формула определяет числа, намного большие р.

Кстати, а как можно отредактировать сообщение?
Чтобы не делать повторные сообщения.

На этом топике было несколько таких редактирований.

Спасибо!

Нашел кнопку!

И как, "зацепило" в рассматриваемом примере?

Итератор должен иметь два момента:

1. Что он ищет
2. Как он ищет (формула поиска).

Так что из этого есть в задаче 22053148 ?

Я так понимаю, последняя фраза - это самокритика.

Так ты проверял свои умозаключения или просто выплеснул мысли вслух?

На форуме мне всегда говорили: сначала проверь на своём ПК, а потом сообщай остальным.

Всё проверил, только одно забыл:
как завершается наш пример - число 45 и р = 61.

Где последние расчёты, где получаемые множители?

А проверка своего метода 22053148 ?

Как известно:
мужик сказал, ...

Или метод 22053148 никуда не годится?

Составил программу факторизации с помощью метода с использованием непрерывных дробей.
https://old.kpfu.ru/f9/bibl/Monograph_ishm.pdf
Исходное 11111 = 41*271.

Перебираю разные простые числа вместо 41 и всё получается.
А на числе 13 - не получается. Интересно!

И на числах 23, 53, 73,...

Что-то мне подсказывает,
что не "проходят" числа, у которых последняя цифра 3.

Хотя прошло 11 * 283.

Нашел у себя ошибку: не до конца прочитал условие алгоритма.

Если не получилось, то надо продолжать (следующий прогон). И всё.

Взял за основу перебор нечётных числ от 3 до 100 (первое число) и число 257 (второе число).

Обычно множители находятся за 1 - 2 прогона.

Множитель 13 найден за 14 прогонов, 71 - за 40 прогонов, 73 - за 14 прогонов, 83 - за 48 прогонов, 97 - за 53 прогона.
А на 89 - программа зависла - очень много прогонов... (в результате не хватает места для одного из массивов)

Продолжаю исследования метода с использованием непрерывных дробей.

Взял за основу перебор нечётных числ от 3 до 255 (первое число) и число 257 (второе число).

Наблюдаю за количеством прогонов для каждой пары чисел при определении множителей произведения этих чисел.

Если количество прогонов ограничить числом 100000 (!), то получается,
что невозможно найти множителей (кроме 1 и произведения двух чисел) для произведения двух чисел,
когда первое число:
89, 139, 151, 181, 197, 211, 229, 239, 251

Немного подумал и "проскочил" 89.

Например, для числа 167 необходимо 36 прогонов и здесь "фигурируют" числа в районе Е+200.