Hiho 数论一·Miller-Rabin质数测试,大素数判断

2024-03-27 10:18

本文主要是介绍Hiho 数论一·Miller-Rabin质数测试,大素数判断,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目1 : 数论一·Miller-Rabin质数测试

时间限制: 10000ms
单点时限: 1000ms
内存限制: 256MB

描述

小Hi和小Ho最近突然对密码学产生了兴趣,其中有个叫RSA的公钥密码算法。RSA算法的计算过程中,需要找一些很大的质数。

小Ho:要如何来找出足够大的质数呢?

小Hi:我倒是有一个想法,我们可以先随机一个特别大的初始奇数,然后检查它是不是质数,如果不是就找比它大2的数,一直重复,直到找到一个质数为止。

小Ho:这样好像可行,那我就这么办吧。

过了一会儿,小Ho拿来了一张写满数字的纸条。

小Ho:我用程序随机生成了一些初始数字,但是要求解它们是不是质数太花时间了。

小Hi:你是怎么做的啊?

说着小Hi接过了小Ho的纸条。

小Ho:比如说我要检测数字n是不是质数吧,我就从2开始枚举,一直到sqrt(n),看能否被n整除。

小Hi:那就对了。你看纸条上很多数字都是在15、16位左右,就算开方之后,也有7、8位的数字。对于这样大一个数字的循环,显然会很花费时间。

小Ho:那有什么更快速的方法么?

小Hi:当然有了,有一种叫做Miller-Rabin质数测试的算法,可以很快的判定一个大数是否是质数。

提示:Miller-Rabin质数测试  

输入

第1行:1个正整数t,表示数字的个数,10≤t≤50

第2..t+1行:每行1个正整数,第i+1行表示正整数a[i],2≤a[i]≤10^18

输出

第1..t行:每行1个字符串,若a[i]为质数,第i行输出"Yes",否则输出"No"

样例输入
3
3
7
9

样例输出

Yes
Yes
No

提示:Miller-Rabin质数测试

小Hi:这种质数算法是基于费马小定理的一个扩展,首先我们要知道什么是费马小定理
费马小定理:对于质数p和任意整数a,有a^p ≡ a(mod p)(同余)。反之,若满足a^p ≡ a(mod p),p也有很大概率为质数。
将两边同时约去一个a,则有a^(p-1) ≡ 1(mod p)
也即是说:假设我们要测试n是否为质数。我们可以随机选取一个数a,然后计算a^(n-1) mod n,如果结果不为1,我们可以100%断定n不是质数。
否则我们再随机选取一个新的数a进行测试。如此反复多次,如果每次结果都是1,我们就假定n是质数。
该测试被称为Fermat测试。需要注意的是:Fermat测试不一定是准确的,有可能出现把合数误判为质数的情况。
Miller和Rabin在Fermat测试上,建立了Miller-Rabin质数测试算法。

与Fermat测试相比,增加了一个二次探测定理
如果p是奇素数,则 x^2 ≡ 1(mod p)的解为 x ≡ 1 或 x ≡ p - 1(mod p)
如果a^(n-1) ≡ 1 (mod n)成立,Miller-Rabin算法不是立即找另一个a进行测试,而是看n-1是不是偶数。如果n-1是偶数,另u=(n-1)/2,并检查是否满足二次探测定理即a^u ≡ 1 或 a^u ≡ n - 1(mod n)。
举个Matrix67 Blog上的例子,假设n=341,我们选取的a=2。则第一次测试时,2^340 mod 341=1。由于340是偶数,因此我们检查2^170,得到2^170 mod 341

这篇关于Hiho 数论一·Miller-Rabin质数测试,大素数判断的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/851770

相关文章

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程

《SpringBoot中整合RabbitMQ(测试+部署上线最新完整)的过程》本文详细介绍了如何在虚拟机和宝塔面板中安装RabbitMQ,并使用Java代码实现消息的发送和接收,通过异步通讯,可以优化... 目录一、RabbitMQ安装二、启动RabbitMQ三、javascript编写Java代码1、引入

Nginx设置连接超时并进行测试的方法步骤

《Nginx设置连接超时并进行测试的方法步骤》在高并发场景下,如果客户端与服务器的连接长时间未响应,会占用大量的系统资源,影响其他正常请求的处理效率,为了解决这个问题,可以通过设置Nginx的连接... 目录设置连接超时目的操作步骤测试连接超时测试方法:总结:设置连接超时目的设置客户端与服务器之间的连接

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

性能测试介绍

性能测试是一种测试方法,旨在评估系统、应用程序或组件在现实场景中的性能表现和可靠性。它通常用于衡量系统在不同负载条件下的响应时间、吞吐量、资源利用率、稳定性和可扩展性等关键指标。 为什么要进行性能测试 通过性能测试,可以确定系统是否能够满足预期的性能要求,找出性能瓶颈和潜在的问题,并进行优化和调整。 发现性能瓶颈:性能测试可以帮助发现系统的性能瓶颈,即系统在高负载或高并发情况下可能出现的问题

字节面试 | 如何测试RocketMQ、RocketMQ?

字节面试:RocketMQ是怎么测试的呢? 答: 首先保证消息的消费正确、设计逆向用例,在验证消息内容为空等情况时的消费正确性; 推送大批量MQ,通过Admin控制台查看MQ消费的情况,是否出现消费假死、TPS是否正常等等问题。(上述都是临场发挥,但是RocketMQ真正的测试点,还真的需要探讨) 01 先了解RocketMQ 作为测试也是要简单了解RocketMQ。简单来说,就是一个分

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

【测试】输入正确用户名和密码,点击登录没有响应的可能性原因

目录 一、前端问题 1. 界面交互问题 2. 输入数据校验问题 二、网络问题 1. 网络连接中断 2. 代理设置问题 三、后端问题 1. 服务器故障 2. 数据库问题 3. 权限问题: 四、其他问题 1. 缓存问题 2. 第三方服务问题 3. 配置问题 一、前端问题 1. 界面交互问题 登录按钮的点击事件未正确绑定,导致点击后无法触发登录操作。 页面可能存在