2020.03.24 16:51:11 (1242479081859338240) from Daniel J. Bernstein, replying to "Martin R. Albrecht (@martinralbrecht)" (1242432452611780608):
A large prime q has chance only about R^2/q^2 of appearing as a stray prime. The total number of such q > R^3 is O(1/R); i.e., practically guaranteed not to happen. ECM finds all q <= R^3 in R^o(1) modular operations. Should be easy to double-check this with an implementation.
2020.03.24 18:25:56 (1242502924468510720) from Daniel J. Bernstein:
The gcd inputs have R^(1+o(1)) bits, so the output can't have more bits, so each modular operation costs at most R^(1+o(1)) bit operations. The ECM stage thus uses at most R^(1+o(1)) bit operations. This works for any R^O(1) bound on the stray primes that appear.