Pollard's $p-1$ method will likely find $p$ quickly if $p-1$ is a least common multiple of positive integers, all of which are small. (To put it another way, $p-1$ is a product of small primes, none of which is repeated too many times.)

There are analogous methods that target $p+1$ or any other product of cyclotomic polynomials in $p$; the key is to compute in a different group modulo $p$. Computation in $F_{p^{2}}^{\times}$, for example, can be accomplished using sequences satisying second-order linear recurrences, using $2 \times 2$ matrices, or other methods.

Also, if there is a small (positive integral) multiplier $c$ such that $n$ has a divisor $d$ such that $cd$ and $\frac{n}{d}$ are very close, a variant of Fermat's method with multipliers will factor $n$ by finding $cn = (\frac{cd+\frac{n}{d}}{2})^{2}-(\frac{cd-\frac{n}{d}}{2})^{2}$. (This assumes that $c$ will not interfere with the calculation of $\gcd (cd,n)$. But if $c$ is small, then trial division up to $c$, among other methods, can rule out $n$ having such small prime factors.)