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

[Yadryara]

wrest. Всё нормально. 430 частных у вас должно быть в файле cha3.txt. Можете сверить с вашим кундштюком

Средняя длина частного — 65.78 десятичных цифр.

[wrest]

Yadryara
Ну, смотрите. Первые соображения такие. Все цепочки - валидные, т.е. в них везде по 192 делителя. Если я правильно вижу, то в каждой цепочке есть числа, которые факторизуются долго (3..15 секунд). Заметно (в разы) ускорить их факторизацию (универсально для всех) не выйдет в виду самой природы задачи факторизации. Отбрасывать "трудные" числа → терять каждую из 45 валидных цепочек.
Вопрос: чего же вы хотите, какого чуда ждёте?

[Dmitriy40]

Я вообще не вижу смысла ускорять факторизацию именно корректных цепочек. Потому что ускорять факторизацию - дело очень так себе.
Ускорить реально лишь факторизацию сложных частных (вызовом других более продвинутых программ типа YAFU), но как их определить - не совсем понятно.
Потому раньше упор всегда делался на "максимально быстро отбросить точно неподходящие кандидаты", а не на проверку точно подходящих. Для длинных паттернов это оправдано, подходящих кандидатов на порядки меньше всех вообще и потому время проверки точно подходящих роли почти не играло. И пока точно подходящие кандидаты валятся в разы медленнее чем потом проверяются - ну и пусть, основные тормоза получаются ведь не в них. Т.е. надо улучшать фильтрацию чтобы оставались как можно меньше самых-самых вероятно подходящих кандидатов, а на скорость финальной факторизации (про которую похоже и идёт речь последнее время) наплевать. Т.е. ускорять проверку не мест с 192 делителями, а мест с иным количеством делителей. Так что вопрос "а чего же хотите-то" очень даже закономерен.

[Yadryara]

Значит мы пришлю к той ситуации, которая возникает в рабочей программе после 6-й фильтрации.

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

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

"7-я фильтрация, проверка по псевдопростоте на недобор по оставшимся после предыдущей проверки местам.

8-я фильтрация, проверка на перебор с использованием алгоритма Полларда.

9-я фильтрация, более сложная проверка и на недобор и на перебор с использованием алгоритма Полларда.

10-я фильтрация. Окончательная проверка. Это единственная проверка с факторизацией. Пока по numdiv. Остаются только непрерывные цепочки длиной не меньше искомой."

Это уже немного устаревшее описание. Более подробно объяснять довольно долго. Но я по ходу конечно нюансы опишу.

Вам может быть проще самому понять какие проверки и в какой последовательности делать, тем более что 7-я фильтрация есть ещё даже в старой вашей функции em3.

Либо просто пишутся всевозможные тесты:

Проверили частные в такой последовательности и такими способами — получили такую скорость нахождения цепочек.

Проверили сяким способом — получили сякую скорость нахождения.

Сравнили. Подумали. Переписали код. Перезапустили. И так миллиард раз

Простор для творчества вроде пока есть. А потом уже можно будет переходить к более сложным вариантам, многопоточно, через Убунту, и конечно не только с хорошими частными, но и с плохими...

[wrest]

Yadryara
Вопрос: чего же вы хотите, какого чуда ждёте? ЧТО вы хотите ускорить?

Зачем вы сюда постили 66 чисел, 540 чисел, 45 цепочек? Что вы там хотели ускорять?

Я просто не понимаю.

Вы тоже поймите, пожалуйста! Эта тема - она не про цепочки, она про ускорение каких-то конкретных мест или участков кода, там где это возможно.

Если бы вы сразу сказали, что хотите ускорить полную факторизацию чисел вида pq/pqr длиной больше 210 бит с близкими делителями, то не было бы последних страниц, т.к. это просто невозможно алгоритмически в рамках pari/gp, где движок факторизации и так уже достаточно хороший (и в общем-то, гибкий). Не придумали ещё человеки новых быстрых алгоритмов полной факторизации. Всё 10..20-летней и более давности.

-- добавлено через 22 минуты --

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

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

Ну вот как раз при помощи пробной факторизации ECM, как в pari/gp и делается.
Если пробный ECM несдюжил - слать в YAFU.

[Yadryara]

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

Я просто не понимаю.

Вы вроде сказали что согласны набраться терпения. И мне тоже нужно его набраться. Я ведь уже и так и сяк объяснял. И пока мои возможности объяснять не исчерпаны.

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

Вы тоже поймите, пожалуйста! Эта тема - она не про цепочки, она про ускорение каких-то конкретных мест или участков кода, там где это возможно.

И про цепочки тоже. Не надо чрезмерно сужать тему, иначе придётся скакать по темам и толку не будет.

Ну вот есть, например, 28-е число. В нём только 7 частных.

28. 1.       68     8
28. 2.       66     4
28. 4.       65     4
28. 5.       64     4
28. 6.       68     8
28. 7.       66     8
28. 8.       69     8

Если исходить из того, что задача заключается в том, чтобы как можно быстрее отбрасывать цепочки, то надо начинать проверять с цепочки 66-4. Согласны? Сейчас-то вы обозначения понимаете?

Вот какие частные проверяем:

14869097725500963314128707547521096558601882008519609825980870702261   8
219892397150501152530302585806713970540751848060204381923013672613   4
25929360613761769851926868530302636955788469708139272387751169231   4
1704354382715100645176873532241505420029629477045879139736991019   4
69151462780609644670590974487324148808598964306793687583541718882489   8
374851412234731338898715009756835760077367564708285335899989890469   8
857352373232314471396054977383482200970314910148041602694268993763743   8

Вот какие временя проверки простым способом по команде factorint(cha, 4):

28. 1.       68     8     1278
28. 2.       66     4     1068
28. 4.       65     4     7654
28. 5.       64     4     7043
28. 6.       68     8      231
28. 7.       66     8     1715
28. 8.       69     8       80

Здесь не то что 10-секунлного времени нет, как в самых сложных случаях, здесь нет даже 8-секундного. Логично что надо проверять скорее варианты с 7-8-ю частными, чем с бо́льшим количеством?

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

Ну вот как раз при помощи проброй факторизации ECM, как в pari/gp и делается.
Если пробный ECM несдюжил - слать в YAFU.

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

[wrest]

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

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

Ну, с YAFU я вам не помощник, нет его у меня в планшете. Этот пост был скорее к Dmitriy40

-- добавлено через 6 минут --

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

Здесь не то что 10-секунлного времени нет, как в самых сложных случаях, здесь нет даже 8-секундного. Логично что надо проверять скорее варианты с 7-8-ю частными, чем с бо́льшим количеством?

Это всё мелкая какая-то возня. Вместо десяти секунд намного меньше - аж около восьми и вместо аж целых восьми чисел всего-то каких-то жалких шесть.

[Yadryara]

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

Зачем вы сюда постили 66 чисел, 540 чисел, 45 цепочек? Что вы там хотели ускорять?

66 чисел я постил для того чтобы вам понятно было о чём идёт речь. Для того чтобы не только я, но и другие люди могли понять, какой они величины, как раскладываются эти числа и за какое время...

Человек находится в творческом поиске. Чуть позже я решил, что 66 чисел это маловато и довёл их количество до 540 в 45 цепочках. Сейчас решил не лениться и довести-таки количество найденных цепочек до 100, хотя бы в серии с одним простым. Это ещё часов 10 счёта.

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

Что вы там хотели ускорять?

Я хотел ускорять скорость нахождения кортежей.

В том числе, как один из вариантов, ускорить скорость проверки частных. И это можно попробовать сделать на примере тех же 45 найденных цепочек.

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

Это всё мелкая какая-то возня.

Вот вы давеча говорили, что я выливаю на тёплый разговор ушат холодной воды.

А я вот вижу, что это раз за разом делаете вы. Вот вы недавно дважды сказали "разбирайтесь сами". А я вам хоть раз говорил "разбирайтесь сами"? Нет, наоборот, по мере сил помогаю разобраться.

