# Tag Info

Indeed, theoretically $$X'\equiv C^{a^{-1}}\equiv A^{x*a^{-1}}\equiv g^{x}=X\pmod p$$ should hold, given $gcd(a,p-1)=1$. However there are two reasons why you won't get this equation to hold. You calculated $a^{-1}$ using the wrong modulus. As it is in the exponent you need to calculate $a^{-1}\bmod q$ with $q$ being the group's order instead of ...
No, we do not know an algorithm running in linear time (or even polynomial time, relative to the number of digits in $n$) that outputs 'true' if $n$ is the product of exactly two prime numbers, and 'false' otherwise. If such an algorithm existed, I do not see that it would imply possibility to factor $n$, or otherwise break RSA. For sure, it would not be a ...