Skip to main content
MathOverflow

Return to Question

retag
Link
Franz Lemmermeyer
Franz Lemmermeyer
  • 32.5k
  • 4
  • 109
  • 215
added 225 characters in body
Source Link
Jeremy West
Jeremy West
  • 317
  • 3
  • 11

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.

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?

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.

Source Link
Jeremy West
Jeremy West
  • 317
  • 3
  • 11

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?