P Полларда p-1 полезен только тогда, когда для одного из простых чисел p, p-1 является гладким. Если у вас есть случайное целое число, которое вы хотите учесть, вы должны использовать ECM и GNFS. Это означает, что если вы пробуете p-1, у вас есть причина подозревать, что p-1 достаточно гладкая, и тогда вы уже должны иметь представление о том, насколько гладкой она может быть (граница гладкости L). В любом случае, чем больше вы пытаетесь - тем больше у вас шансов сломаться, поэтому вам следует ставить настолько большую границу, насколько вы можете позволить себе ждать, но только если у вас есть основания подозревать p-1 в гладкости.
Я верю, выбирая $а$ не имеет большого значения, и изменение $а$ вообще бесполезен, пока не получится нетривиальный $gcd$. Идея в том, что для новых $а$ надо умножить на все $1,2,3,...$ снова, в то время как вы уже сделали эту работу для предыдущего $а$. Вы можете получить новый $а$ такой, что какой-то большой множитель $д$ из $p-1$ уже удален, и тогда вам нужна меньшая граница $L$ работать, но шанс на это есть $1/день$ и вы скорее продолжаете поднимать свой оригинал $а$ к следующим полномочиям и достичь власти $д$ естественно.
Единственная проблема, которая может возникнуть - это то, что вы получите 1 мод. $р$ и 1 мод $q$ одновременно (т.е. получить $a^L\эквив 1 \mod{n}$), который не пропускает фактор. Тогда вы попробуете другой $а$, но по крайней мере вы узнаете, что Поллард $p-1$ вероятно, будет хорошо работать на этом числе.
