Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1495905
  • 博文数量: 164
  • 博客积分: 2993
  • 博客等级: 少校
  • 技术积分: 1718
  • 用 户 组: 普通用户
  • 注册时间: 2011-06-24 11:42
文章分类

全部博文(164)

文章存档

2014年(1)

2013年(36)

2012年(90)

2011年(37)

分类: 网络与安全

2013-09-11 16:52:38

欧几里德算法

欧几里德算法又称辗转相除法,用于计算两个整数a,b的最大公约数。gcd函数就是用来求(a,b)的最大公约数的。

 

gcd函数的基本性质:

性质一:gcd(a,b)=gcd(b,a)=gcd(-a,b)=gcd(|a|,|b|)

证明略。

 

性质二:gcd(a,b)=gcd(b,a mod b)

证明:a可以表示成a = kb + r,则r = a mod b

假设d是a,b的一个公约数,则有 d|a, d|b,而r = a - kb,因此d|r ,d是(b,a mod b)的公约数

假设d 是(b,a mod b)的公约数,则 d|b , d|r ,又a = kb +r ,因此d也是(a,b)的公约数

因此(a,b)和(b,a mod b)的公约数是一样的,其最大公约数也必然相等,得证。

 

//求GCD的递归方法

  1. def gcb(a, b):
  2.     if b==0:
  3.         return a
  4.     else:
  5.         return gcb(b, a%b)

  6. print gcb(12, 18)


//时间复杂度O(lgn)

 

扩展欧几里德算法
定理一:对于不完全为 0 的非负整数 a,b,gcd(a,b)表示 a,b 的最大公约数,必然存在整 数对 x,y ,

使得gcd(a,b)=ax+by。

解:设a、b不全为0,令a>b,

当b=0时,gcd(a,b)=a,解的情况为x=1,y=0

当ab!=0,令

a*x1+b*y1 = gcd(a,b)
b*x2+(a%b)*y2 = gcd(b,a-a/b*b)
又gcd(a,b) = gcd(b,a-a/b*b)
故有a*x1+b*y1 = b*x2+(a%b)*y2
a*x1+b*y1 = b*x2+(a-a/b*b)*y2
= b*x2+a*y2-a/b*by2
= a*y2+b*(x2-a/b*y2)
即有,x1=y2,  y1=x2-a/b*y2
由上推导可知,x1与y1的值可由x2、y2推知,拓展欧几里得算法就是不断地的将b放小,直至b等于0,最后反推求回x和y。

 

//算法,解方程ax+by=gcd(a,b),其中d=gcd(a,b)

求5mod7的逆元和最大公约数

  1. def egcd(a, b):
  2.     if b == 0:
  3.         return a, 1, 0
  4.     else:
  5.         g, x, y = egcd(b, a % b)
  6.         return g, y, x - a / b * y
  7.         
  8. print egcd(5, 7 )
阅读(3211) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~