Вы кстати, не ответили, обозначения понятны?

Теперь вот "мелкая возня". Ну уж какая есть, придумайте крупную возню, я совершенно не против.

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

Вместо десяти секунд намного меньше - аж около восьми и вместо аж целых восьми чисел всего-то каких-то жалких шесть.

Немного не такие цифры. Вот такие:

8 + 11 + 10 + 8 + 10 + 11 + 10 + 11 + 10 + 10 + 10 + 8 + 10 + 10 + 9 + 10 + 11 + 9 + 10 + 10 + 9 + 10 + 8 + 9 + 11 + 11 + 8 + 7 + 9 + 9 + 10 + 11 + 10 + 10 + 9 + 10 + 8 + 9 + 8 + 8 + 10 + 10 + 9 + 10 + 11 = 430

По временам напишу позже.

Скажите, а заранее было понятно что будут именно такие результаты, что вы назовёте их мелкой вознёй? Мне — нет. Собрали статистику, посмотрели, допустим, поняли — этот метод не даёт заметного ускорения. Отрицательный результат — тоже результат. Генерим другие идеи.

[wrest]

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

Вот вы недавно дважды сказали "разбирайтесь сами".

Так это относилось к вашему коду который вы не хотели приводить в удобный для разбирательства вид.

-- добавлено через 39 минут --

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

Скажите, а заранее было понятно что будут именно такие результаты, что вы назовёте их мелкой вознёй? Мне — нет.

Было бы понятно, если бы задача была сформулирована не "побыстрее найти кортежи" а "побыстрее полностью факторизовать числа вида pr/pqr размером 66 десятичных разрядов/210 бит".
Я же от вас постановки задачи ждал-ждал, но так и не дождался. Предположу, что вы считаете такую постановку мелкой вознёй, ведь впереди большая, крупная цель: рекорды, да и VAL в соседней теме поджимает

По сути. Пока что обойти по скорости встроенный в pari/gp движок факторизации средствами самого pari/gp не получалось.
Но я допускаю, что заранее зная что мы ищем именно числа вида pq/pqr можно тоньше настроить и получить небольшой (думаю, менее 40%) выигрыш. Для этого надо экспериментально, на конкретном наборе чисел, определить параметры перехода от ECM к MPQS. Но надо не метаться из стороны в сторону, не расширять количество чисел или их разрядность, а тестировать один и тот же набор, подбирая параметры так чтобы уменьшить общее время. Возможно даже, что надо будет факторизовать одно и тоже число десятки раз и найти оптимальные параметры, потом следующее и так далее.
Если вы готовы этим заняться, то я мог бы потратить время на подготовку инструментов. Вам останется их применять и аккуратно протоколировать. Успех не гарантирован. Если не готовы - то считаем это мелкой вознёй, не заслуживающей [вашего] внимания.

[Yadryara]

Я опять не торопясь буду действовать. Сначала в ход пойдёт самый простой в использовании numdiv. Вот у вас уже есть файл cha3.txt.

Берём, да смотрим пока хотя бы времена проверки:

default(parisizemax, 128M);
{kstrok = 0; kcep = 0; sumtime = 0;
print;
name = fileopen("cha3.txt");
while( stroka = filereadstr(name),
kstrok++;
if (stroka <> "", s = strsplit(stroka, "  "); cha = eval(s[1]); nudel = eval(s[2]);
t0=getwalltime(); nmdv = numdiv(cha); t1=getwalltime()-t0; sumtime += t1;
print(kstrok, "   ", cha, "   ", nmdv, "   ", nudel, "   ", t1, "   ", sumtime)
,
kcep ++;
print; print(kcep, ".   ", sumtime);print;
sumtime = 0;
));
}quit

А времена вот такие:

(45 цепочек)

