medie2005 发表于 2008-5-20 09:46:50

ax+by=c求解

ax+by=c，$a,b,c$为已知量，且$a,b,c$两两互素。如何求(x,y)？

gxqcn 发表于 2008-5-20 10:12:22

可以通过辗转相除法得到通解。
应该有些结论，可惜我身边没有参考书。

其实，a,b,c 不必两两互素，只要 gcd(a,b) | c 即可。
可先求出 {g, {x_0, y_0}} = "ExtendedGCD"，
则 x = (c/g)x_0,\quad y = (c/g)y_0

上述函数 ExtendedGCD 是 Mathematica 中的，HugeCalc 对应的函数名为“GcdEx”。

zgg___ 发表于 2008-5-20 10:14:51

因为a和b互质，所以存在x和y使得ax+by=1，其中x和y可以这样求，将a和b辗转相除得到1，然后返回去，得到x和y。貌似叫做联带辗转相除。这样数对(cx,cy)就是要求的。
也可以用中国剩余定理。对于变量更多的情况也适用。

medie2005 发表于 2008-5-20 10:40:01

呵呵,我发贴后想了想,已经知道答案了.
谢谢楼上两位.

medie2005 发表于 2008-5-20 10:43:21

另外,我好象发现了一个分解因子的算法.
不过,目前还没太想清楚.
如果算法是对的话,有希望分解掉RSA-1024.

zgg___ 发表于 2008-5-20 11:00:02

呵呵，那就祝好运了。
可以认为当abc很大（上万位）的时候，问题可以瞬间解决（因为辗转相除的速度是很快的）。
但是貌似分解大整数还是很困难的……

medie2005 发表于 2008-5-20 11:02:33

呵呵,当然不是只用这个了.

无心人 发表于 2008-5-20 17:08:12

那你如果利用这个式子
我觉得你还是不要继续了

连尝试的必要都没有

medie2005 发表于 2008-5-20 18:05:36

呵呵，现在已经发现了算法中一个很难实现的步骤．如果这个步骤可以高效实现，还是有希望分解掉RSA-1024的，但是，现在还没发现比较高效的方法．
呵呵，可能没什么希望了．

无心人 发表于 2008-5-20 20:47:11

:)

能给我描述下么？
页: [1]
查看完整版本: ax+by=c求解