In Mild Obfuscation, I proposed
as a “cryptographic” primitive. For , the only possible solutions for are and . But what are the solutions if ? Are there better than others?
Well, to see if is adequate, it suffices to test if , and will be satisfactory iff , that is, if and are relatively prime, if they have no common factors. Therefore, neither nor need to be prime for this to work properly; after all, we have shown that has solutions.
Testing using is efficient (and sufficient), as the GCD can be computed in (times the complexity of computing modulo), but it is much more efficient (and also sufficient) to test using directly, which is performed in (times the complexity of modulo). If we want to also have an additional key, say , the problem generalizes to (which is called the th root of unity mod , which can still be tested quite efficiently using the fast (integer) exponentiation method (in ), but let us focus on the case with .
So to find a suitable for a given , we only have to test whether . We can test sequentially (although there are (marginally) better methods to search for ), but the question is, how many solutions does a given affords?
The complete answer is rather involved, but somewhat counter-intuitive. For one thing, one might expect that having being a prime number yields the most solutions for , but that’s not the case. In fact, I first thought that since only had solutions , a prime number with rather small (so that the number of possible values that one can encode was still large compared to , in the original context of mild obfuscation) would yield more solutions.
However, it seems that the more factors has, the more solutions it has for .
For example, (a prime number somewhat close to ) only has ($1$ and ) for solutions. With , we have 1, 16, 86, 101, 154, 169, 239, and 254 as solutions (and has 8 divisors, namely 1, 3, 5, 15, 17, 51, 85, 255, essentially ). So already having 255 rather than 256 for increases the possible number of “keys”. In the vicinity of 256 (without exceeding it), 240 has 1, 31, 41, 49, 71, 79, 89, 119, 121, 151, 161, 169, 191, 199, 209, and 239 as solutions (16 of them!). 240 is indeed quite composite as , with a total of 20 divisors.
So having , with “very” composite, will give you more different solutions for , and as grows, it will offer you a better security—although not truly cryptographic, merely cumbersome to break for smallish $n$. If you combine finding some value for an exponent , that is, finding such that , for large and , you may be up to something…