Multiplicative order calculator

How it works

For $a$ coprime to $n$, the powers $a, a^2, a^3, \dots$ modulo $n$ must eventually come back to 1. The smallest $k \ge 1$ with $a^k \equiv 1 \pmod n$ is the order $\operatorname{ord}_n(a)$, the size of the subgroup that $a$ generates. If $\gcd(a, n) > 1$ no power is ever 1.

By Lagrange’s theorem the order divides the group size $\varphi(n)$, and in fact the group exponent $\lambda(n)$ (the Carmichael function). So instead of trying every $k$ one only tests divisors of $\lambda(n)$: either all of them in increasing order, or starting from $\lambda(n)$ and dividing out each prime factor $q$ as long as $a^{t/q} \equiv 1$ stays true. Both need the factorization of $\lambda(n)$.

Orders matter throughout cryptography: Diffie-Hellman and DSA use an element of large prime order $q$, and the order of $10$ modulo a prime $p \ne 2, 5$ is the length of the repeating block in the decimal expansion of $1/p$.