Цепочка   Проверка
  номер     секунд

     1.         18
     2.         36
     3.         18
     4.         25
     5.         21
     6.         31
     7.         32
     8.         46
     9.         17
    10.         34
    11.         34
    12.         17
    13.         24
    14.         30
    15.         28
    16.         42
    17.         35
    18.          7
    19.         28
    20.         16
    21.         16
    22.          9
    23.         16
    24.          8
    25.         27
    26.         14
    27.         17
    28.         20
    29.         29
    30.         25
    31.         29
    32.         13
    33.         50
    34.         50
    35.         34
    36.         44
    37.         20
    38.         29
    39.         15
    40.         18
    41.         31
    42.         39
    43.         53
    44.         27
    45.         35

Округление — потолок.

Как видно: от 7 до 53 секунд. То есть налицо 7-кратная разница времени проверки.
И, можно, например попытаться понять, от чего же зависит такая большая разница в скорости между цепочками. Да сразу от многих вещей, в том числе от статистических показателей.

И, разумеется, с этим надо отдельно и не торопясь разбираться, чтоб не запутаться.

[wrest]

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

Как видно: от 7 до 53 секунд. То есть налицо 7-кратная разница времени проверки.
И, можно, например попытаться понять, от чего же зависит такая большая разница в скорости между цепочками. Да сразу от многих вещей, в том числе от статистических показателей.

И, разумеется, с этим надо отдельно и не торопясь разбираться, чтоб не запутаться.

Воот. Теперь начинает просматриваться подход.
Ну так-то вроде понятно, что время факторизации зависит от величины предпоследнего (по величине) делителя.
Давайте это подтвердим, а то вдруг там что-то иное
Рекомендую, для начала, записать а как именно встроенная факторизация работает, из чего сложились эти времена.
Для этого даём команду\g 4 и смотрим сколько занял поллард, сколько ecm (при том - сколько кривых перебиралось и с какими B1) и сколько mpqs.

[Yadryara]

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

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

Вот вы недавно дважды сказали "разбирайтесь сами".

Так это относилось к вашему коду который вы не хотели приводить в удобный для разбирательства вид.

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

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

Я же от вас постановки задачи ждал-ждал, но так и не дождался.

Надеюсь, дождётесь. Вот уже программу ещё одну привёл.

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

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

Предположу, что вы считаете такую постановку мелкой вознёй,

Неправильно предположили. Я же написал что по мере разбирательства у меня у самого многие моменты устаканивались и постепенно выявлялось что важное, а что второстепенное. И этот процесс ещё не закончен.

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

тестировать один и тот же набор, подбирая параметры так чтобы уменьшить общее время.

Кто же против-то. Какое-то время можно и на одном наборе разбираться. Вот у вас есть список из 45 цепочек и 430 частных для них. И, как видите, я уже начал разбираться. Нашёл ещё 17.

Конечно у меня есть желание объединить их, потому что статистика тем надёжнее, чем больше данных обрабатывается. Если не желаете, могу подождать. Будем пока говорить о 45 цепочках.

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

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

Конечно готов. И этим и много чем другим. Задача сложная, в рабочей программе около полутысячи строк, не считая пустых.

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

Было бы понятно, если бы задача была сформулирована не "побыстрее найти кортежи" а "побыстрее полностью факторизовать числа вида pr/pqr размером 66 десятичных разрядов/210 бит".

Так вот именно что непонятно, а надо ли их полностью факторизовывать или их надо в какой-то момент бросать.

И, что очень важно, это для цепочек D(192,12) частные бывают где-то около 66 разрядов, а для длины 15 они, возможно, будут существенно больше, например, за 80 разрядов. Это сильно от серии зависит. А серия — тоже много от чего.

-- добавлено через 10 минут --

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

Для этого даём команду\g 4

Этого не понял. Запускать не через консоль, как я сейчас, а через gp, то есть выйти на приглашение в виде вопроса и запускать в фигурных скобках? А потом, когда отработает, дать эту команду? Или наоборот заранее её дать?

[Yadryara]

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

Я вообще не вижу смысла ускорять факторизацию именно корректных цепочек.

Ну вот теперь я снова решил напечатать частные не только для корректных цепочек. Причём вроде ограничил это количество — печатаю только те, которые приходят на последнюю, 10-ю фильтрацию.

