登陆注册
18217400000141

第141章 米勒拉宾素性测试

对于一个数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必为合数。

同类推荐
  • 月书白传之蜕变

    月书白传之蜕变

    不学无术的阔家少爷,在父亲的强迫下参军,展现了一个普通人到一个军人的转变。这里将告诉你信仰是什么?
  • 江南孤雁

    江南孤雁

    他被迫过继给姑姑,背井离乡来到遥远的江南崇山峻岭之间。从此他像一只倔强的孤雁,在异地他乡浮来荡去,身不由己……这是一部回忆录,也是一部传奇史。
  • 九零后新农民

    九零后新农民

    一个被联合国评价为最不适宜人类居住的地方。九零后青年魏成魔在这里开始了他创业的第一步。以精准扶贫起家,以一己之力带动一地经济的发展。在这个面朝黄土背朝天,干旱少雨,靠天吃饭的西北大山沟。能让一个穷山沟变成家喻户晓的知名地方。 魏成魔这个泥腿子的身上,究竟发生着什么样的变化?
  • 生活挺甜

    生活挺甜

    【本书已签约影视版权+实体出版】 【第四届网络文学现实主义征文大赛特别奖】 80后是第一批被称为叛逆的人群,他们处于一个特殊的时代,一边被人注目着,一边被人鄙视着,一边任人宠溺着,一边任人声讨着……曾经的“叛逆少年”,不知不觉就步入了“油腻中年”,工作与生活的双重压力让他们疲于应付。这个群体中还有一部分更加特殊的群体——80后妇产科男医生,苏庆春就是这类人群,工作中,他被戏称为“万红丛中一点绿”,常年“周旋”在女人堆里;生活中,他要面对强势的女老师妻子、古灵精怪的孩子及人情冷淡的父母,苏庆春该如何化解这一切?
  • 白领黑心

    白领黑心

    记录职场争斗的黑暗角落,领略白领生存的明潜规则!黑不遮白,邪不压正,一个人就是一座城,脚踏实地方能步步为赢!他叫白一城,晋升之路由你开启...
