Как писать быстрые программы

[Dmitriy40]

wrest, Yadryara
Функция ispseudoprime(x,1) ошибается на сильных псевдопростых по тому основанию, которое будет применено, но так как оно выбирается случайно, то заранее предсказать на каком числе ошибётся невозможно. И уж тем более это не связано с наличием малых делителей.
Ошибка состоит в том что она вернёт 1 на составном числе (оно и будет сильным псевдопростым по выбранному основанию). Если функция вернула 0 - это 100% надёжный результат, в нём ошибки быть не может.
По основанию 2 до $2^{64}$ есть примерно 33млн сильных псевдопростых, причём с ростом чисел плотность сильных псевдопростых падает (например 50% от 33млн сосредоточено в первых 4.22e18, т.е. в первых 23% диапазона, а 25% сосредоточено в первых 5.2%), так что вероятность наткнуться на ошибку всяко меньше $\frac{17\cdot10^6}{0.77\cdot2^{64}}\approx10^{-12}$. И можно предположить что количество растёт лишь вдвое на каждое учетверение интервала, т.е. пропорционально корню из интервала. Значит для чисел порядка 50 цифр количество исключений будет порядка 2.3e15 штук или вероятность порядка $10^{-35}$. По другим основаниям вопрос не исследован так далеко, но вероятность сравнима по порядку величины.
И да, среди этих 33млн составных чисел есть и числа с малыми делителями. Например первое же: $2047=23\cdot89$. Или 12-е: $74665=5\cdot109\cdot137$.
Так что да, ispseudoprime(x,1) может не заметить делителя скажем 89, но вероятность этого достаточно мала.

[wrest]

Yadryara в сообщении #1720251 писал(а):

НО. С недобором ситуация не такая простая как с перебором. Надо перепроверить, посмотреть на степени простых выше первой.

Так это надо делать или сразу, или нести с собой найденные множители. omega_upto() кстати имеет параметр отбрасывать ли несвободные от квадратов.
100% гарантию не даёт ни numdiv ни factor, они ведь факторизуют до псевдопростых.

[Dmitriy40]

wrest в сообщении #1720275 писал(а):

100% гарантию не даёт ни numdiv ни factor, они ведь факторизуют до псевдопростых.

Это да, вот только есть большая разница с ispseudoprime(x,1) - ispseudoprime(x) (которой и пользуются и factor и numdiv и все прочие) очень намного точнее и надёжнее, настолько, что до сих пор неизвестно ни одного исключения. Вообще ни одного! И есть теоретические подозрения (недоказанные) что их и быть не может.

А вот с параметром она ошибается относительно часто (на сильных псевдопростых числах, на других не ошибается):

? for(i=1,100, print1(ispseudoprime(2047,1)))
1000000000000000010000000000001000000000010100000000010100001000000000000000000000010000010001000000
? for(i=1,100, print1(ispseudoprime(2047,1)))
1000000100001000100000010000010000000000000010000010000100000000000101000100000000100000000000000001
? for(i=1,100, print1(ispseudoprime(2047,1)))
0010000010000000000000000000000010000000000100010010010000000000010000000000000000000101000000000000
? for(i=1,100, print1(ispseudoprime(2047,1)))
0010010000000010001011001000000000000000010000000000000000000000000000100001000000000000000000000000
? for(i=1,100, print1(ispseudoprime(2047,1)))
0000000000000010000110000010000010100000000000000001000000110000010000000000010000000010000010001100

Видите сколько единиц? Это всё ошибки. И видите что они не детерминированы, т.е. распределены довольно случайно потому что ispseudoprime(x,1) выбирает основания случайно.
Т.е. даже для известных сильных псевдопростых она ошибается не 100% случаев, а сильно меньше, так как сильные псевдопростые по разным основаниям пересекаются слабо.

Отдельно забавно что ispseudoprime(x,1) не проверяет делимость на малые простые (например может иногда сказать что 561 или 1105 простое), зато про числа Кармайкла она часто таки говорит что они составные, хотя они по идее проходят тест Ферма по любому взаимно простому основанию и должны определяться как псевдопростые, ан нет, ошибается сильно реже чем 100% случаев, с чем связано не знаю.

