Given a specific $\mathbb Z^*_n$, what is the probability that a random element has odd multiplicative order? While writing an answer over on Cryptography StackExchange where I argued why being able to compute $\operatorname{ord}(a,n)$ (finding the multiplicative order of an element $a$ in $\mathbb Z_n^*$) allows you to efficiently factor $n$ I stumbled over an issue I'm highly unsure about.

Let $n\in\mathbb N$ be $n>2$. Pick an $a\in\mathbb Z_n^*$ uniformly at random. What is the probability that $a$ has odd multiplicative order? 
I think this probability should be non-negligible, given that all subgroups must be covered by all $a$ and given that $\mathbb Z_n^*$ always has even order. But I don't know whether this hints towards a probability larger than 50% ("for every oddly ordered element there must also be at least one corresponding evenly ordered element") or what the exact (or at least approximate) probability is.
 A: This is probably hard to decide.
Take an easy case, when $\mathbb Z_n^*$ is cyclic. This happens, for instance, when $n$ is prime.
Write $\phi(n)=2^e m$ with $m$ odd and $e\ge 1$. Then $a$ has odd order iff $a$ is in the subgroup of order $m$. Since $1$ has even order $0$, the probability of $a$ having odd order is $$\dfrac{m-1}{\phi(n)}=\dfrac{m-1}{2^e m} < \dfrac{m}{2^em} = \dfrac{1}{2^e} \le \dfrac12$$
Thus, the probability is always strictly less than $\frac12$ and may be $0$, when $n$ is a Fermat prime.
The exact probability depends on the factorisation of $\phi(n)$, not something that can be predicted from $n$ and its factorisation.
When $n$ is a prime of the form $4k+3$, the probability is $\dfrac{2k}{4k+2} \to \dfrac12$ because there are infinitely many such primes.
A: For certain $n$, the probability of picking an element (other that the identity) of odd order, is 0. We know that the cardinality of $\mathbb{Z}_n^*$ is given by Euler's totient function $\tau$. It turns out that $\tau(34) = 16$ and so by Lagrange's Theorem, all elements in $\mathbb{Z}_{34}^*$ have even order. Similarly $\tau(96) = 32$ and again none of the elements in $\mathbb{Z}_{96}^*$ can have odd order.
In general it looks like it could be very difficult to provide explicit values or to give bounds for these probabilities.
