Multiplicative Order Calculator
Calculate ordn(a) - the smallest positive integer k such that ak ≡ 1 (mod n).
Enter a modulus n >= 2 (max 1,000,000)
The multiplicative order of a modulo n, denoted ordn(a), is the smallest positive integer k such that ak ≡ 1 (mod n). This concept is fundamental in number theory and has important applications in cryptography.
Definition: For integers a and n with gcd(a, n) = 1:
ordn(a) = min { k ∈ Z+ : ak ≡ 1 (mod n) }
Key Properties:
- The multiplicative order only exists when gcd(a, n) = 1 (a and n are coprime)
- ordn(a) always divides φ(n) (Euler's totient function)
- ordn(a) always divides λ(n) (Carmichael function)
- am ≡ 1 (mod n) if and only if ordn(a) divides m
- If ordn(a) = φ(n), then a is a primitive root modulo n
Algorithm: The calculator finds the multiplicative order by computing successive powers of a modulo n until reaching 1. At each step, it reduces the intermediate result modulo n to keep numbers small and avoid overflow.
Applications: Multiplicative order is essential in:
- RSA cryptography - understanding the structure of (Z/nZ)*
- Diffie-Hellman key exchange - selecting secure generators
- Primality testing - Fermat and Miller-Rabin tests
- Pseudorandom number generators - analyzing period lengths
Common multiplicative orders for small values:
Note: When the order equals φ(n), the element is a primitive root. For prime p, φ(p) = p - 1, so primitive roots mod 7 have order 6, and primitive roots mod 13 have order 12.
What is the multiplicative order?
The multiplicative order of a modulo n, written as ord_n(a), is the smallest positive integer k such that a^k ≡ 1 (mod n). It only exists when a and n are coprime (gcd(a, n) = 1). The multiplicative order tells you how many times you need to multiply a by itself before getting back to 1 in modular arithmetic.
How is multiplicative order related to primitive roots?
A primitive root modulo n is an integer g whose multiplicative order equals Euler's totient φ(n). In other words, g is a primitive root if ord_n(g) = φ(n). Primitive roots generate all elements coprime to n through their powers, making them fundamental in cryptography.
Why is multiplicative order important in cryptography?
The multiplicative order is crucial in cryptographic protocols like RSA and Diffie-Hellman. In Diffie-Hellman key exchange, the security relies on choosing a generator with a large multiplicative order. Understanding multiplicative orders helps in analyzing the security and efficiency of these cryptographic systems.
What is the relationship between multiplicative order and the Carmichael function?
The Carmichael function λ(n) gives the maximum possible multiplicative order for any element coprime to n. For any a coprime to n, ord_n(a) always divides λ(n). When ord_n(a) = λ(n), the element a is called a primitive λ-root. The Carmichael function is the exponent of the multiplicative group (Z/nZ)*.