Encoding of multiplicative group of integers modulo n

Definition

This article defines the standard (typical) method of encoding the multiplicative group of integers modulo n for $n>1$.

The encoding is as follows. We assume that there is an encoding available for the positive integers, say, using a suitable base notation (such as binary notation). To encode an element of the multiplicative group of integers modulo n, simply use the encoding for the unique positive integer among $1,2,3,\dots ,n-1$ that corresponds to that congruence class.

Note that the order of the group is the Euler totient function $\varphi (n)$ which is $\Omega (n/\log n)$ and $O(n)$. In particular, this means that $O(\log \varphi (n))=O(\log n)$ and polynomials in $n$ also grow polynomially in $\varphi (n)$. It's easier to give estimates based on $n$, which is what we do below.

The algorithms are as follows:

Shorthand for algorithm	Input	Output	How it works	Time taken
identity element	--	the codeword for the identity element	the identity element code-word is always the encoding of the positive integer 1.	$O(1)$
group multiplication	codewords for elements $g,h\in G$ (possibly equal, possibly distinct elements)	codeword for $gh$	we multiply the code-words as positive integers, using the standard algorithm for multiplication of integers. We then perform Euclidean division of the answer by $n$ and compute the remainder. The remainder is the desired answer.	$O((\log n)^{3})$ (we can probably do better by some smart work)
inverse map	codeword for $g\in G$	codeword for $g^{-1}$	Suppose $a$ is the positive integer representing $g$. Solve the linear Diophantine equation $ax+ny=1$ using the Euclidean algorithm method. Reduce the solution $x$ obtained modulo $n$.	$O((\log n)^{3})$ (we can probably do better by some smart work)
membership testing	any word	yes/no depending on whether it is a codeword for an element of the group.	First, check if the code-word is for a positive integer between 1 and $n-1$. Use the Euclidean algorithm to determine the gcd with $n$ and output yes if the gcd is 1, no otherwise.	$O((\log n)^{3})$ (we can probably do better by some smart work)

Other common algorithms

Shorthand for algorithm	Input	Output	How to achieve it
list all group elements (also called an enumeration algorithm)	--	list of all the elements of the group	We could run through all the numbers from 1 to $n-1$ and do a membership test on each. Since $\varphi (n)=\Omega (n/\log n)$, this is not too wasteful. Alternatively, we could factor $n$ and then use a sieve to remove all multiples of all prime factors of $n$ and enumerate the remaining elements.
order of the whole group	--	a number that equals the order of the group	factorize the order, then use the formula for the Euler totient function
uniform random sampling from the whole group		outputs an element picked uniformly at random from the group	PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE] One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.
algorithm for the power computation problem: computing a given power of a given element	element of the group, integer	outputs codeword for the power of that element	repeated squaring algorithm for power computation problem -- the black-box method
algorithm for the element order-finding problem: computing the order of an element	element of the group	order of that element as a nonnegative integer	brute-force black-box group algorithm for element order-finding problem, square root-based black-box group algorithm for element order-finding problem