[Yadryara]

Yadryara в сообщении #1720228 писал(а):

Перебор очень хорош тем, что другие степени факторов можно и не смотреть.

А вот как раз с перебором-то и ошибка. Надо смотреть другие степени: 3-ю, 7-ю и 15-ю. И для 3-й степени решения находятся:

Если частное разделилось один раз на 79 и один раз на 83, то оно может разделиться ещё два раза на 79. Вот и получилось 8 делителей. По счастью такие числа получаются всё-таки маленькими, исходя из проверки до $2^{20}$, верхняя граница — $1.21 \cdot 10^{24}$.

Если частное разделилось один раз на 79, один раз на 83 и один раз на 89, то оно может разделиться ещё два раза на 79. Вот и получилось 16 делителей. По счастью такие числа получаются всё-таки маленькими, исходя из проверки до $2^{20}$, верхняя граница — $1.27 \cdot 10^{30}$.

[Dmitriy40]

Yadryara
Ещё совсем недавно все высшие степени (выше первой) приводили к отказу цепочки. Потому что считалось что они слишком редки и ещё реже таки дают решения, а проверка их стоит ресурсов (времени) и себя не оправдывает. Мы же не ищем минимальное решение.
Тем более что сделать такую проверку тривиально: k=valuation(n,p) и в k будет максимальная степень p.
Но учитывая редкость таких делителей не думаю что их проверка как-то ускорит программу.

[Yadryara]

Dmitriy40 в сообщении #1720322 писал(а):

Но учитывая редкость таких делителей не думаю что их проверка как-то ускорит программу.

Не понимаю к чему это сказано.

Меня интересовала корректность работы алгоритма. Не хочется отбрасывать цепочки, если они могут оказаться годными. И пока что проверка показывает, что таких отбрасываний не происходит. По причине малости экзотических случаев.

Хотя, вот уже 36-ю степень десятки насчитал.

6-я фильтрация пока реализована так:

111112222233333

Проход по всем оставшимися местам и для тех мест, где дельта ровно 1 (в примере таких мест 5), частные сортируются по убыванию.

Далее для каждого места осуществляется проверка по Полларду, 30 тысяч итераций.

Если фактор найден,

то проверяем частное самой быстрой командой !ispseudorprime(cha,1).

Ежели определено, что частное составное, это значит, что в разложении частного есть ещё как минимум один фактор, а значит имеется перебор.

Но и при переборе возможны 8 делителей на этом месте. Например:

На 4-м этапе найден фактор 79.
На 6-м этапе Поллардом найден 7-12-значный фактор.
Частное — составное. И вполне может и 2-й и 3-й раз разделиться на 79.

Три фактора 79      — 4 делителя
7—12-значный фактор — 2 делителя
_________________________________
                      8 делителей

e6 * e7—e12 * e12   ——>   e6 * e7—e12 * e6 * e6   ——>   e25-e30     маловато

Но и при переборе возможны 16 делителей на этом месте. Например:

На 4-м этапе найдены факторы 79 и 83.
На 6-м этапе Поллардом найден 7-12-значный фактор
Частное — составное. И вполне может и 2-й и 3-й раз разделиться на 79.

Три фактора 79      — 4 делителя
Один фактор 83      — 2 делителя
7—12-значный фактор — 2 делителя
_________________________________
                     16 делителей

e6 * e6 * e7—e12 * e12   ——>   e6 * e6 * e7—e12 * e6 * e6   ——>   e31-e36     маловато

[wrest]

Dmitriy40 в сообщении #1720322 писал(а):

Потому что считалось что они слишком редки и ещё реже таки дают решения, а проверка их стоит ресурсов (времени) и себя не оправдывает.

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

-- 16.03.2026, 10:24 --

Yadryara в сообщении #1720324 писал(а):

На 6-м этапе Поллардом найден 7-12-значный фактор
Частное — составное. И вполне может и 2-й и 3-й раз разделиться на 79.

Ну не знаю, тут пример нужен. Поллард же ищет мелкие множители, с чего бы им отложиться в частное?

[Yadryara]

wrest в сообщении #1720328 писал(а):

