TOP榜写作榜手机小说

最近更新新书入库全部小说

白洁小说网 >> 数学心 >> 第一百四十八章 米勒拉宾素性测试(计算数论)

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

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

喜欢数学心请大家收藏:数学心本站更新速度全网最快。

数学心最新章节 - 数学心全文阅读 - 数学心txt下载 - 蔡泽禹的全部小说 - 数学心 白洁小说网

最近更新: 无敌战神附体,对抗剑与魔法 某霍格沃茨的密教教主 原神:神行世间 综影视:时途红颜幻旅录 开心超人之我成为了她们的哥哥 雷鸣彼岸:将军与永恒 HP:当邓布利多有了个女鹅 逃不掉!又被黑化男主强制爱 无限开局 寻常书

数学心最新章节手机版 - 数学心全文阅读手机版 - 数学心txt下载手机版 - 蔡泽禹的全部小说 - 数学心 白洁小说网移动版 - 白洁小说网手机站