python生成一组1024与512位数的大素数对_win 如何生成1024位质数-程序员宅基地

技术标签: 素数判断  python  大素数  素数  大质数  

python生成一组二进制1024位和512位数的大质数对


前些天同学求助: 用python生成一组二进制1024位与512位数的大素数对,要求1024位的质数减一后可以整除512位数,经过两天鏖战后成功,在这里总结一下思路与代码。简单来讲,生成质数对首先要生成质数,之后再成对就ok了,下面分成两部分说明。


一. 生成大素数

解决这个问题首先需要生成大素数,一个二进制的1024位数大概相当于300位十进制位数,运用穷举法最多可能跑到1亿(9位十进制数)这种单位,300位的大数用我的电脑是不可能跑出来的,所以只能更换算法。

经过查阅,随着数的增大,质数的数量其实是在大幅增多的,而随机生成一个1024位二进制奇数很容易,只要能判断出来这个数是否是质数就可以了,如果不成立的话,在附近不断+2应该很快就能找到了一个质数。根据这个想法,生成大素数的算法分3部:

1.生成伪素数 (把未通过验证的奇数称为伪素数)
2.判断伪素数是否为素数
3.如果不成立,循环判断查找

1.生成伪素数

算法很简单,直接贴代码。

# 其实这个二级制奇数产生代码感觉很冗长,可以优化的很多,欢迎大神指教改进
def proBin(w):  # w表示希望产生位数
    list = []
    list.append(1)  #最高位定为1
    for i in range(w - 2):
        c = randint(0, 1)
        list.append(c)
    list.append(1)
    ls2 = [str(j) for j in list]
    ls3 = ''.join(ls2)
    b = int(ls3[0])
    for i2 in range(len(ls3) - 1):
        b = b << 1
        b = b + int(ls3[i2 + 1])
    d = long(b)
    return d

2.判断伪素数是否为素数

这一部分自己的代码编了好几种都跑不理想,想了很久没什么办法,求助度娘,了解素数测试算法后,最终选择了主流的Miller-Rabin检测。这里贴一段百度知道的简介:

Miller-Rabin检测基于概率测试算法,在构建密码安全体系中占有重要的地位

后面会对Miller-Rabin检测原理做深入介绍,如果不关心数学过程,可以跳过这一部分,直接看代码。

Miller-Rabin检测是Fermat算法加入二次探测定理的一种实现,它的理论基础是由Fermat定理引申而来,这里先介绍Fermat定理。

(1)Fermat 定理

Fermat 定理:p是一个质数(非2),a是任何整数(1≤ a≤n-1) ,则 a p a^p ap ≡ a(mod p) 或 a p − 1 a^{p-1} ap1 ≡ 1(mod p)

a p a^p ap ≡ a(mod p) 为 同余符号,表示 a p a^p ap mod p = a,也可以理解为 a p a^p ap- a可以被 p整除 ,还可以理解为 a p a^p ap与 a 除以p的余数相等, 除以同余式 a ≡ a (mod p)后得常用结论:

a p − 1 a^{p -1} ap1 ≡ 1(mod p)

根据定理,我们可以随机选取一个数a,然后计算 a N − 1 a^{N - 1} aN1 mod N,观察结果是否为1,如果是1,需要进一步检测,如果不是1,则N一定不是质数。

Fermat定理实现: (这一段参考 blog 蛇小狼)
因为N是300位以上的数字, a N − 1 a^{N - 1} aN1 mod N并不容易计算,这里介绍一个模运算规则
a b a^b ab mod p = ( a  mod  p ) b {(a\text{ mod } p)} ^ b (a mod p)b mod p
因为a很小,N很大,所以计算 a N a^{N} aNmod p可以通过递归降幂实现,如果N为偶数:
a N a^{N} a

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_33828894/article/details/81358051

智能推荐

如何使用计算机管理来为硬盘分区,电脑如何硬盘分区合理_电脑硬盘分区的基本步骤-win7之家...-程序员宅基地

