接前面一小节 扩展欧几里德算法的推导。
前面提到了扩展欧几里德算法的证明和推导,对于这些定理,我们主要关心的是它的应用,是吧。定理用不着,价值就很难体现。扩展欧几里得算法的用途非常广,比如RSA加密算法中求私钥d。
这里我们要用程序来感受扩展欧几里德算法。还是前面小节的问题:已知等式 47x + 30y = 1; 求x,y的整数解。
设扩展欧几里德算法为gcdEx(a,b,x,y) 其中a,b为已知,x,y为所求。那么gcdEx(a,b,x,y)函数就有如下的计算过程:
解释一下这个过程:
1. 左边是利用朴素欧几里德算法相除得到一系列中间值,gcdEx(47,30,x,y),a = 47,b = 30,所以 gcd(47, 30) = gcd(b, a%b) = gcd(30, 17),直到b=0。
2. 当b=0时,可以得知x=1,y=0,当知道这两个值的时候,就可以开始根据扩展欧几里德算法倒推了。还记得那个定理吗?这里再说一次:
x1 = y2 y1 = x2 - (int)(a/b) * y2
3. 往上一步的x,y看作x1,y1,下面“旧”的x,y看作x2,y2,利用朴素欧几里德算法推导出的结论,x1=y2,y1=x2-(a/b)*y2。其中a,b就是当前gcdEx中的a,b.当这样递归回去到了第一个调用点时,所得到的x,y就是结果,即x=-7,y=11;
理解了吧?下面我们用程序验证一下。网上一大把其它语言的实现,就是没PHP的,这里就PHP实现一下吧:
<?php $a = 47; $b = 30; $x; $y; $re = exgcd($a, $b, $x, $y); function exgcd($a, $b, &$x, &$y) { if($b == 0) { $x = 1; $y = 0; return $a; } echo 'exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />'; $r = exgcd($b, $a%$b, $x, $y); echo '--exgcd() paras $b ='.$b.', $a%$b = '.$a%$b.', $x = '.$x.', $y = '.$y.'<br />'; $t = $x; $x = $y; $y = $t - floor($a/$b)*$y; return $r; } echo '$x = '.$x; echo "<br />"; echo '$y = '.$y; echo "<br />"; ?>
程序运行结果:
exgcd() paras $b =30, $a%$b = 17, $x = , $y = exgcd() paras $b =17, $a%$b = 13, $x = , $y = exgcd() paras $b =13, $a%$b = 4, $x = , $y = exgcd() paras $b =4, $a%$b = 1, $x = , $y = exgcd() paras $b =1, $a%$b = 0, $x = , $y = --exgcd() paras $b =1, $a%$b = 0, $x = 1, $y = 0 --exgcd() paras $b =4, $a%$b = 1, $x = 0, $y = 1 --exgcd() paras $b =13, $a%$b = 4, $x = 1, $y = -3 --exgcd() paras $b =17, $a%$b = 13, $x = -3, $y = 4 --exgcd() paras $b =30, $a%$b = 17, $x = 4, $y = -7 $x = -7 $y = 11
扩展欧几里得算法就是不断地的将b放小,直至b等于0,最后反推求回x和y。前面不断的递归求解一定会有个时候 b=0,所以递归可以结束。结束之后再利用定理反推。
如果还不清楚,对着程序执行结果和图再仔细想想。
现代魔法 推荐于 2013-02-27 10:23