公因子什么意思

Question

如题所述

Answer 1

公因子指的是能同时整除几个整数的整数，可以用辗转相除法算出。

辗转相除法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b)=gcd(b,a mod b)。两个整数的最大公约数是能够同时整除它们的最大的正整数。辗转相除法基于如下原理：两个整数的最大公约数等于其中较小的数和两数相除余数的最大公约数。

Stein算法

欧几里得算法是计算两个数最大公约数的传统算法，他无论从理论还是从效率上都是很好的。但是他有一个致命的缺陷，这个缺陷只有在大素数时才会显现出来。

硬件平台，一般整数最多也就是64位，对于这样的整数，计算两个数之间的模是很简单的。对于字长为32位的平台，计算两个不超过32位的整数的模，只需要一个指令周期，而计算64位以下的整数模，也不过几个周期而已。

但是对于更大的素数，这样的计算过程就不得不由用户来设计，为了计算两个超过64位的整数的模，用户也许不得不采用类似于多位数除法手算过程中的试商法，这个过程不但复杂，而且消耗了很多CPU时间。对于现代密码算法，要求计算128位以上的素数的情况比比皆是，设计这样的程序迫切希望能够抛弃除法和取模。

Stein算法由J.Stein于1961年提出，这个方法也是计算两个数的最大公约数。和欧几里得算法不同的是，Stein算法只有整数的移位和加减法，这对于程序设计者是一个福音。扩展欧几里得算法对于最大公约数的计算和普通欧几里得算法是一致的。计算乘法逆元则显得很难明白。我想了半个小时才想出证明他的方法。