数学好的，正经学习过数论的同志们，进来看看这个有关问题

数学好的，正经学习过数论的同志们，进来看看这个问题
现有一公式：X^a mod b = c.给出a,b,c，求出所有满足条件的X。
输入包括多组数据，每组数据三个正整数1<=a,b,c<=10^7。
每组数据输出若干行，每一行代表了满足方程的一个X的解，解的顺序按照从小到大输出,最后输出一个空行。
没有解输出“No Solution!”

c#区的原帖：
http://topic.csdn.net/u/20110602/10/18edd5c3-fb85-4e78-964e-824e2a787622.html

fancymouse在么？
mathe在么？

[解决办法]
baby-step giant-step
用hash可以O(sqrt(n))，用排序+merge可以O(sqrt(n)*log(n))
[解决办法]
b是否素数关系不大，我们总可以先将b因子分解后再考虑。另外假设c不是b的倍数（不然显然）
如果b是素数，我们可以设d=gcd(a,b-1),根据中国剩余定理，存在e使得
a*e=d(mod b-1),于是我们得到
X^d(mod b)=c^e(mod b)
于是变换成方程
X^d (mod b)=h,其中d|b-1
这时，我们需要判断方程是否有解
设q=(b-1)/d，于是我们得到
1=X^(d*q)(mod b)=h^q(mod b)
所以如果h^q(mod b)不是1，无解。
如果h^q(mod b)=1,
那么我们可以任意选择b的原跟g
如果x0是一个解，那么x0*g^(kq)必然是所有解，所以只要求一个特解即可。
不过特解我想不出什么特别好的方法，在d比较大时，由于解比较多，可能采用随机算法比较有效。
[解决办法]

探讨

b是否素数关系不大，我们总可以先将b因子分解后再考虑。另外假设c不是b的倍数（不然显然）
如果b是素数，我们可以设d=gcd(a,b-1),根据中国剩余定理，存在e使得
a*e=d(mod b-1),于是我们得到
X^d(mod b)=c^e(mod b)
于是变换成方程
X^d (mod b)=h,其中d|b-1
这时，我们需要判断方程是否有解
设q=(b-1)/d，于是我们得到……

[解决办法]
22楼中的
64*a mod 37 = 26
估计是打错了，应该是
64*a mod 37 = 25

看了一下shanks算法，和bsgs原理一样。
shanks除去那个sqrt(q)，平凡的实现算法复杂度还要加上q^0.5 * log(q^0.5)[排序] + q^0.5[找到相同数对]，也就是sqrt(q) * log(q)[忽略解同余方程复杂度]。如前面的楼说过的，也可以用hash降低到sqrt(q).

m有原根，(n, m) = 1，则二项同余式x^k = n (mod m)有解的充要条件是：d = (k, phi(m)) | ind_g n，如果有解，则恰好有d个解。
[解决办法]
用Mathematics求解：
输入： Reduce[x^4 == 11 y + 3, {x, y}, Integers]

输出： C[1] \[Element]
Integers && (x == 4 + 11 C[1] || x == 7 + 11 C[1]) &&
 y == 1/11 (-3 + x^4)

Mathematics求解很快。
看到结果后，相信大家知道怎么编程解决这类问题。

这个问题其实是求（x mod b)^a mod b 是否等于c,那么从0开始到b-1循环检测这个等式，
如果成立，设x mod b = d,e是任意整数，则下面的解都是我们要的结果:
x=be+d
[解决办法]
这个问题其实是求（x mod b)^a mod b 是否等于c, 循环一下就可以求成全部解，解法如下：
for i = 0 to b - 1 do
if i^a mod b = c then
x = b * d + i (d是任意整数)是其中一组解

[解决办法]
不用数论，给个简单的办法
不断生成两个数x, y

x = 1^a, 2^a, 3^a, 4^a ...
y = 1*b+c, 2*b+c, 3*b+c ...

x,y互相追赶，x<y时x按规律递增，y<x时y按规律递增，x==y时就是解
[解决办法]

探讨

static int Bsgs(int pRoot, int prime, int mod)

[解决办法]
各位强大啊,这是传说中的指数对数问题,ECC加密算法就是计算指数对数的复杂性决定了ECC加密强度非常高,就目前来看,世界上还没有指数对数的计算方法,似乎只能从前到后一个一个的找了,所以从数学上求解密算法目前几乎是扯淡,如果你解出来了,哪绝对是世界上一流的数学家了.
[解决办法]
说错了,是离散对数问题

查看更多 下一篇