For primes of current acceptable size (>= 1024 bits), you might as well drop those extra checks. The elliptic curve method gives you around 2^512 attempts at do

For primes of current acceptable size (>= 1024 bits), you might as well drop those extra checks. The elliptic curve method gives you around 2^512 attempts at doing the exact same thing, each one with the same probability of having a smooth p-1 or p+1. The paper you link to reaches essentially the same conclusion.