http://b.niaojidi.com

卡迈克尔数是什么意思,卡迈克尔数有什么意义

  卡迈克尔数是什么意思,卡迈克尔数的定义是对于合数n,如果对于所有与n互质的正整数b,都有同余式b^(n-1)≡ 1 (mod n)成立,则称合数n为Carmichael数。

卡迈克尔数是什么意思

卡迈克尔数有什么意义

  对于合数n,如果对于所有与n互质的正整数b,都有同余式b^(n-1)≡ 1 (mod n)成立,则称合数n为Carmichael数。 2016年物流工人余建春带着自己的五项数学发现登上了浙江大学数学系的讲台,与教授和博士生们同堂论道,最具价值的发现是一组“卡迈克尔数”的判别准则。

卡迈克尔数是什么意思

  卡迈克尔数的定义是对于合数n,如果对于所有与n互质的正整数b,都有同余式b^(n-1)≡ 1 (mod n)成立,则称合数n为Carmichael数。

  定理介绍:

  每个Carmichael至少是三个不同素数的乘积。

  如561=3*11*17。

  费马小定理(Fermat theorem):

  设p为一素数,对于任意整数a,有a(p-1)≡1 (mod p)。

  假如p是质数,且gcd(a,p)=1,那么 a^(p-1) ≡1(mod p) 假如p是质数,且a,p互质,那么 a的(p-1)次方除以p的余数恒等于1。

  费马判定:

  设p为一素数,而a与p互素,则 a^p-a 必为p的倍数。

   利用费马小定理,对于给定的整数n,可以设计一个素数判定算法。

  通过计算d=a^(n-1)mod n来判定整数n的素性。

  当d不等于1时,n肯定不是素数;当d等于1时,n则很可能是素数。

  但也存在合数n使得d=a^(n-1)≡1(mod n)。

  例如,当a=2时,满足d=1的最小合数是n=341。

  为了提高测试的准确性,我们可以随机地选取多个a对a^(n-1)mod n的结果进行测试。

  能通过全部a的测试的合数n,被称为Carmichael数,前3个Carmichael数是561,1105,1729。

  Carmichael数是非常少的。

  在1~100000000范围内的整数中,只有255个Carmichael数。

郑重声明:为了让新农科技信息更丰富,我们修改了原文排版和分段,如有冒犯你的利益,请第一时间联系我们修改或删除,感谢!

新农看点
版权与免责声明:
①凡本站注明"来源:新农科技"的所有作品,均由本站编辑搜集整理,并加入大量个人点评、观点、配图等内容,版权均属于新农科技,未经本站许可,禁止转载,违反者本站将追究相关法律责任。
②本站转载并注明自其它来源的作品,目的在于传递更多信息,并不代表本站赞同其观点或证实其内容的真实性,不承担此类作品侵权行为的直接责任及连带责任。其他媒体、网站或个人从本站转载时,必须保留本站注明的作品来源,并自负版权等法律责任。
③如涉及作品内容、版权等问题,请在作品发表之日起一周内与本站联系,我们将在您联系我们之后24小时内予以删除,否则视为放弃相关权利。