混混小说网

手机浏览器扫描二维码访问

第一百四十八章 米勒拉宾素性测试计算数论(第1页)

对于一个数n,如果想要判断它是否为素数,常规的方法为试除法。即,让n依次除以2到sqrt(n)以内的整数。如果有出现除尽的情况,则为合数。

该方法的时间复杂度为O(sqrt(n))在面对n为长整型的时候有可能超出时间要求。因此普遍采用米勒拉宾算法进行素性判定。

在此之前介绍一种伪素数判定方法——小费马定理。

但没有米勒拉宾素性测试快。

米勒拉宾素性测试是:

判断一个数p是否为素数

p首先得为大于等于2的正整数才有可能为素数,

首先判奇偶,若为偶数只有2为素数,

若为奇数(这里可以考虑去掉3甚至5的倍数),则先求出d。

对于每一个底a,让d不断乘以2直到为(p-1)2,

在此过程中(包括原本的d与d=(p-1)2时的情况),

设t为a的d次方模p的余数,

(1)当t=-1时跳出,声明p有可能为素数

(2)当t=1时,若d为奇数,跳出声明p有可能为素数,否则跳出声明p必为合数

(3)当d=(p-1)2时跳出,声明p必为合数。

喜欢数学心请大家收藏:()数学心

开局被渣,反手投资女帝无敌  开局成为峰主,打造万古不朽仙门  大清话事人  在明末奋斗  邪灵战神  都市重生:我在七日世界刷神宠  包青天断案传奇故事汇  造孽啊,曹贼竟是我自己  沉睡千年醒来,749局找上门  一本杂录  春过辽河滩  仙骨  偏偏宠上你  好运撞末日  尘封的仙路  跨越阶层的恋爱  神奇宝贝:开局十连抽,获得梦幻  剑神韩友平第一部  柯南!快看,你爸爸过来了!  高冷学神之攻略手册  

热门小说推荐
极品捉妖系统

极品捉妖系统

万众瞩目之下,楚浩扔出一柄剑这轩辕剑你拿好,以后别在我面前装逼。这天,这地,这沧海,这宇宙,谁都无法阻止我。ps看完了?新书搜索从诡秘复苏开始不当人推荐票刷起来,让我们再次征战。...

我和大圣是兄弟

我和大圣是兄弟

王虎穿越了,而且悲催的成了五指山下的一只老虎。我去,这是要做猴哥虎皮裙的节奏?王虎表示不服。作为一只21世纪穿越来的新时代老虎,怎么着也要和猴哥拜把子,做兄弟啊!此时此刻齐天大圣孙悟空被压五行山马上就满五百年,再有十年,波澜壮阔,影响三界格局的西天取经之旅就要开始,看王虎如何在其中搅动三界风云,与猴哥一起再掀万...

绝色占卜师:爷,你挺住!

绝色占卜师:爷,你挺住!

听说她在占卜,他捧着手眼巴巴的就过来了爱卿,你给本君算算,今晚是本君睡了国师呢?还是国师睡了本君?她哆嗦了一下,一脚就踹了过去谁都不睡!她今晚就阉了你!!重生前,她是惊才绝艳的大占卜师,重生后,她还是上知天文下知地理的一品国师,可是,她算了两世,却没算到自己这一世会犯桃花国师大人,不好了,帝君来了!卧槽!她一下子就从八卦盘里站了起来他来干什么?他不干什么!那就好那就好!她狂抹一把额头上的冷汗。小太监欲哭无泪可他说了,今晚他夜观星象,是个鸾凤和鸣...

大国工程

大国工程

余庆阳一个搬砖二十年的老工程,梦回世纪之交,海河大学毕业,接老爸的班继续搬砖。用两辈子的行动告诉老师,搬砖不是因为我学习不好!是我命中注定要搬砖已有两本百万字完本书超级村主任最强退伍兵,可以放心入坑!大国工程书友群,群聊号码492691021新书重生之大国工匠...

每日热搜小说推荐