Ага, высшие степени вносят сумятицу в учёт, т.к. квадрат увеличивает количество делителей в три раза, а две первых степени в четыре.

Ну вот я и разбираюсь, чтобы не было никакой сумятицы.

wrest в сообщении #1720328 писал(а):

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

Именно квадраты как раз ни к чему, ибо 8 или 16 делителей можно собрать только из кубов, 7-х и 15-х степеней. Возможно, вы имели в виду все степени старше первой.

wrest в сообщении #1720328 писал(а):

Ну не знаю, тут пример нужен.

Пример с числом 79 как раз был выше. Впрочем, могу ещё раз расписать.

wrest в сообщении #1720328 писал(а):

Поллард же ищет мелкие множители, с чего бы им отложиться в частное?

Не понял вопроса. Что значит отложиться в частное?

На всякий случай: при каждом вызове реализованный алгоритм Поллард ищет не мелкие множители, а ровно один фактор, который, вероятнее всего, самый мелкий и к тому же простой.

[Yadryara]

Стал ещё раз перепроверять, пример ещё раз вспомнил. Всё-таки наиболее вероятный расклад такой:

Но и при переборе возможны 8 делителей на этом месте. Например:

На 4-м этапе найден фактор 79.
На 6-м этапе алгоритмом Полларда найден фактор 79.
Частное — составное. И вполне может в 3-й раз разделиться на 79.

Три фактора 79 — 4 делителя
Частное        — 2 делителя
____________________________
                 8 делителей

Но и при переборе возможны 16 делителей на этом месте. Например:

На 4-м этапе найдены факторы 79 и 83.
На 6-м этапе алгоритмом Полларда найден фактор 79.
Частное — составное. И вполне может в 3-й раз разделиться на 79.

Три фактора 79      — 4 делителя
Один фактор 83      — 2 делителя
Частное             — 2 делителя
_________________________________
                     16 делителей

И ограничение на величину частного сверху неуместно. То есть получается что непрерывные цепочки всё-таки могли быть пропущены.

[Dmitriy40]

Yadryara в сообщении #1720330 писал(а):

На всякий случай: при каждом вызове реализованный алгоритм Поллард ищет не мелкие множители, а ровно один фактор, который, вероятнее всего, самый мелкий и к тому же простой.

Ошибаетесь:
42: [1, 1, 21, 2]
242: [1, 2, 22, 11]
1024: [1, 2, 64, 16]
И ещё огромное море других комбинаций.

[Yadryara]

Dmitriy40 в сообщении #1720339 писал(а):

Ошибаетесь:
42: [1, 1, 21, 2]

В чём ошибаюсь? В том, что не уточнил уж не знаю в какой раз, что речь идёт о разложении актуальных, то бишь не менее чем 39-значных чисел?

Будьте добры, покажите релевантный пример. Чтобы найденный алгоритмом Полларда фактор был хотя бы 25 знаков, а частное — 7-12.

[Dmitriy40]

Yadryara в сообщении #1720340 писал(а):

В чём ошибаюсь?

В том что минимальный делитель и в том что он простой. Банальный контрпример:
$\forall k \in N: n=21\cdot10^k: [1, 1, 21, 10^k]$
21 конечно меньше остатка (кроме $k=1$), вот только ну совсем не простое и точно не минимальный делитель (там ещё и 2 и 5 и 10 и 20 (для $k>1$) есть в остатке).
И числа $n$ хоть 39-значные (при $k=37$), хоть 100500-значные, $k$ выше может быть любым.
В частности при $k=1$ делитель больше остатка:
210: [1, 1, 21, 10]

Ещё пара примеров:
428689: [1, 5, 25217, 17]
439375: [1, 3, 87875, 5]

-- 16.03.2026, 14:35 --

Вот Вам ещё 39-значный контрпример с простым остатком:
210000000000000000000000000000000000903: [1, 1, 21, 10000000000000000000000000000000000043]
А вот вообще $21^{29}$:
220983347100817338120002444455525554981: [1, 1, 21, 10523016528610349434285830688358359761]

-- 16.03.2026, 14:47 --

Yadryara в сообщении #1720340 писал(а):

Чтобы найденный алгоритмом Полларда фактор был хотя бы 25 знаков, а частное — 7-12.

