Jan 29
在欧几里德算法的简单描述以及C++与Java的各自实现代码中介绍的欧几里德算法是计算两个数最大公约数的传统算法，无论从理论还是从实际效率上都是很好的。但是却有一个致命的缺陷，这个缺陷在素数比较小的时候一般是感觉不到的，只有在大素数时才会显现出来。
一般实际应用中的整数很少会超过64位（当然现在已经允许128位了），对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过 64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算 128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。
Continue reading »
written by Minidxer
| tags: C++, Java, Stein, 最大公约数, 欧几里德, 算法, 试商法
Jan 29
欧几里德算法描述：
欧几里德算法又称辗转相除法，用于计算两个整数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)的公约数是一样的，其最大公约数也必然相等，得证
Continue reading »
written by Minidxer
| tags: C++, Java, 最大公约数, 欧几里德, 算法, 辗转相除法
