OrderDem

Order Calculation Algorithm

Calculate the multiplicative order of $a$ modulo $n$ step by step

Base element $a$:

Modulus $n$:

Number $c$ such that $b^c \equiv 1 \pmod{n}$ for every $b$ coprime to $a$:

Understanding Multiplicative Order

The multiplicative order of an element $a$ modulo $n$ is the smallest positive integer $k$ such that $a^k \equiv 1 \pmod{n}$. This algorithm efficiently computes this value:

1. 1First, we verify that $\gcd(a, n) = 1$ to ensure $a$ is invertible modulo $n$
2. 2We start with an upper bound (either provided or computed using Carmichael's function)
3. 3We factor this upper bound and systematically test if we can reduce it
4. 4For each prime factor $p$, we test if $a^{\mathrm{bound} / p} \equiv 1 \pmod{n}$. If so, we replace $\mathrm{bound}$ with $\mathrm{bound} / p$.
5. 5We repeat this process until no further reduction is possible