词条 | 卡米切尔数 |
释义 | Carmichael数。 费马小定理: 费马小定理(Fermat theorem): 设p为一素数,而a与p互素,则 a^p - a 必为p的倍数。 利用费马小定理,对于给定的整数n,可以设计一个素数判定算法。通过计算d=2^(n-1)mod n来判定整数n的素性。当d不等于1时,n肯定不是素数;当d等于1时,n则很可能是素数。但也存在合数n使得2^(n-1)≡1(mod n)。例如,满足此条件的最小合数是n=341。为了提高测试的准确性,我们可以随机地选取整数1Carmichael数,前3个Carmichael数是561,1105,1729。Carmichael数是非常少的。在1~100000000范围内的整数中,只有255个Carmichael数。 |
随便看 |
百科全书收录4421916条中文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。