Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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$.
Now you have to assemble everything again using either the product structures or disjoint unions.
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$).
