ax+by=c求解

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

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

$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"[a, b]$，
则 $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很大（上万位）的时候，问题可以瞬间解决（因为辗转相除的速度是很快的[log(n)]）。
但是貌似分解大整数还是很困难的……

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

能给我描述下么？

账号		自动登录	找回密码
密码			欢迎注册

[讨论] ax+by=c求解

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。