## (more) Mild Obfuscation

In Mild Obfuscation, I proposed

$a^2 \equiv 1 ~(\mathrm{mod}~n)$

as a “cryptographic” primitive. For $n=2^k$, the only possible solutions for $a$ are $\pm{}1$ and $2^{k-1}\pm{1}$. But what are the solutions if $n \not\sim 2^k$? Are there better $n$ than others?

Well, to see if $a$ is adequate, it suffices to test if $a^2 \equiv 1 ~(\mathrm{mod}~n)$, and $a$ will be satisfactory iff $\gcd(a,n)=1$, that is, if $a$ and $n$ are relatively prime, if they have no common factors. Therefore, neither $a$ nor $n$ need to be prime for this to work properly; after all, we have shown that $n\sim{}2^k$ has solutions.

Testing using $\gcd(a,n)=1$ is efficient (and sufficient), as the GCD can be computed in $O(\lg\min(a,n))$ (times the complexity of computing modulo), but it is much more efficient (and also sufficient) to test using $a^2 \equiv 1~(\mathrm{mod}~n)$ directly, which is performed in $O(1)$ (times the complexity of modulo). If we want to also have an additional key, say $r$, the problem generalizes to $a^r \equiv 1~(\mathrm{mod}~n)$ (which is called the $r$th root of unity mod $n$, which can still be tested quite efficiently using the fast (integer) exponentiation method (in $O(\lg r)$), but let us focus on the case with $a^2$.

So to find a $a$ suitable for a given $n$, we only have to test whether $a^2 \equiv 1 ~(\mathrm{mod}~n)$. We can test $a=1,2,\ldots,n-1$ sequentially (although there are (marginally) better methods to search for $a$), but the question is, how many solutions does a given $n$ affords?

The complete answer is rather involved, but somewhat counter-intuitive. For one thing, one might expect that having $n$ being a prime number yields the most solutions for $a$, but that’s not the case. In fact, I first thought that since $n\sim{}2^k$ only had solutions $2^{k-1}\pm{1}$, a prime number $n^\prime=2^k-c$ with $c$ rather small (so that the number of possible values that one can encode was still large compared to $2^k$, in the original context of mild obfuscation) would yield more solutions.

However, it seems that the more factors $n$ has, the more solutions it has for $a$.

For example, $n=241$ (a prime number somewhat close to $2^8$) only has $\pm{}1$ ($1$ and $240\equiv{}-1~(\mathrm{mod}~241)$) for solutions. With $n=255$, we have 1, 16, 86, 101, 154, 169, 239, and 254 as solutions (and $n=255$ has 8 divisors, namely 1, 3, 5, 15, 17, 51, 85, 255, essentially $255=3\times{}5\times{}17$). So already having 255 rather than 256 for $n$ 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 $240=2^4\times{}3\times{}5$, with a total of 20 divisors.

*
* *

So having $n\not\sim{}2^k$, with $n$ “very” composite, will give you more different solutions for $a$, and as $n$ 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 $a$ for an exponent $r$, that is, finding $a$ such that $a^r \equiv 1~(\mathrm{mod}~n)$, for large $a$ and $r$, you may be up to something…