欢迎来到天天文库
浏览记录
ID：59781042
大小：244.00 KB
页数：41页
时间：2020-11-24
《最大公因数、辗转相除法、整除性质-、最小公倍数ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、最大公因数与辗转相除法 整除的性质与最小公倍数复习带余数除法的内涵它可以看作是整除的推广，也可以用带余除法定理来定义整除性将一个未知的整数表示为小于除数的余数，将整数进行分类，从而可将无限问题转化为有限问题其他应用：辗转相除法、进制间转换算法§2最大公因数与辗转相除法辗转相除法的应用求出两个正整数的最大公因数推出最大公因数的重要性质解一次不定方程的基本工具辗转相除法在密码学中的应用RSA算法的重要部分还被用来解丢番图方程，寻找满足中国剩余定理得数，或者求有限域的倒数。还可以用来构造连分数，在一些整数分解算法中也有
2、应用。同时在处理大数时非常高效，它需要的步骤不会超过较小数的位数（十进制下）的五倍。辗转相除法求最大公约数问题步骤：时间复杂性：O(logn)§3整除的进一步性质及最小公倍数作业21、辗转相除法求以下数组的最大公因数，并把它表为这些数的整系数线性组合（i）2947,3997；（ii）-1109,49992、设p是素数，(a,p2)=p,(b,p3)=p2,求(ab,p4),(a+b,p4)3、P91，P141,2
此文档下载收益归作者所有
