算法案例(辗转相除法和更相减损术).ppt

该【算法案例(辗转相除法和更相减损术) 】是由【wyj15108451】上传分享，文档一共【23】页，该文档可以免费在线阅读，需要了解更多关于【算法案例(辗转相除法和更相减损术) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。算法案例-辗转相除法和更相减损术目录CONTENTS辗转相除法更相减损术比较与讨论案例分析01辗转相除法定义与原理辗转相除法,也称为欧几里得算法,是一种求两个正整数最大公约数(GCD)的经典算法。原理基于这样一个事实:对于任意两个正整数a和b(b不为0),存在整数q和r,使得a=bq+r。当r=0时,b就是a和b的最大公约数。。,取余数。,直到余数为0。此时,除数就是两个数的最大公约数。应用场景01在计算机编程中,辗转相除法被广泛应用于计算两个整数的最大公约数。02在密码学中,辗转相除法用于实现模逆运算,是RSA等公钥密码体系的重要基础。在数学领域,辗转相除法用于证明一些与最大公约数相关的定理和性质。0302更相减损术定义更相减损术是一种求两个整数的最大公约数的方法,通过不断减去较大的数,再对剩余的数重复这个过程,直到剩余数为0,此时减去的次数就是最大公约数。原理更相减损术基于一个简单的事实,即两个整数的最大公约数等于其中较小的数和两数之差的最大公约数。定义与原理算法实现输入:两个正整数a和b(a>b)。,则将a减去b,记差值为c。输出:a和b的最大公约数。,则它们的最大公约数是a或b。,计算b和c的最大公约数。应用场景求最大公约数是更相减损术最直接的应用场景。在数学、计算机科学和其他领域中,经常需要求取两个数的最大公约数。在计算机编程中,更相减损术可以用于实现整数的除法操作,因为求最大公约数的过程实际上就是不断做除法的过程。在密码学中,更相减损术可以用于实现模逆运算,用于RSA等公钥密码算法中。