# Are some RSA moduli more resistant than others to Shor's factorization algorithm?

Does there exist a semi-prime integer $$n$$ (e.g., an RSA modulus) such that the order of every element in the multiplicative group modulo $$n$$ is equal to the order of the full group modulo $$n$$? If so, would such an integer be more resistant to factorization by Shor’s factorization algorithm (the quantum version) than a semi-prime integer that does not have this property?

What I am thinking here is that if the number of qubits required to factor an RSA modulus is directly proportional to the order of a random element selected from the group (big assumption, but I know very little about how quantum computers work), then the number of qubits required to factor such an integer would be guaranteed to be large (i.e., it would have to equal the order of the full group), and perhaps this fact could be leveraged to at least delay the demise of RSA.

Does there exist a semi-prime integer $$n$$ (e.g., an RSA modulus) such that the order of every element in the multiplicative group modulo $$n$$ is equal to the order of the full group modulo $$n$$?

No, but we can come close; if we gave the product of two distinct safeprimes $$n = (2r+1)(2s+1)$$ (where $$r, s$$ are prime), then almost all the elements in $$\mathbb{Z}_n^*$$ are either of order $$rs$$ or of order $$2rs$$. The exceptions are the values that happen to be 1, -1 modulo $$2r+1$$ or $$2s+1$$ - if $$r, s$$ are large, such values are rare (and if you happen to stumble on one of those values (other than 1, n-1), you can factor anyways).

On the other hand:

What I am thinking here is that if the number of qubits required to factor an RSA modulus is directly proportional to the order of a random element selected from the group

This wouldn't help that much; if we consider the order of a random element of $$Z_n^*$$, the order will be $$n/d$$ for a relatively small $$d$$; exceptions will be comparatively rare (and someone who doesn't know the factorization won't be able to produce them without guessing).

Here's how it works: the order of a value $$g$$ modulo $$n$$ is the least common multiple of the order of $$g$$ modulo $$p$$ and the order of $$g$$ modulo $$q$$ - hence, we need to look at the behavior modulo those primes to understand how the order modulo $$n$$ works. Now, if $$r$$ is a divisor of $$p-1$$, then the probability that a random $$g$$ has an order which is a divisor of $$(p-1)/r$$ is $$1/r$$ - hence if $$r$$ is large, this happens only with small probability (and if $$r$$ is small, this doesn't reduce the order much).

Now, one case where the order might be smaller if the value of $$\gcd(p-1, q-1)$$ is large (because that is effectively a division of the least common multiple). However, with random $$p, q$$, this is usually small; it's not clear whether going to extra effort to make sure that it is minimal (2, which it is in the clear where $$p, q$$ are safeprimes) is worth the effort.

• Thanks @poncho. Just so that I understand, I think you are saying that the probability a prime number $p$ (of a size suitable as a factor in an RSA modulus) contains elements modulo $p$ that will generate small subgroups is very small. Or perhaps that the proportion of such elements relative to the size of $p$ is very small? In either case, ensuring $p$ (and $q$) are safe primes in order to maximize qubits is not worth the effort. Do I have that right? If not, please clarify. Commented Jun 21, 2023 at 15:59
• @divaconhamdip: will if $p-1$ has $r$ as a factor, then $1$ out of every $r$ members of $\mathbb{Z}_p^*$ is a member of the subgroup of size $(p-1)/r$. Hence, if we're looking for elements of small subgroups, that is, we have $(p-1)/r \lll p$, then such elements are rare (as $r$ is necessarily large). Hence, to answer your question, it is the "proportion of such elements relative to the size of $p$" that is small Commented Jun 22, 2023 at 2:18