In Shor's algorithm we require the period to be even. If the period is not even or $x^{r/2}+1 \equiv 0 \bmod N$ then we have to restart the process and pick a new random $x$. Why do we know that the process will work for some $x$ and still be quicker than the current method of just checking if factors work?
(Here $r$ is the period, $x$ is the random number given at the start of Shor's, $N$ is the number to be factorised.)