Раз не пошло обсуждение некоторых книг,
то предлагается обсудить «древний» метод факторизации чисел – (р – 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

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

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

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

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