most recent 30 from http://mathoverflow.net 2013-06-19T10:44:14Z http://mathoverflow.net/feeds/question/44033 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/44033/what-is-the-order-of-a-in-z-nz Jeremy West 2010-10-28T23:13:45Z 2010-10-29T07:44:24Z

<p>I was recently thinking about efficient algorithms for modular exponentiation. This led me to the (more interesting, in my opinion) question:</p> <blockquote> <p>Let $1 &lt; a &lt; 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}$)?</p> </blockquote> <p>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 <a href="http://en.wikipedia.org/wiki/Carmichael_function" rel="nofollow">Carmichael function</a>). 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.</p> <blockquote> <p>Is this a question that has been seriously considered? If so, what is known and does anyone have any good references?</p> </blockquote> <p>I am happy to suppose that we know <em>a priori</em> the prime factorization of both $a$ and $n$. Even given this information, is there something precise that can be said?</p> <p>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?</p> <p><strong>Edit</strong>: 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.</p>

http://mathoverflow.net/questions/44033/what-is-the-order-of-a-in-z-nz/44035#44035 wood 2010-10-29T00:03:52Z 2010-10-29T00:03:52Z

<p>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 &lt; a &lt; 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.</p> <p>However, I do not know if the prime factorization of $n$ or $a$ may help to give even an efficient algorithm on classical computers.</p>

http://mathoverflow.net/questions/44033/what-is-the-order-of-a-in-z-nz/44046#44046 Felipe Voloch 2010-10-29T02:17:42Z 2010-10-29T02:17:42Z

<p>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$.</p> <p>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.</p> <p>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.</p> <p>In general, you get the order modulo $n$ by factoring $n$, and using the Chinese remainder theorem to reduce to the above cases.</p>