文章浏览阅读1.3k次。我们都知道,在给电脑安装完系统的过程中,有些用户也会顺便将自己电脑中的硬盘进行分区处理,以此来帮助用户在使用电脑时更好的对文件进行分类管理,让用户寻找文件时更加的快速,那么电脑如何硬盘分区合理呢?今天小编就来给大家分享一篇电脑硬盘分区的基本步骤。具体步骤:1、首先先对固态硬盘做分区,这里使用PE系统自带diskgenius硬盘固盘工具。选择快速分区即可开启下列界面,固态硬盘只分一个区(120G~2..._硬盘分区怎样分好

区块链的架构模型以及核心技术-程序员宅基地

文章浏览阅读5.5k次,点赞2次,收藏6次。一.架构模型一般说来,区块链系统由数据层、网络层、共识层、激励层、合约层,应用层组成。数据层: 封装了底层数据区块以及相关的数据加密和时间戳等基础数据和基本算法。网络层: 则包括分布式组网机制、数据传播机制和数据验证机制等。共识层: 主要封装网络节点的各类共识算法。激励层: 将经济因素集成到区块链技术体系中来,主要包括经济激励的发行机制和分配机制等。合约层: 主要封装各类脚本、算法和...

POJ 2299 Ultra-QuickSort 线段树-程序员宅基地

文章浏览阅读55次。题目链接题意:求冒泡排序的交换次数,即求逆序数,即求对于每个数前面有多少个数比他大,n < 500,000,0 ≤ a[i] ≤ 999,999,999。题解:因为值较大,个数较少,所以我们把每个元素进行映射,比如50,20,30,16,就映射为4,2,3,1这种。先记录下标然后sort排序后用rank数组记录每个数最后所在的位置,rank数组里存的值就是映射后的值,更新加查询即可。...

远离国学100年以后--《国学大师之死》-程序员宅基地

文章浏览阅读115次。我出生于20世纪70年代,小时侯根本没听说过《诗经》、《千字文》、《幼学琼林》之类的书,更别说四书五经了,一直到高中时,这些名词才变成了语文考试中的一道题目,而且也只是考察什么叫四书,什么叫五经,至于里面的内容则不在我们的掌握范围内。大学毕业后,虽然不再应付考试写命题作文,但每每用大白话罗里罗唆讲一个道理却讲不清时,就觉得自己语言无味,面目可憎了——还是文科毕业的学生呢!闲时偶然翻翻《老子》、..._新文化运动骂幼学琼林

大数据——Java 知识点整理_java大数据需要掌握哪些框架的哪些内容-程序员宅基地

文章浏览阅读1.3w次,点赞12次,收藏30次。1. JDK 和 JRE 有什么区别?JDK:Java Development Kit 的简称,java开发工具包,提供了java的开发环境和运行环境。 JRE:Java Runtime Environment 的简称,java运行环境,为java的运行提供了所需环境。具体来说,JDK其实包含了JRE,同时还包含了编译java源码的编译器javac,还包含了许多java程序调试和分析的工具。要运行java程序,只需要安装JRE就可以了,如果需要编写java程序,则还需要安装JDK。2. java_java大数据需要掌握哪些框架的哪些内容

硬盘柱面损坏怎么办_硬盘坏道屏蔽工具,详细教您如何修复硬盘坏道-程序员宅基地

文章浏览阅读9.7k次。我们有遇到过硬盘出现坏道的用户都知道,硬盘坏道的确是件感觉糟糕透了的事情,会让我们的电脑运行速度变慢,如果当我们遇见这种情况,可以使用硬盘坏道屏蔽工具来对硬盘坏道进行屏蔽,从而到达修复的目的,下面就是使用的方法。长期使用的笔记本和台式机,硬盘可能会有坏道,肯定不会全部都是坏道,不能使用了。硬盘在使用过程产生了坏道,怎么屏蔽呢,能修复吗?答案是肯定的,为了让硬盘得到使用最大化,下面,小编就把硬盘坏道..._固态硬盘柱面损坏怎么办啊

随便推点

使用Arduino Due调用FFT库函数时编译器报错_arduinofft fft = arduinofft();为什么编译总是报错呢-程序员宅基地

文章浏览阅读1.5k次,点赞3次,收藏5次。最近在用Arduino Due开发板调用库函数进行FFT运算,我选择的IDE为Arduino 1.8.9,安装的软件包为Arduino SAM boards(32-bits ARM Cortex-M3)by Arduino 版本1.6.12,但编译器始终不通过,错误如下:Arduino:1.8.9 (Windows 10), 开发板:"Arduino Due (Programming Por..._arduinofft fft = arduinofft();为什么编译总是报错呢

git常用命令+代码上传冲突+vscode拉取代码报would clobber existing tag错误_(would clobber existing tag)-程序员宅基地

文章浏览阅读1.2k次。记录自己开发过程中遇到的问题...提交:1、提交到同级目录:git add .2、提交到缓存 并附上提交信息:git commit -m ":提示信息"3、推送到指定分支,如若没指定,默认为master:git push origin‘分支名’拉取:克隆线上指定分支代码:git clone -b “分支名” “地址”没有加-b 则默认拉取默认分支合并:合并“xx”分支到当前分支:git merge “xx”解决上传代码冲突:1、暂存到缓存:git _(would clobber existing tag)

java 包导入快捷键_Java导入包的快捷键-程序员宅基地

文章浏览阅读4.9k次,点赞2次,收藏11次。Random类是在java.util这个包中。可以手动在源程序顶部输入importjava.util.Random;语句来申明该程序将要使用java.util包中的Random类,然而有了Eclipse,就不用那么麻烦了—把光标移动到有红色波浪线的Random上,然后按下Ctrl+Shift+M,Eclipse会自动帮你完成导入的工作了。此时保存一下源代码,警告是不是消失了?希望你牢记这个快捷键的..._java导入类包快捷键

MIPS反汇编拆炸弹-程序员宅基地

文章浏览阅读6.6k次,点赞26次,收藏114次。计算机系统原理的实验,参考了我的前舍友和不知道哪位同学的博客,不过写得也太简略了并且还有一些错误,更像是单纯的记录,对手头没代码的人大概没啥意义吧。所以就把我自己做时的带注释的代码贴住来吧,也不过是记录罢了。两位同学的博客:MIPS - 反汇编 - 拆炸弹 - bomb(如你所见直接把标题抄过来了)bomb二进制炸弹拆除实验(MIPS)如果有同校学弟做实验时看到这篇博客,还是希望可以先尽量尝试独立完成,实在没办法时再来参考。如有错误,欢迎指正。前导知识gdb操作请看:GDB汇编调试指令合集MI_mips反汇编

nRF 蓝牙广播数据及操作相关_sd_ble_gap_adv_data_set-程序员宅基地

文章浏览阅读1.8k次。若使用 advdata 中 sd_ble_gap_adv_set_configure 的方法设置广播,仍可以按照advertising的配置方法,广播数据结构体用 ble_advdata_t ,将各值填入后,要解析一遍才可 sd_ble_gap_adv_set_configure 配置广播数据:/**@brief Struct that contains pointers to th..._sd_ble_gap_adv_data_set

虚拟机安装Centos7.8_centos7.8虚拟机安装-程序员宅基地

文章浏览阅读825次。虚拟机安装Centos7.8下载centos7镜像安装Centos7.8标准版用Xhell或其他工具进行连接最后下载centos7镜像[阿里镜像下载链接][http://mirrors.aliyun.com/centos/7.8.2003/isos/x86_64/][其他镜像下载站参考这里][http://isoredirect.centos.org/centos/7/isos/x86_64/],选择国内的资源站下载速度会比较快!按照需求选择版本,这里演示在VMware安装Centos7.8标准版_centos7.8虚拟机安装

推荐文章

热门文章

相关标签