6
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 1
    $\begingroup$ Your question is kind of vague. Is there something specific you want to know about the order? $\endgroup$
    – Ryan Budney
    Commented Oct 28, 2010 at 23:32
  • $\begingroup$ I assume the question is about efficient algorithms for finding the order. $\endgroup$
    – Qiaochu Yuan
    Commented Oct 28, 2010 at 23:35
  • $\begingroup$ @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! $\endgroup$
    – Jeremy West
    Commented Oct 28, 2010 at 23:55
  • 1
    $\begingroup$ What do you by "is known where n is prime". Does there exist a polynomial time algorithm. To be honest, I would be surprised if thats the case. The reason for that is that I believe that it would enable us to find the prime factorisation of p-1 quickly. A heuristic for that is that, for some randomly chosen a we can compute its order, which is a factor of p-1. With a certain probability it should be a non-trivial factor. If we repeat this for sufficiently many numbers a we can get all non-trivial factors of p-1. ... $\endgroup$
    – wood
    Commented Oct 29, 2010 at 0:33
  • 1
    $\begingroup$ @Jeremy: What I had in mind was the following: you have a residue a mod n and a prime factorization of F=Phi(n). Obviously a^F=1 mod n. If p is a prime dividing F, compute a^(F/p) mod n. If you get 1 mod n, then the order of a mod n divides (F/p). Repeating this will eventually give you the proper power of p appearing in the multiplicative order of a mod n. So just do this for each of the primes dividing F. $\endgroup$
    – user1073
    Commented Oct 29, 2010 at 1:22

2 Answers 2

Reset to default
8
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ 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! $\endgroup$
    – Jeremy West
    Commented Oct 29, 2010 at 2:40
  • $\begingroup$ You might also look up primitive roots on wiki (how can I hyperlink in a comment?). To emphasize how little one can say (if I recall correctly), there is no a>1 for which it is even known that a is a primitive root mod p for infinitely many primes p! $\endgroup$
    – Kimball
    Commented Oct 29, 2010 at 4:55
  • $\begingroup$ Kimball, you can hyperlink in a comment by just cutting and pasting the URL, like en.wikipedia.org/wiki/Emil_Artin $\endgroup$
    – KConrad
    Commented Oct 29, 2010 at 6:15
  • 4
    $\begingroup$ A good place to start to learn about computational number theory (elementary and more advanced) is Henri Cohen's book "A Course in computational algebraic number theory", Spring GTM 138. Algorithm 1.4.3 in there is what is described in this answer. $\endgroup$
    – Chris Wuthrich
    Commented Oct 29, 2010 at 8:19
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – Jeremy West
    Commented Oct 29, 2010 at 1:18
  • 4
    $\begingroup$ @Jeremy West: The idea of "parallelism" in quantum computers is derived purely from an extra-scientific interpretation of quantum mechanics (the so-called "many worlds hypothesis"). What is less controvertial, and certainly true regardless of one's opinions on what quantum mechanics 'means', is that quantum computers would be very good at solving certain problems exhibiting periodic structures. "Order finding modulo n" is precisely one such problem, and is the heart of Shor's algorithm. $\endgroup$
    – Niel de Beaudrap
    Commented Oct 29, 2010 at 6:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .