This terminology is considered obsolete by the cryptography industry: the ECM factorization method is more efficient than Pollard's algorithm and finds safe prime factors just as quickly as it finds non-safe prime factors of similar size, thus the size of p is the key security parameter, not the smoothness of p-1.
Check at each stage, or once at the end if you prefer, whether gcd(x − 1, n) is not equal to 1.
Since the algorithm is incremental, it is able to keep running with the bound constantly increasing.
Assume that p − 1, where p is the smallest prime factor of n, can be modelled as a random number of size less than √n.
After completing the first stage, which is the same as the basic algorithm, instead of computing a new for B2 and checking gcd(aM' − 1, n), we compute where H = aM and check if gcd(Q, n) produces a nontrivial factor of n. As before, exponentiations can be done modulo n. Let {q1, q2, …} be successive prime numbers in the interval (B1, B2] and dn = qn − qn−1 the difference between consecutive prime numbers.
Hence, the values of H2, H4, H6, … (mod n) can be stored in a table, and Hqn be computed from Hqn−1⋅Hdn, saving the need for exponentiations.