Let be a unit modulo and let be a positive integer. To prove that is its multiplicative order, it is necessary and sufficient to check
The first check makes the true order a divisor of . If , choose a prime divisor of ; then , contradicting the second check. Conversely, if , no smaller positive exponent can return to one.
For example, alone does not prove order six: the divisor gives and rejects it. The candidate three passes, since but . Once the prime factorization of is supplied, this certificate needs one modular exponentiation per distinct prime factor, plus the return check. The factorization itself is separate work. The candidate has no prime divisors and is accepted exactly when .

Articles by others on the same topic (0)

There are currently no matching articles.