What is the best strategy to avoid getting even orders in Shor's algorithm? I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.  But is there a relationship between safe primes and the order of an element being even? In other words, is $N = pq$ --- where $p$, $q$ are safe primes --- the hardest integer for Shor's algorithm?

I'm not interested in order-finding.  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?
I do understand Shor's algorithm wants the order of an element to be even so that it can use the factoring identity and find a non-trivial factor.


Not really; to factor, all you need is a value $e$ such that $x^e \equiv 1 \pmod{N}$ a nontrivial fraction of the time (and practically it would be sufficient if it holds with probability $2^{-30}$ for random $x$); it doesn't matter if $e$ is even or odd.

And Shor's will hand you such an $e$ with quite high probability.


  I'm only interested in the classic-side of Shor's algorithm.  How can I slow Shor's algorithm down?


You can't; or at least, not to any significant extent.  If the attacker gets his hands on such an $e$, then the time taken by the classic-side of Shor's is utterly tiny compared to the Quantum side of things...


  is $N=pq$ --- where $p, q$ are safe primes --- the hardest integer for Shor's algorithm?


In some odd sense, that's the easy case.  If the attacker obtains any $x, e$ pair with $x^e \equiv 1$, $x \not\equiv 1, N-1$ and $e &gt; 0$ and not ridiculously huge, it's straight-forward to factor $N$ with simple algebra.  In contrast, if we select $p, q$ with $\gcd(p-1, q-1)$ large, these simple algebraic methods often don't work; the attacker might have to resort to simple number theoretical attacks (but, as above, other than taking a small amount of additional time, they don't really have a drawback...)