Fast method for solving modular exponential function with semi-prime modulus Assume we have a semi-prime $N = pq.$ Assume $N$ is not divisible by $2$ or $5$. We want to solve the equation $$10^x \equiv 1 \mod N, \ \ \ x>0.$$ One solution is enough.
Is there any fast method for doing this without knowing $p$ and $q$?
A "trivial" solution would be $$x = N - (p-1)(q-1),$$ but this requires knowing $p$ and $q$.
One method would be to test every number up to $N - (p-1)(q-1)$ or maybe to start from $N-1$ and go down from there, it would require $p+q$ trials.
Is this as hard a problem as integer factorization?
 A: The problem of finding the smallest $x > 0$ for this is finding the multiplicative order of $10 \bmod N$, and no efficient algorithm is known.
An $x$ here can be used to obtain the factorization of a number that isn't a prime power, and this is in fact how the end of Shor's Algorithm works, assuming $x$ isn't odd and $10^{x/2}$ isn't $-1$, in which case you need to try a different coprime base than 10. Assuming you had such an $x$, you could do $10^{x/2}$, which would lead to a number $a \not\equiv \pm 1 \pmod N$ such that $a^2 \equiv 1 \pmod N$. Then $(a + 1)(a - 1) \equiv 0 \pmod N$, and we can find the factors via GCD($a + 1, N$) and GCD($a - 1,  N$).
For any $x > 0$, a multiple of the multiplicative order, we could just divide it by two until we get a number we can work with or can conclude that we need a different base (e.g. getting an odd number $x$ such that $10^x$ that still equals $1$ or that $10^x$ is equal to $-1$).
So, given the ability to solve this for 10 and other bases, you could factor, so at least that generalization isn't any easier.
A: If p and q are not known, there is no known efficient method to compute such an x. The order $ord_{10}(N)$ is difficult to calculate without factoring N. You are content with an arbitary multiple of the order, but this cannot be done efficiently either.
Maybe, your problem is slightly easier than factorization, but I think the difference is small. If your problem could be solved efficiently, it would at least be much easier
to factor numbers than it actually is.
