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求解

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