Раз не пошло обсуждение некоторых книг,
то предлагается обсудить «древний» метод факторизации чисел – (р – 1) Полларда.

В этом методе на первом этапе есть граница В,
и для этой границы «набирается» простые числа в некоторой степени таким образом,
чтобы эти простые числа в степени не превышали В.

Если необходимо определять все простые числа как делители до 500,
то необходимо, наверное, перемножать все простые числа до 500,
или некоторые, про которые ничего не известно.
И ещё добавить степень. То есть, число М будет ещё больше.
Всего простых чисел до 500 – 92.

Оказывается, достаточно перемножить «только» 32 числа, и без степеней.

Есть желающие продолжить обсуждение?

1. По первому этапу метода:

Нигде не сказано:
- что такое максимальное М;
- что такое максимальное В;
- зависят ли эти числа от факторизируемого числа.

Это в порядке обсуждения.

И если на это будет дан ответ, то, наверное, это и будет новым.

Есть сомнение: что лучше:

1. скрупулёзно выбирать нужные простые числа и уменьшать М

2. перемножать все простые числа в диапазоне и будет очень большое М,
а далее "спасает" блочное умножение,
при этом блоков будет несколько больше, чем в первом варианте.

(мысли вслух)

Решил рассмотреть многоблочность метода.
То есть выбор числа В.

На отдельном примере: 9929243 * 699720181 = 6947691709152983 (n)

Оказалось, что:
- если В = sqrt(n) (или 83352814), то время работы - 2м 6 сек
- если В = n , то время работы - 2м 16 сек
- если В = n*2 , то время работы - 2м 17 сек
- если В = n^2 , то время работы - 2м 49 сек

А как вам такая вещь:

зачем искать простые числа, и тратить на это время.

Проще перемножить все нечётные числа.
А многоблочность всё "скушает"!

Конечно по схеме 6хК + 1 и 6хК + 3 (без 6хК + 3)

https://ru.wikipedia.org/wiki/P?1-метод_Полларда

В конце данной статьи увидел рекорды по определению делителей.

Взял число из 66 десятичных цифр, произведение простых чисел умножил на 37 и прибавил 1.

Получилось число, большее чем указанное число, это число будет простым.
Число 24865434557959795430290772917670661657299237407700521891770082957981 простое.

Получается рекорд побит или нет?

Я понимаю, что в этой публикации что-то напутали.

С другой стороны, а чём заключается рекорд, если об этом говорят уже в 2-х публикациях?
И причём говорят одинаково.

https://members.loria.fr/PZimmermann/records/Pminus1.html

Посмотрел импортный вариант, там то же самое.

Согласен.

Но кто-то ставит рекорды, поскольку у данного метода есть ограничения на величину делителя.
И кто-то эти рекорды публикует.

Парадокс (р – 1) – метода Полларда.

Рассмотрим парадокс метода на примере. Определяем число М, как:
M = 2^7 = 128.
Тогда, определяются общие делители чисел (2^128 -1) и факторизуемого числа n.
У числа (2^128 -1) следующие делители:
3 , 5, 17, 257, 641, 65537, 274177, 6700417 и 67280421310721. (1)

Следовательно, если у числа n будет хоть один делителей из (1), то этот делитель будет определён.
Согласно методу среди делителей (1) должны быть только те числа Р, для которых величина (Р – 1) будет степенью числа 2.
Таких чисел среди делителей (1) только 5: 3, 5, 17, 257 и 65537.

Для остальных чисел среди делителей (1) величина (Р – 1) не являются степень числа 2, так как:
640 = 2^7 * 5
274176 = 2^8 * 3^2 * 7 * 17
6700416 = 2^7 * 2 * 17449
67280421310720 = 2^8 * 5 * 47 * 373 * 2998279.
однако эти делители метод определяет как делителей некоторого числа n1.

Кроме того, сомножитель числа М есть 2^7, а при этом определяется число 65537, у которого (65537 – 1) = 2^16.

Парадокс метода заключается в следующем:
в сомножители числа М включаются одни числа, а в результате применения метода определяются делители Р чисел n1, у которых в числе (Р – 1) имеют место другие числа.

А вот ещё один момент.

Первая стадия (р - 1) метода идёт до числа В1,
при этом число М получается как произведение нескольких сомножителей.

И, вдруг, начинается вторая стадия,
когда после числа В1 выбираются следующие сомножители,
и уже число М не произведение нескольких сомножителей,
а 1 сомножитель (постоянный элемент * дельта).

Спрашивается: а когда наступает вторая стадия?
Или каждый решает это про себя.

1974

В статье обозначил задачи. которые позволяют лучше представить идеи (p – 1) – метода Полларда.
http://sci-article.ru/stat.php?i=1599050022

Может быть, это всё уже когда-то было.
В существующих описаниях по данному методу такие задачи не рассматривались.

Система показывает, что у меня нет права на эту ссылку.

И как туда попасть?

Там есть методы?

Зашел и что дальше?

Там их очень много.

Что надо найти?

Добавлена:
Задача 8. Изменение формул (р – 1) - метода Полларда.

http://sci-article.ru/stat.php?i=1599050022

Значительно уменьшает время определения делителей.

И что что-то было?

Попадаются числа, для которых нельзя применить (р-1)-метод Полларда.

Например:
274177 * 67280421310721

Метод эти числа "не разделяет".

Оказывается у них ux (из статьи) равны между собой и = 128!

Добавлена:
Задача 9. Шаги двух делителей в произведении М.

http://sci-article.ru/stat.php?i=1599050022

Рассмотрен случай a^M = 1 (mod n).

Добавлена:
Задача 10. Определение сильных простых чисел применительно к (р – 1) - методу Полларда.

http://sci-article.ru/stat.php?i=1599050022

Приведены не сильные простые числа применительно к (р – 1) - методу Полларда для границы В1.

Уточнена задача 3, добавлены выводы.

В (р - 1) методе Полларда можно добавить 0-ю стадию.
На этой стадии определяются простые числа р с очень простыми сомножителями числа (р - 1).

Как известно из статьи:
если a^M = 1 (mod n),
то в произведении М "присутствуют" сомножители от двух (или больше) делителей.
И не надо думать, пока, о границе В1.
Просто устанавливается граница В0.

Поэтому на 0-й стадии будет простой алгоритм:


Если на определённом шаге a^M = 1 (mod n), то применяется с1 от предыдущего шага.
И d определяет делитель числа а, а именно, 593.

Здесь в цикле можно ограничить количество вычислений,
а потом переходить на 1-ую стадию,
если не будут найдены делители.

Все простые числа можно вычислить по формулам р = 6*К+1 или р = 6*К+5.

Среди этих чисел интересны, как сильные, числа р, у которых (р -1)/2 - простое число.

Для таких чисел справедлива формула: р = 11 + 12*К

Каких "этих": всех простых или (6к+-1)?
Например:
р = 839
(р-1) = [2, 419]
т.е. (р-1) состоит только из двух простых сомножителей.
Наверное, такие простые числа р - сильные простые числа.

Такого вида числа р будут иметь формулу:р = 11 + 12*К

Теперь о количестве таких сильных простых чисел:

программа определяет 116 таких сильных простых чисел в диапазоне от 3 до до 10000.

А вот и ошибка!

https://dpva.ru/Guide/GuideMathematics/GuideMathematicsFiguresTables/SimpleFigures/SimpleFiguresPrint/

Здесь перечислено 1229 простых чисел