Euclidean Algorithms and Congruences
Structure of the Unit Group Modulo n
The structure of the multiplicative group of integers modulo n, its decomposition by CRT, and computing element orders.
Engineering / MathematicsEuclidean Algorithms and Congruences2 min readKV-MATH-0518
The multiplicative group of residues coprime to n is the setting for pseudoprime tests, discrete logarithms and much of finite field computation. Its structure is completely known, which makes it a rare case where theory answers the computational question directly.
Order of the group
Computing the totient requires the factorisation of n. This is a genuine obstacle: for an unfactored modulus the group order is not known, which is exactly the difficulty several cryptographic constructions rely upon.
Structure
By the Chinese remainder theorem the group decomposes as a product over the prime power factors.
| Modulus | Structure |
|---|---|
| p odd prime | Cyclic of order p - 1 |
| p^k, p odd | Cyclic of order p^(k-1)(p-1) |
| 2 | Trivial |
| 4 | Cyclic of order 2 |
| 2^k, k >= 3 | Product of a group of order 2 and a cyclic group of order 2^(k-2) |
The Carmichael function
The exponent of the group — the smallest positive integer annihilating every element — is the Carmichael function, generally smaller than the totient.
Computing element orders
Order of an element
- Factor the group orderRequires factoring phi(n), hence factoring n first.
- Start from the exponentTake the group exponent as the initial candidate.
- Divide out primesFor each prime dividing the candidate, test whether raising to the reduced power still gives the identity; if so, reduce.
- TerminateThe final candidate is the exact order.
For the analogous structure in a number field setting, see residue rings of the maximal order.
Source. Henri Cohen, A Course in Computational Algebraic Number Theory, Springer GTM 138 — 1.4.1. Structural reference unverified: the source file was not available during authoring; chapter and section numbers are taken from the published edition and have not been checked against a physical copy.