Это ищите сами, обе части Вашего утверждения я опровергнул, и вместе и по отдельности.
Подсказка: найденный делитель зависит от инициализации x,y, их подбором можно получить достаточно произвольный делитель, в том числе и больше остатка. Но я подбирать 25-значную инициализацию не собираюсь.

-- 16.03.2026, 15:20 --

Yadryara
Впрочем, оказалось всё проще, вот вам пример (инициализацию не менял):
100000000000154338435947053816616724069: [1, 6, 306811686917208776117540917, 325932825457]
Такой устраивает или опять что-то не так?
Использовался Ваш код отсюда без изменений.

[Yadryara]

Dmitriy40 в сообщении #1720343 писал(а):

Это ищите сами, обе части Вашего утверждения я опровергнул,

Не вижу релевантного примера.

И тем более не вижу опровержения.

Dmitriy40 в сообщении #1720343 писал(а):

Это ищите сами,

А что значит "ищите сами"? Зачем? У меня накопилось немало статистики, несколько сотен разложений, я её ранее частично опубликовал. И картина вроде бы ясна.

Ну вот ещё могу показать из 7-й фильтрации, где исходное частное(2-й справа столбец) порой поменьше бывает чем в 6-й. Я не сортировал. Как алгоритм выдаёт, так и показываю. Фактор, который находит алгоритм (3-й справа столбец) — 7-12 знаков, а частное гораздо больше.

Всегда ли этот фактор здесь простой, пока не проверял.

(Оффтоп)

