墨缘文学网
会员书架
首页 > 都市 > 学霸的另类养成 > 第22章 微小的学术贡献

第22章 微小的学术贡献(2 / 4)

章节目录 加入书签
好书推荐: 我是尸化天师 试炼在影视世界 在小叮当里的漫画家 冰河世纪之超神战车 NBA:传奇主帅,联盟签到十年 四合院:开局阎解旷,我谁都坑 青知锦 初景道君 乾坤未定苦为舟 离岸人

在miller-rabin素数测试中,迭代次数是由测试次数k决定的。

每次迭代的计算包括取模运算和幂运算,它们的复杂度都是多项式级别的。

与指数复杂度的算法相比,多项式复杂度的算法在处理超大数时更加高效。

尽管miller-rabin素数测试是一种概率性测试,但随着测试次数的增加,错误概率可以降低到极小的程度。

虽然miller-rabin素数测试具有多项式时间复杂度,但如果是对于比超大数还要大的数(也就是是说对于一些动辄千万位的数非常大的数,想要验证其是不是素数仍然需要相当大的计算资源和时间才能完成测试。

甚至于在实际应用中,常常会结合其他优化技术和算法来提高素数测试的效率。

而如何验证一个数是不是梅森素数呢?

首先梅森素数也是素数的一种。

因此要先判定这个数是素数。

而后再验证这个数是否符合梅森素数的定义。

具体来说,可以依靠lucas-lehmer测试即卢卡斯-莱默检验法。

卢卡斯-莱默检验法(lucas-lehmertest是一种用于验证梅森素数的特定形式的素数测试方法。

它仅适用于梅森素数的验证(形如2^p-1的素数,其中p是一个素数。

卢卡斯-莱默检验法的原理如下:

初始化s=4。

重复进行以下步骤p-2次:计算s的平方减去2,并将结果对2^p-1取模,即s=(s^2-2)%(2^p-1)。

如果最终得到的s等于,则该数2^p-1是素数;否则,它不是素数。

卢卡斯-莱默检验法是一种确定性的测试方法,可以准确判断形如2^p-1的数是否为素数。

点击切换 [繁体版] [简体版]
章节目录 加入书签
新书推荐: 我的总裁老婆是女神 订婚宴,陆总偷偷勾她尾指 热痒 重生1979,带着全村赶山致富 重生1960:我承包了整座大山 重生白富美后,她放飞自我了 坠崖重生后,京圈太子爷骗我领证 晚风捎来你的信 顾总快追,死遁的白月光回来啦! 重生后,我截胡了大姨子
热门推荐