模幂的反函数

Mgccl

$x^k \equiv b (mod n)$
知道k,b,n怎么才能快速的找到一个x, 如何快速找到最小的x?
当然不是反函数啦,无穷多的解...但想不到更好的称呼...

有点像是算法题,但是想看看有没有可以手算的方式...

mathe

离散对数问题,这个应该同因子分解问题(对n进行因子分解)等价

gxqcn

好像 ECC 加密的安全性就是建立在离散对数计算的困难度上。

medie2005

呵呵，这个目前是不可能有高效算法的，如果有的话，大数分解就解决了。
如果我们知道如何高效求满足$a^x=1 mod N$的最小的x话，那么，对一个大整数N，我们可以先求得满足$a^x=1 mod N$的最小解x0，然后，分解x0，对x0的各个因数f0,f1,f2,f3,...，依次计算$gcd(a^f0-1,N)$,$gcd(a^f1-1, N)$,$gcd(a^f2-1,N)$,...，只要结果非1和N，就得到了N的一个因数。容易证明的是，若N非素，则上面的方法必然可以分解N。
当然，对x0还是比较难分解的情况，我们可以利用上面的算法来分解x0，这样，经过步步规约，总可以得到一个比较好分解的数，我们分解这个数，然后回代回去，就可以分解x0了。

gxqcn

楼主要求的是底数，非指数。

medie2005

呵呵，看错。

medie2005

那就不是离散对数问题了。

无心人

难度很大
除非很熟悉有限域算法
呵呵
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
PS:
发现淘宝好多SUN工作站，特便宜
不知道功耗大么？
买一个玩编程效果一定不错

无心人

我想，这个在我连续发的数论变换帖子里
似乎有专门的讨论这个的
呵呵
似乎是要知道n的分解的

mathe

的确不是离散对数问题，不过知道n的因子分解就很简单计算了。