16         5        415 ms        1     16959        9     46   Perebor2
14        10        914 ms        1      8055        9     51   Nedobor
14         8        913 ms        1      3311        8     54   Nedobor
9          7        638 ms        1     28709        9     42   Nedobor3
12        11      1,028 ms        1     14749        9     42   Perebor2
14         2        129 ms        1     24535        9     55   Nedobor
14         2        190 ms        1     23144       11     46   Nedobor3
12         6        494 ms        1      1404        7     53   Nedobor
13         2        154 ms        1     33140       10     47   Nedobor3
11         1         46 ms        1     38998       10     50   Nedobor3
10         6        493 ms        1      1818        7     46   Nedobor3
10         3        210 ms        1     11442        8     55   Nedobor
18         2        160 ms        1     50805       10     56   Nedobor
12         3        216 ms        1      1546        7     54   Nedobor
16         9        838 ms        1     40932       10     55   Nedobor
14         1         29 ms        1     24138        9     56   Nedobor
13         8        715 ms        1      1877        7     52   Nedobor
12         4        306 ms        1      1725        7     55   Nedobor
17         6        525 ms        1      1303        7     55   Nedobor
10         1          3 ms        1      2188        8     57   Nedobor
13         1         85 ms        1     71576       11     56   Nedobor
7          1          1 ms        1       583        7     56   Nedobor
8          2        108 ms        1      7975        8     55   Nedobor
6          3        204 ms        1      4296        8     45   Nedobor3
10         4        306 ms        1      7299        8     47   Nedobor3
14         1         95 ms        1     80717        10     56   Nedobor
11         3        198 ms        1     892        7     55   Nedobor
11         4        324 ms        1     19414        9     55   Nedobor
11         9        802 ms        1     5900        8     52   Nedobor
17         1         27 ms        1     20430        10     49   Nedobor3
13         2        198 ms        1     82568        10     56   Nedobor
12         2        113 ms        1     11260        10     56   Nedobor
15         6        547 ms        1     40120        11     48   Perebor2
13        13      1,170 ms        1     16184        9     48   Nedobor
8          4        315 ms        1     10536        9     45   Perebor2
15         2        114 ms        1     11538        8     56   Nedobor
15         6        504 ms        1     6255        8     47   Nedobor3
13         4        352 ms        1     41268        9     48   Perebor2
15         1         34 ms        1     18611        9     48   Nedobor3
15         4        300 ms        1     3344        7     55   Nedobor
13         1          6 ms        1     5312        7     55   Nedobor
9          1          3 ms        1     2637        8     56   Nedobor
11         2        105 ms        1     3694        8     56   Nedobor
13         3        201 ms        1     1296        7     56   Nedobor
13         1         71 ms        1     48419        10     48   Nedobor3
11         5        477 ms        1     71100        10     55   Nedobor
10         1          1 ms        1     203        7     56   Nedobor
10         8        720 ms        1     18990        9     43   Nedobor3
11         9        846 ms        1     35642        10     42   Perebor2
12         4        315 ms        1     1344        7     47   Nedobor3
12         3        240 ms        1     36054        10     55   Nedobor
13        10        926 ms        1     2616        7     52   Nedobor
9          3        201 ms        1     2649        7     54   Nedobor
10         1         18 ms        1     15670        9     55   Nedobor
13         4        343 ms        1     42336        9     48   Nedobor3
10         3        285 ms        1     73888        10     54   Nedobor
14         1         60 ms        1     50890        10     57   Nedobor
12         8        821 ms        1     80604        10     45   Nedobor3
14         8        707 ms        1     3362        8     53   Nedobor
13         2        107 ms        1     6090        9     55   Nedobor
11         1         87 ms        1     43688        11     48   Nedobor3
14         2        104 ms        1     4534        8     49   Perebor2
12         2        180 ms        1     67959        11     55   Nedobor
12         2        143 ms        1     36121        12     55   Nedobor
10         3        274 ms        1     65894        10     53   Nedobor
11         2        110 ms        1     8192        9     49   Perebor2
15         2        108 ms        1     1248        7     56   Nedobor
12         9        900 ms        1     10935        9     45   Nedobor3
15         1          3 ms        1     2694        7     57   Nedobor
15         6        580 ms        1     2880        7     49   Perebor2
11        11        997 ms        1     6454        9     42   Nedobor3
15         4        444 ms        1     30668        9     55   Nedobor
9          1          4 ms        1     3660        7     56   Nedobor
14        10        905 ms        1     11400        8     52   Nedobor
12         3        204 ms        1     4592        9     55   Nedobor
14         6        611 ms        1     75645        10     47   Nedobor3
11         2        102 ms        1     2074        7     54   Nedobor
16         2        161 ms        1     53426        10     49   Nedobor3
13         1         79 ms        1     66568        12     57   Nedobor
13         4        309 ms        1     10202        8     47   Perebor2
10         1          2 ms        1     1292        7     50   Nedobor3
14         2        135 ms        1     28668        9     48   Nedobor3
12         2        119 ms        1     12118        8     55   Nedobor
13         4        305 ms        1     5813        8     48   Perebor2
10         2        104 ms        1     3752        7     56   Nedobor
13        10        930 ms        1     1623        8     52   Nedobor
11         1        2 ms        1     1749        7     57   Nedobor
13        11        989 ms        1     4113        7     51   Nedobor
10         1        88 ms        1     73788        10     49   Nedobor3
13         8        800 ms        1     61764        10     45   Perebor2
15         1        2 ms        1     1341        7     57   Nedobor
13        10        975 ms        1     20508        9     53   Nedobor
12         1        2 ms        1     2056        7     54   Nedobor
14         4        379 ms        1     59057        11     55   Nedobor
14         1        46 ms        1     33916        10     49   Nedobor3
9          1        61 ms        1     51779        9     55   Nedobor
15         1        4 ms        1     3558        8     56   Nedobor
10         6        500 ms        1     8694        8     51   Nedobor
10         1        83 ms        1     70656        11     56   Nedobor
16         3        329 ms        1     79272        11     56   Nedobor
15         2        102 ms        1     1575        7     55   Nedobor
12         3        201 ms        1     2250        7     49   Nedobor3
11        10        938 ms        1     9720        9     41   Nedobor3
12         6        505 ms        1     3106        9     54   Nedobor
12         9        832 ms        1     4152        9     50   Nedobor
13         8        691 ms        1     10088        10     52   Nedobor
15         3        204 ms        1     3232        7     46   Nedobor3
12         3        217 ms        1     3546        8     47   Nedobor3
9          3        240 ms        1     15031        9     46   Nedobor3
9          1        2 ms        1     1844        9     56   Nedobor
10        10        902 ms        1     1868        7     50   Nedobor
9          2        141 ms        1     29914        10     46   Perebor2
12         1        83 ms        1     69292        10     48   Nedobor3
14         1        5 ms        1     4347        8     57   Nedobor
13         8        761 ms        1     40916        10     52   Nedobor
11         1        3 ms        1     2062        7     57   Nedobor
14         1        46 ms        1     39560        9     50   Nedobor3
12         3        203 ms        1     910        7     55   Nedobor
13         8        700 ms        1     4508        8     46   Nedobor3
14         1        72 ms        1     61137        10     56   Nedobor
10         2        136 ms        1     29177        9     49   Nedobor3
12         2        118 ms        1     15708        9     49   Perebor2
14         3        309 ms        1     24756        9     47   Perebor2
10         8        766 ms        1     5254        9     53   Nedobor
13         6        511 ms        1     12596        9     54   Nedobor
12         1        3 ms        1     2662        7     56   Nedobor
10         4        368 ms        1     19165        8     55   Nedobor
12         1        2 ms        1     1256        7     57   Nedobor
13         1        9 ms        1     7356        9     56   Nedobor
12         5        441 ms        1     17291        9     46   Perebor2
13         4        328 ms        1     19878        9     55   Nedobor
16         1        1 ms        1     849        7     55   Nedobor
11         2        131 ms        1     25898        9     50   Perebor2
14         1        2 ms        1     1890        7     57   Nedobor
14         1        1 ms        1     444        7     57   Nedobor
9          5        415 ms        1     1050        7     53   Nedobor
12         4        372 ms        1     24424        9     35   Perebor3
15         6        516 ms        1     777        7     54   Nedobor
9          3        193 ms        1     2353        7     54   Nedobor
10         8        721 ms        1     27637        10     51   Nedobor
16         4        298 ms        1     884        8     48   Perebor2
11         1        10 ms        1     5196        8     49   Perebor2
15         2        125 ms        1     20853        10     57   Nedobor
13         5        551 ms        1     74746        10     46   Perebor2
13         1        9 ms        1     7176        8     56   Nedobor
9          1        16 ms        1     13253        9     56   Nedobor
13         3        217 ms        1     17299        9     54   Nedobor
12         6        525 ms        1     26926        10     54   Nedobor
17         4        346 ms        1     8241        8     56   Nedobor
16         2        120 ms        1     11005        8     48   Nedobor3
12         3        222 ms        1     14883        9     54   Nedobor
14         2        102 ms        1     844        7     56   Nedobor
9          3        222 ms        1     2070        7     55   Nedobor
14         1        41 ms        1     34779        10     56   Nedobor
15         4        407 ms        1     79993        12     55   Nedobor
12         2        112 ms        1     9893        9     48   Perebor2
12         3        201 ms        1     2750        8     55   Nedobor
9          2        133 ms        1     28194        9     54   Nedobor
11         1        57 ms        1     48888        9     50   Perebor2
13         3        281 ms        1     62882        10     46   Perebor2
12         2        106 ms        1     5544        7     48   Nedobor3
15         4        331 ms        1     3679        8     49   Perebor2
18         1        19 ms        1     11121        9     48   Perebor2
15         8        753 ms        1     40021        10     54   Nedobor
12         9        828 ms        1     26892        8     52   Nedobor
10         5        497 ms        1     18973        9     55   Nedobor
11         6        497 ms        1     2436        8     55   Nedobor
17         3        245 ms        1     34194        11     48   Perebor2
11         5        414 ms        1     16788        9     47   Perebor2
11         1        19 ms        1     15408        8     55   Nedobor
12         1        45 ms        1     33820        9     47   Nedobor3
8          5        426 ms        1     3484        9     51   Nedobor
13         4        339 ms        1     3447        7     54   Nedobor
10         2        107 ms        1     7546        9     48   Nedobor3
11         9        892 ms        1     82485        11     44   Nedobor3
12         5        416 ms        1     3910        8     48   Nedobor3
13         5        428 ms        1     28576        11     54   Nedobor
15         2        109 ms        1     5632        8     48   Nedobor3
14         6        521 ms        1     3904        7     46   Perebor2
10         8        815 ms        1     54720        10     52   Nedobor
13         3        271 ms        1     59742        10     55   Nedobor
15         7        779 ms        1     49057        11     45   Perebor2
8          6        516 ms        1     12936        10     47   Nedobor3
14         3        239 ms        1     23285        9     47   Nedobor3
12         2        181 ms        1     50346        9     47   Nedobor3
12         5        418 ms        1     6320        9     55   Nedobor
10         5        509 ms        1     13630        9     48   Nedobor3
12         3        200 ms        1     1394        7     55   Nedobor
13         4        337 ms        1     27749        9     46   Perebor2
15         2        202 ms        1     19344        10     56   Nedobor
13         3        222 ms        1     20656        9     55   Nedobor
12         3        229 ms        1     26526        11     55   Nedobor
17        16        1,573 ms        1     17766        10     41   Perebor2
12         3        204 ms        1     5518        7     55   Nedobor
12         5        413 ms        1     16890        9     54   Nedobor
11         1        31 ms        1     16944        11     49   Nedobor3
11         3        266 ms        1     58810        10     54   Nedobor
14         1        64 ms        1     44652        11     48   Perebor2
13         1        48 ms        1     30495        10     48   Nedobor3
13         2        105 ms        1     3662        8     49   Nedobor3
8          7        617 ms        1     1172        7     53   Nedobor
12         2        109 ms        1     1101        8     55   Nedobor
11         3        317 ms        1     13848        10     55   Nedobor
10         8        706 ms        1     18082        10     50   Nedobor
13         6        608 ms        1     1570        8     54   Nedobor
10         5        498 ms        1     83472        10     46   Nedobor3
15         4        410 ms        1     82948        11     55   Nedobor
14         5        413 ms        1     14016        9     48   Nedobor3
12         2        117 ms        1     15051        8     55   Nedobor
11         3        228 ms        1     23141        9     55   Nedobor
13         7        620 ms        1     19686        8     55   Nedobor
13         6        533 ms        1     32114        9     54   Nedobor
11         4        356 ms        1     9500        9     47   Nedobor3
9          5        430 ms        1     5202        9     47   Nedobor3
14         5        431 ms        1     21436        9     46   Nedobor3
10         1        46 ms        1     29734        9     49   Nedobor3
12         1        27 ms        1     21658        10     57   Nedobor

