# Permutations coming from RSA

The RSA algorithm can be used to generate a permutation.

Given two prime numbers $p$ and $q$, the key length is $n=pq$.

If $a$ is the private key, then $b$ is the public key, where $ab \equiv 1 \pmod {\phi(n)}$.

We define a permutation $\pi : \mathbb Z/n\mathbb Z \to \mathbb Z/n\mathbb Z$, given by $\pi(k) = k^b \pmod n$.

Is anything known about these permutations from a group-theoretic point of view?

• The usual terminology is that the key length is the number of bits in $n=pq$, rather than $n=pq$. Usually it is assumed $p\ne q$, ensuring that $\pi$ indeed is a permutation. Assuming that, $a$ is a private key matching public key $b$ if and only if $ab\equiv 1\pmod{\operatorname{LCM}(p-1,q-1)}$; but $ab\equiv 1\pmod{\phi(n)}$ may not hold.
– fgrieu
Sep 20, 2016 at 17:26

If you write $\mathbb Z/n\mathbb Z$ first as $\mathbb Z/p\mathbb Z\times \mathbb Z/q\mathbb Z = \mathbb F_p\times\mathbb F_q$, and then $\mathbb F_p$ as $\mathbb F_p^\times\cup\{0\}$ (and the same for $\mathbb F_q$), then you see (using the discrete logarithm) that taking the $b$-th power in $\mathbb F_p^\times$ corresponds to multiplying by $b$ in the cyclic group $\mathbb Z/(p-1)\mathbb Z$, where $b$ is coprime to $p-1$ by assumption.
If $p-1 = \prod_i p_i^{e_i}$ is the prime power factorization of $p-1$, then you get $\mathbb Z/(p-1)\mathbb Z = \prod_i \mathbb Z/p_i^{e_i}\mathbb Z$ and you have to investigate what multiplication by $b$ (coprime to $p_i$) does to $\mathbb Z/p_i^{e_i}\mathbb Z$.
Writing $\mathbb Z/p_i^{e_i}\mathbb Z = \cup_{j=0}^{e_i} p^{e_i-j}(\mathbb Z/p_i^j\mathbb Z)^\times$ you'll see that you have to determine only the order $o$ of (multiplying by) $b$ in $(\mathbb Z/p_i^{e_i}\mathbb Z)^\times$ (as it gives the order of $b$ in $(\mathbb Z/p_i^j\mathbb Z)^\times$ for all $j\le e_i$ --- slight caution is necessary for $p_i=2$ as only for odd $p_i$ one has $(\mathbb Z/p_i^j\mathbb Z)^\times = (\mathbb Z/p_i\mathbb Z)^\times\times \mathbb Z/p_i^{j-1} \mathbb Z$, whereas $(\mathbb Z/2^j\mathbb Z)^\times = (\mathbb Z/2\mathbb Z)\times \mathbb Z/2^{j-2} \mathbb Z$ for $j>1$). Multiplying with an element of order $o$ in a group of order $g$ gives $\frac{g}{o}$ cycles of length $o$.
If you were just interested in the order of the permutation, take just the least common multiple of all group orders at the level of $(\mathbb Z/p_i\mathbb Z)^\times$ and $\mathbb Z/p_i^{e_i-1} \mathbb Z$ (don't forget to do the same for $q$ and beware of $p_i=2$).