Так рабочая прога за 10 минут напечатала мне 600+ таких частных. Сколько же будет за 7 часов, пока длится заезд...

Они навряд ли понадобятся в таком количестве.

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

1   64867554139373969355590615382634973963247501826653501912565069007   4
1   34282412794615742830854327386042672766524057538471836360505682829743   8
1   88997384327116262100283422210050583976643900398423171438343759   4
1   38428018071462102341548619589968350181722832195671731667851346829743   8
1   18599535078782253855061632228579364099541230738712462206503496589743   8
2   905159848023161254659672678076789843028546704913670797141100272530123   8
2   1870127336520137962526291581585838108729254591747805592242729533330123   8
3   976316272525962892438249203569188378232563438451293717911651157   4
4   319405314701294932175318241445559588358195033853487248201315729141411   8
2   4493245272309123072854755469153153134933261561001759535180720169   4
1   32295016807490823042346054730187883031078783853950946831016817549743   8
2   1870078940459684045521259474606403291546522792763031595107297821330123   8
1   26700919414513035695029929483648329070805878223586752180351425115219   8
2   254140289740426978003600802016936630437158631069153620025049080261   4
5   7421193001819519578628560261450435110606744856824537183335500329   4

[Dmitriy40]

Yadryara
Мне остаётся только повторить:

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

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

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

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

Все формата 4 (pq) кроме последнего имеют именно pq и разлагаются медленно (QS). Т.е. разлагать их смысла мало.
Формата 8 (pqr) 3шт реально имеют pq и тоже медленно. И ещё 2шт с правильным pqr тоже медленно.
Вердикт: надо улучшать фильтрацию.

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

-- добавлено через 4 минуты --

Но только: меня опять же интересует лишь первое любое решение, а не 100500 в неделю, это Вы уж сами как-нибудь.

[wrest]

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

Этого не понял. Запускать не через консоль, как я сейчас, а через gp, то есть выйти на приглашение в виде вопроса и запускать в фигурных скобках? А потом, когда отработает, дать эту команду? Или наоборот заранее её дать?

Используется синтаксис Text

? \g 4
? factor(105757311957308040904820229090204467693408243851750161314519534535367)
IFAC: cracking composite
        105757311957308040904820229090204467693408243851750161314519534535367
IFAC: checking for pure square
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 226-bit integer
Rho: using X^2+3 for up to 14620 rounds of 32 iterations
Rho: time =     28 ms,  1108 rounds
        found factor = 548226331
IFAC: cofactor = 192908122023982173349532583998057670260657808228751714799557
IFAC: factor 192908122023982173349532583998057670260657808228751714799557
        is composite
IFAC: factor 548226331
        is prime
IFAC: prime 548226331
        appears with exponent = 1
IFAC: main loop: 1 factor left
IFAC: cracking composite
        192908122023982173349532583998057670260657808228751714799557
IFAC: checking for pure square
IFAC: trying Pollard-Brent rho method
Rho: searching small factor of 197-bit integer
Rho: using X^2+7 for up to 7591 rounds of 32 iterations
Rho: time =     21 ms,  1536 rounds
Rho: fast forward phase (512 rounds of 64)...
Rho: time =     10 ms,  2052 rounds, back to normal mode
Rho: time =      5 ms,  2560 rounds
Rho: time =      5 ms,  3072 rounds
Rho: fast forward phase (1024 rounds of 64)...
Rho: time =     20 ms,  4100 rounds, back to normal mode
Rho: time =      5 ms,  4608 rounds
Rho: time =      5 ms,  5120 rounds
Rho: time =      5 ms,  5632 rounds
Rho: time =      6 ms,  6144 rounds
Rho: time =      0 ms,  Pollard-Brent giving up.
IFAC: trying Shanks' SQUFOF, will fail silently if input
      is too large for it.