[Dmitriy40]

Dmitriy40 в сообщении #1720343 писал(а):

Yadryara
Впрочем, оказалось всё проще, вот вам пример (инициализацию не менял):
100000000000154338435947053816616724069: [1, 6, 306811686917208776117540917, 325932825457]
Такой устраивает или опять что-то не так?
Использовался Ваш код отсюда без изменений.

Ещё:
100000000000965569336948487190758018697: [1, 6, 379614460084004078925092999, 263425160303]

-- 16.03.2026, 15:27 --

Yadryara в сообщении #1720348 писал(а):

Не вижу релевантного примера.

И тем более не вижу опровержения.

Смотрите лучше.
Я привёл кучу примеров когда найденный делитель не наименьший и не простой. Это две части вашего утверждения, обе опровергнуты, и вместе и по отдельности. И даже для так желаемых непонятно зачем 39-значных чисел.

-- 16.03.2026, 15:31 --

Т.е., ещё раз: алгоритм Полларда не гарантирует нахождение ни наименьшего делителя, ни его простоты. Найденный делитель может быть не наименьшим, быть больше остатка (частного) или быть составным, в том числе и больше и составным одновременно.

[Yadryara]

Dmitriy40 в сообщении #1720349 писал(а):

Такой устраивает или опять что-то не так?

Пока устраивает, ещё не проверял. Ну допустим, есть такой пример. Что он опровергает?

Dmitriy40 в сообщении #1720349 писал(а):

Я привёл кучу примеров когда найденный делитель не наименьший и не простой. Это две части вашего утверждения, обе опровергнуты, и вместе и по отдельности.

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

Dmitriy40 в сообщении #1720349 писал(а):

И даже для так желаемых непонятно зачем 39-значных чисел.

Потому что это минимальная значность, которую я до этого видел при тестировании реальных данных. Да, есть и поменьше. Что изменится, если я смягчу критерий и скажу про 30-значные?