与指数和同余有关的数论问题

manthanein

给定正整数\(n\)和\(m\)，求\(x^{y}\equiv n \pmod{m} \)，\(0 \lt x \lt m\)的所有可能的正整数解。
例如取\(n=1\)，\(m=10\)，可能的解为：
\(x=1\)，\(y\)任取
\(x=3\)，\(y=4k\)
\(x=7\)，\(y=4k\)
\(x=9\)，\(y=2k\)

.·.·.

只能枚举
没有什么特别有效的方法

如果m是一个素数
对m的每一个原根x都存在mod m-1意义下唯一的y使得x^y=n
而求出这样的y是一个困难的问题（离散对数问题，据传比RSA难）

所以可能只能枚举了