What do you mean exactly by a "serious problem"? Also, is this question significantly different than your previous question? mathoverflow.net/questions/28695/…

This wasn't my question, but this answer was uncommonly informative. Thanks!

I realize I am very late to the party here, but I couldn't resist commenting that the high school student I am currently tutoring is required to do these types of proofs. In fact, when I explain to people that research mathematicians prove theorems, the most common response I get is "I hated doing proofs in geometry!" Upon examination, I always find that they did two-column proofs, and this is their only association with the term.

I only meant that they would numerically estimate it at x = 2 using the limit definition. It is easy to estimate using the definition, but if they try to differentiate and plug in 2 they will probably get the wrong answer.

Is this a necessary condition as well?

I feel a bit embarrassed since these are certainly facts that I should have remembered. They key I was missing was the order for prime powers. Thanks for the answer!

As far as I can tell (from the wiki article) Shor's algorithm relies on the parallelism inherent in quantum computing, rather than any particular insight about how the order of a might be related to a and n. Is this accurate?

@Ben: In what sense is it easy? I am not aware of any algorithm or method for doing this. If you are, please elaborate/post it as a answer!

@wood: Sorry, I misspoke. What I meant was merely that we know that (Z/nZ)^* is cyclic when n is prime, so we can use some of the structure of cyclic groups to at least give heuristics on what orders might be likely. It is certainly not true that we know the order of any given a, even when n is prime.

@Ryan: An algorithm would be fine. From what I can tell, all that is known is the case where n is prime and otherwise we are reduced to taking powers of a until we obtain 1 mod n. I am curious to know if there is a better algorithm or perhaps something that can be said, perhaps in terms of the prime factorization of a. Since I am not sure what such a statement would look like, I had a hard time being more precise. If you have suggestions for clarifying the question, I would greatly appreciate them!

Where are you assuming this polynomial lives to begin with? Real coefficients? Rational?

@Ryan: I think you have captured my intent better than I was able to express it myself.