3
$\begingroup$

Possible Duplicate:
Quick algorithm for computing orders mod n?

Let $l$ be an odd prime number. Let $p$ be a prime number such that $p \neq l$. I'd like to compute efficiently the order of $p$ mod $l$ using a calculator. For example, how can I compute efficiently the order of 2 mod 53? Thanks in advance.

My motivation came from this.

  • 0
    The order in what group exactly ?2012-07-23
  • 0
    The multiplicative group of integers mod $l$. Namely $(\mathbb{Z}/l\mathbb{Z})^*$. The order of an integer mod $l$ is standard in elementary number theory.2012-07-23
  • 0
    It is cheap in general whether $p$ is a quadratic residue of $\ell$. In this case $2$ is a NR of $53$. The order divides $52$. The only interesting possibilities are $13$, $26$, $52$. It cannot be $13$, else $2$ would be a QR. So calculate $2^{26}\pmod{53}$, or maybe $2^{27}$.2012-07-24

1 Answers 1