IFAC: trying Lenstra-Montgomery ECM
ECM: working on 16 curves at a time; initializing for up to 6 rounds...
ECM: time =      0 ms
ECM: B1 = 1000, B2 = 110000,    gss =  128*420
ECM: time =     43 ms, B1 phase done, p = 1009, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 1219
ECM: time =     30 ms
ECM: B1 = 1300, B2 = 143000,    gss =  128*420
ECM: time =     54 ms, B1 phase done, p = 1301, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 1511
ECM: time =     38 ms
ECM: B1 = 1600, B2 = 176000,    gss =  128*420
ECM: time =     65 ms, B1 phase done, p = 1601, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 1811
ECM: time =     45 ms
ECM: B1 = 2000, B2 = 220000,    gss =  128*420
ECM: time =     78 ms, B1 phase done, p = 2003, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 2213
ECM: time =     55 ms
ECM: B1 = 2450, B2 = 269500,    gss =  128*420
ECM: time =     95 ms, B1 phase done, p = 2459, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 2671
ECM: time =     66 ms
ECM: B1 = 2950, B2 = 324500,    gss =  256*420
ECM: time =    111 ms, B1 phase done, p = 2953, setting up for B2
ECM: time =      1 ms, entering B2 phase, p = 3163
ECM: time =     77 ms,  ellfacteur giving up.
IFAC: trying MPQS
MPQS: number to factor N = 192908122023982173349532583998057670260657808228751714799557
MPQS: factoring number of 60 decimal digits
MPQS: sieving interval = [-80000, 80000]
MPQS: size of factor base = 4801
MPQS: striving for 4811 relations
MPQS: coefficients A will be built from 8 primes each
MPQS: primes for A to be chosen near FB[135] = 1429
MPQS: smallest prime used for sieving FB[13] = 67
MPQS: largest prime in FB = 98621
MPQS: bound for `large primes' = 7889680
MPQS: computing relations: 1% 2% 3% 4% 5% 6% 7% 8% 9% 10% 11% 12% 13% 14% 15% 16% 17% 18% 19% 20% 21% 22% 23% 24% 25% 26% 27% 28% 29% 30% 31% 32% 33% 34% 35% 36% 37% 38% 39% 40% 41% 42% 43% 44% 45% 46% 47% 48% 49% 50% 51% 52% 53% 54% 55% 56% 57% 58% 59% 60% 61% 62% 63% 64% 65% 66% 67% 68% 69% 70% 71% 72% 73% 74% 75% 76% 77% 78% 79% 80% 81% 82% 83% 84% 85% 86% 87% 88% 89% 90% 91% 92% 93% 94% 95% 96% 97% 98% 99% 100%
MPQS: starting Gauss over F_2 on 4813 distinct relations
MPQS: Gauss done: kernel has rank 63, taking gcds...

MPQS: time in Gauss and gcds = 37 ms
MPQS: found 2 factors =
        2520040504432747640402108423,
        76549611676739743990529833666259
IFAC: factor 76549611676739743990529833666259
        is prime
IFAC: factor 2520040504432747640402108423
        is prime
IFAC: prime 2520040504432747640402108423
        appears with exponent = 1
IFAC: main loop: 1 factor left
IFAC: prime 76549611676739743990529833666259
        appears with exponent = 1
IFAC: main loop: this was the last factor
IFAC: found 3 large prime (power) factors.
time = 2,897 ms.
%232 = 
[                       548226331 1]

[    2520040504432747640402108423 1]

[76549611676739743990529833666259 1]

? 

Мы там виидим как последовательно применяются разные методы. Сперва поллард, который нашёл делитель. Потом поллард уже не смог, попробовали ECM, последовательно с B1=1000,1300,1600,2000,2450,2950 - не вышло, перешли к MPQS который и разложил число окончательно. Но если бы не разложил (получились найденный множитель или частное составные), то опять бы пробовали ECM, MPQS и так до победного конца.
За чем именно там стоит смотреть: ну вот встроенная факторизация сдалась в методе ECM на B1=2950.
Оправдано ли это? Почему не раньше (при меньшем B1) или почему не позже (при большем B1).
Что будет если отключить полларда, найдёт ли ECM малый множитель так же быстро (ответ: да).
Ну и так далее.