热门推荐
  • 追妻无门:女boss不好惹

    追妻无门:女boss不好惹

    青涩蜕变,如今她是能独当一面的女boss,爱了冷泽聿七年,也同样花了七年时间去忘记他。以为是陌路,他突然向他表白,扬言要娶她,她只当他是脑子抽风,他的殷勤她也全都无视。他帮她查她父母的死因,赶走身边情敌,解释当初拒绝她的告别,和故意对她冷漠都是无奈之举。突然爆出她父母的死居然和冷家有丝毫联系,还莫名跳出个公爵未婚夫,扬言要与她履行婚约。峰回路转,破镜还能重圆吗? PS:我又开新文了,每逢假期必书荒,新文《有你的世界遇到爱》,喜欢我的文的朋友可以来看看,这是重生类现言,对这个题材感兴趣的一定要收藏起来。
  • 漫威小男巫

    漫威小男巫

    这是一个关于熊孩子黑魔法师的成长故事,凑足二十个字
  • 日本推理天才伊坂幸太郎全集(共12册)

    日本推理天才伊坂幸太郎全集(共12册)

    伊坂幸太郎的作品风格鲜明,既能把暴力凶杀写得仿如日常生活般轻松,又能从不经意的对话中迸发鼓舞人心的强大力量。他想象力丰富,擅长多线条叙事,故事看似一团乱麻,结尾却常常令人高呼过瘾,并用其独特的“爱与勇气”打动了一大批忠实读者。
  • 小麦苗桥梁书·稀奇古怪的人

    小麦苗桥梁书·稀奇古怪的人

    全文是由小女孩小妖的妈妈讲故事开始和收束的,这个智慧的妈妈在孩子遇到各种事情或者需要告诉孩子某些道理的时候总是编许多故事,在小妖的世界中就有了各种各样的稀奇古怪的人的形象。不但符合儿童的“泛灵论”,而且拉近了妈妈与孩子的距离,从小故事中感受善良、勇敢和温暖……作者用《一千零一夜》式的传统结构,用心中的爱和笔尖的温情,不但讲述出世间万物的烦恼和幸福,也呈现出生命的美和好。文中稀奇古怪的人虽然都是虚构出来的,但其实也是现实生活的缩影。比如鞋子人的故事,是女儿小妖喜欢穿“鸳鸯鞋”引起的,希望通过这个故事提醒孩子要穿一只球鞋一只拖鞋出门时不要摔倒,但从另一个层面也在告诉读者并不是墨守成规的东西就是对的,尊重个性、尊从每个人的内心更重要。因为邻居家的大姐姐拒绝和小妖玩,小妖很伤心,妈妈编了一个能擦去人忧伤的橡皮人的故事来安慰她,通过这个故事也在告诉孩子不管是忧伤还是快乐,都是记忆的一部分,都值得珍藏……每个故事都有表面意和深层意,希望孩子在读到这些稀奇古怪的人的故事时,快乐开心,还能有所思考,有所成长!
  • 骨钗

    骨钗

    漫漫长夜,你我终将踏上无休止的旅途,当无数个难捱的深夜成为归宿,有多渴望一双温暖的手,犹如葬身万丈悬崖之前,随手拈来一朵带香的花儿……
  • 如是东方

    如是东方

    中国古建筑体现了明确的礼制思想,注重等级体现:形制、色彩、规模、结构、部件等都有严格规定。本书属于“中国古典建筑美学通识类读物”,内容通过普及中国“府+院”为特点的中式建筑为核心,结合作者个人成长及设计经历,详细介绍北方合院建筑特点,并结合目前中国著名建筑遗产,探讨传统文化与现代人居的融合与碰撞,将专业建筑欣赏普及化。
  • 乡里招商黄大明

    乡里招商黄大明

    汝东市组织四套班子去浙江等地学习考察,回来之后就确定这年为“项目年”。秀瑞县委书记龚睿智连夜指示写作班子起草“项目年”的决定,分发给四套班子征求意见。西津乡在全县行动最快,《秀瑞报》头版头条加评论员文章突出报道,乡党委书记吴七因此受到全县通报表扬。本来,副乡长阿光见母亲病重,想推迟几天外出招商,吴七便以看望阿光母亲为由,上门做工作。阿光父亲苏蓝是聪明人,知道吴七在打政治牌,动员阿光上路。乡里决定阿光带一支小分队,分赴温都。小分队除了老乡干部秦谷福外,还有乡医院的医生岳京志。
  • 不负花期不负你

    不负花期不负你

    这是一个以桂花花期为主线,讲述男女主人公的爱情几经辗转终于修成正果的故事。有虐有宠,双洁文,结局美满。那一年,他10岁,她5岁,开得正盛的桂花树下:“北宸哥哥,你要走了吗?”“是啊,丫头。”“哦,那我什么时候能再见到你啊?”“嗯…又一年花开的时候吧!”时光荏苒,命运它总是将我们连在一起;可若记忆尘封,我们谁又还记得谁?“对不起,对不起,先生,我不是故意的。”“你知道你做了什么吗?嗯?”当我们在爱情里迷失方向,相识亦是陌路:“顾先生,今日一别,日后我们当算是回到最初原点;他日若是相见,视彼此为陌生人即可。唯愿各自安好,互不相扰。”然而,当那些尘封在岁月里的记忆被唤醒,你可还愿意与我携手看花开花落?“丫头,如今花开正盛,飘香十里。故人已归,可佳人却不在。你可是也要我等你?如果那样的话,我们还以老树为证、花开为约,可好?”
  • 再也不见,绝望

    再也不见,绝望

    你大步走吧!我不追了。――这场游戏里,是我一厢情愿,我也愿赌服输。
  • 最后一个金融大鳄

    最后一个金融大鳄

    带你识破金融大鳄操纵市场、内幕交易、利益输送的教科书式小说。一眼看穿老鼠仓、股市黑嘴、抢帽子操纵、高频幌骗、拉抬打压、忽悠式重组、空手套白狼……囊括时下热点:国家重拳出击整治金融环境、影视资本投资、互联网P2P爆雷等等。作者是前操盘手,在国内外从事金融投资工作多年。生动刻画了金融从业人员的复杂心理及生活状态,展现了一代金融人的奋斗、迷茫与堕落。翻开本书,看最后一个金融大鳄如何被打回原形。