What is the order of a in (Z/nZ)*? I was recently thinking about efficient algorithms for modular exponentiation. This led me to the (more interesting, in my opinion) question:

Let $1 < a < n$ be an integer relatively prime to $n$. What is the order of ${\overline{a}}$ in $\mathbb{Z}/n\mathbb{Z}^*$ (the multiplicative group of $\mathbb{Z}/n\mathbb{Z}$)?

I did some Google searching, but all I could find were the obvious facts that the order should divide the order of the group $\phi(n)$ and the exponent of the group $\lambda(n)$ (see Carmichael function). I asked several people if anything more could be said, but the answers were generally: "Some people study this. It is really hard." However, I couldn't find any other references.

Is this a question that has been seriously considered? If so, what is known and does anyone have any good references?

I am happy to suppose that we know a priori the prime factorization of both $a$ and $n$. Even given this information, is there something precise that can be said?
Because this is a (potentially) open problem, it is possible that it should be a community wiki page, I am not entirely certain what the policy is there. If so, someone please wiki-hammer this, as I have not the power! It might also be deserving of the open-problem tag?
Edit: I do in fact have the power to make community wiki posts (which I discovered by checking the faq) just not to edit someone else's. Still, I would prefer that this be a "real" question unless that is inappropriate.
 A: You seem to have been given some misinformation so I'll answer this question although I think it is elementary. You want to find the order of $a$ modulo $n$. The prime factorization of $a$ is largely irrelevant, the prime factorization of $n$ is crucial since otherwise you don't know the order of the group. Conversely, knowing the order of $a$ for many $a$'s will allow you to factor $n$. I'll assume you can factor $n$.
If $n$ is prime, then the group is cyclic, so any factor of $n-1$ is the order of some element. There isn't much more that can be said, you can't eyeball the order except in some obvious cases such as $a=\pm 1$. If you know a factorization of $n-1$, then you can run through the divisors of $n-1$ to find the order. If you don't know the factorization of $n-1$ then brute force is basically all you can do.
If $n$ is the power of a prime $p$, then if you can compute the order modulo $p$ (say $d$), it is easy to compute it modulo $n$ by finding the highest power of $p$ dividing $a^d-1$. This is an exercise which most number theory textbooks do when discussing primitive roots modulo prime powers.
In general, you get the order modulo $n$ by factoring $n$, and using the Chinese remainder theorem to reduce to the above cases.
A: Essentially Shor's algorithm (http://en.wikipedia.org/wiki/Shor's_algorithm) for factorizing integers uses the fact that for any given $n$ and any $0 < a < n$ we can compute the order of $a$ efficiently - at least on quantum computers. This means that even if we do not know anything about $n$ and $a$ there is an quantum algorithm in BQP.
However, I do not know if the prime factorization of $n$ or $a$ may help to give even an efficient algorithm on classical computers.
