$x^y=z(mod\ n) 的所有相关问题的解法$

以下$x$为未知数。所有数都是整数

$a^x=b(mod\ n)$

• 这是离散对数问题，是一个难的问题——Diffie-Hellman算法就依赖于该问题的难解性。

当$gcd(a, n)=n$时

• 如果$b=1$，则$x=0$，如果$b=0$，则x为任意正数

当$gcd(a,n)=1$时

• 使用baby-step giant-step算法，具体可以参考求解a^x=b(mod m)

$x^a=b(mod\ n)$

• 这也是一个难的问题，目前并没有高效的通解，RSA算法就依赖于$n=pq$（p、q为质数）时x的难解性

$n$为质数时

• 根据费尔马小定理有$x^{n-1}=1(mod\ n)$
• 求解a在模$n-1$下的乘法逆元$b$，$x^{ab}=x^{1+k(n-1)}=x(mod\ n)$

$n$为合数时

• 目前是没有通用的高效解的——不仅仅在$n=pq$（p、q为质数）时没有，而是$n$为任意合数时都没有
• 可以构造如下规约，使得如果$n$为多个（大于2个）质数的积时有高效解，那么RSA就被攻破。假设$y^e=c(mod\ pq)$，即$y^e+kpq=c$，然后假设有一个算法，对于$n=rst$（r、s、t为任意质数）时有高效算法$T$，那么，我们两边乘以$t^e$得到 $y^e\times t^e +kpqt^e=(yt)^e+kpqt^e=ct^e$，模上$pqt$，得到$(yt)^e=ct^e(mod\ pqt)$，让算法$T$求解出$yt$，从而，我们得到了$y=yt\times t^{-1}(mod\ pqt)$

$a^b=x(mod\ n)$

• 快速模幂，算法如下

  def fastModulePow(x, y, n):
      """
      :return: x**y mod n
      """
      if y == 0:
          return 1 % n
      ans, x = 1 % n, x % n
      while y != 0:
          if (y & 1) == 1:
              ans = x * ans % n
          x, y = x * x % n, y // 2
      return ans