rho算法

① c++分解质因数求教（时间复杂度一定要优秀！）

1. “分解质因数”定义：每个合数都可以写成几个质数相乘的形式，其中每个质数都是这个合数的因数，把一个合数用质因数相乘的形式表示出来，叫做分解质因数，如30 = 2 × 3 × 5。质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，1 既不是质数也不是合数。

2. 简单思路：先从n=2，3，4...开始，跟合数m取余，如果n能被m除尽，n就是m的因数，然后m = m / n，继续分解m剩下的部分。不用担心n增加后，n=4之类的合数也能被m除尽，因为每次都是先从2，3...开始的，跟后面4，6之类的合数取余为0的合数，跟2，3取余一定能是0。n为1的时候，就跳出求解逻辑。这种方法不一定是最快的，但却是最容易理解。

3. 代码示例：

   int n = 1000;

   //1不是质数

   while (n > 1) {

   for (int i = 2; i <= n; i++) {

   if (n % i == 0) {

   cout << i << endl;

   n /= i;

   break;

   }

   }

   }

   结果：2 2 2 5 5 5

② 椭圆加密算法的公钥密码系统的加密算法ECC与RSA的对比

第六届国际密码学会议对应用于公钥密码系统的加密算法推荐了两种：基于大整数因子分解问题（IFP）的RSA算法和基于椭圆曲线上离散对数计算问题（ECDLP）的ECC算法。RSA算法的特点之一是数学原理简单、在工程应用中比较易于实现，但它的单位安全强度相对较低。目前用国际上公认的对于RSA算法最有效的攻击方法--一般数域筛(NFS)方法去破译和攻击RSA算法，它的破译或求解难度是亚指数级的。ECC算法的数学理论非常深奥和复杂，在工程应用中比较难于实现，但它的单位安全强度相对较高。用国际上公认的对于ECC算法最有效的攻击方法--Pollard rho方法去破译和攻击ECC算法，它的破译或求解难度基本上是指数级的。正是由于RSA算法和ECC算法这一明显不同，使得ECC算法的单位安全强度高于RSA算法，也就是说，要达到同样的安全强度，ECC算法所需的密钥长度远比RSA算法低（见表1和图1）。这就有效地解决了为了提高安全强度必须增加密钥长度所带来的工程实现难度的问题.

③ 安全质数的详细介绍

安全质数在加密算法中的运用：一些因子分解的算法（象Pollard Rho算法）的计算时间部份取决于被分解数的质因子减去一的因子大小，假如被分解的数以一个安全素数2p+1作为因子，因为此素数减去一有一个大素数p做为因子，计算时间会变多。可是很容易理解任何一个小于10的素数都不是真正安全的，对于任何一个有着合适算法的现代计算机都能在适当的时间内判断出它的素性，可是这些小一点的安全素数在加密算法原理的教学中仍然还是很有用的。对于安全素数还没有像对费马素数与梅森素数一样的特别的素性检测方法。
开始的几个安全素数是：
5, 7, 11, 23, 47, 59, 83, 107, 167, 179, 227, 263, 347, 359, 383, 467, 479, 503, 563, 587, 719, 839, 863, 887, 983, 1019, 1187, 1283, 1307, 1319, 1367, 1439, 1487, 1523, 1619, 1823, 1907
之所以叫它们是“安全”素数，是因为它们在加密算法中的运用，很容易理解：任何一个小于1050的素数都不是真正安全的，对于任何一个有着合适算法的现代计算机都可以在适当的时间内判断出它的素性，但是这些小一点的安全素数在加密算法原理的教学中仍然还是很有用的。 不过对于安全素数还没有像对费马素数与梅森素数一样的特别的素性检测方法。
除了5，还没有即是费马素数又是安全素数的数了。一个给定的费马素数F，一个小小的反证就可以证明（F－1）/2会是2的平方。
除了7，还没有即是梅森素数又是安全素数的数了。这个证明有点麻烦，不过仍然在基础代数的范畴内，p必须是素数，2p-1才有可能是素数，那么((2p - 1) - 1)/2 = 2p - 1 - 1,（梅森素数），因为只有当p=3时p－1才有可能是素数，即2^3-1=7。
第一类坎宁安链中所有的数除了最后一项都是索菲热尔曼素数，除了第一项都是安全素数，如果安全素数是以7结尾，那么它具有10n+7的形式。

④ 椭圆加密算法的方程

椭圆曲线密码体制来源于对椭圆曲线的研究，所谓椭圆曲线指的是由韦尔斯特拉斯（Weierstrass）方程：
y2+a1xy+a3y=x3+a2x2+a4x+a6 (1)
所确定的平面曲线。其中系数ai(I=1,2,…,6)定义在某个域上，可以是有理数域、实数域、复数域，还可以是有限域GF（pr），椭圆曲线密码体制中用到的椭圆曲线都是定义在有限域上的。
椭圆曲线上所有的点外加一个叫做无穷远点的特殊点构成的集合连同一个定义的加法运算构成一个Abel群。在等式
mP=P+P+…+P=Q (2)
中，已知m和点P求点Q比较容易，反之已知点Q和点P求m却是相当困难的，这个问题称为椭圆曲线上点群的离散对数问题。椭圆曲线密码体制正是利用这个困难问题设计而来。椭圆曲线应用到密码学上最早是由Neal Koblitz 和Victor Miller在1985年分别独立提出的。
椭圆曲线密码体制是目前已知的公钥体制中，对每比特所提供加密强度最高的一种体制。解椭圆曲线上的离散对数问题的最好算法是Pollard rho方法，其时间复杂度为，是完全指数阶的。其中n为等式(2)中m的二进制表示的位数。当n=234, 约为2117，需要1.6x1023 MIPS 年的时间。而我们熟知的RSA所利用的是大整数分解的困难问题，目前对于一般情况下的因数分解的最好算法的时间复杂度是子指数阶的，当n=2048时，需要2x1020MIPS年的时间。也就是说当RSA的密钥使用2048位时，ECC的密钥使用234位所获得的安全强度还高出许多。它们之间的密钥长度却相差达9倍，当ECC的密钥更大时它们之间差距将更大。更ECC密钥短的优点是非常明显的，随加密强度的提高，密钥长度变化不大。
德国、日本、法国、美国、加拿大等国的很多密码学研究小组及一些公司实现了椭圆曲线密码体制，我国也有一些密码学者
做了这方面的工作。许多标准化组织已经或正在制定关于椭圆曲线的标准，同时也有许多的厂商已经或正在开发基于椭圆曲线的产品。对于椭圆曲线密码的研究也是方兴未艾，从ASIACRYPTO’98上专门开辟了ECC的栏目可见一斑。
在椭圆曲线密码体制的标准化方面，IEEE、ANSI、ISO、IETF、ATM等都作了大量的工作，它们所开发的椭圆曲线标准的文档有：IEEE P1363 P1363a、ANSI X9.62 X9.63、 ISO/IEC14888等。
2003年5月12日中国颁布的无线局域网国家标准 GB15629.11 中，包含了全新的WAPI(WLAN Authentication and Privacy Infrastructure)安全机制，能为用户的WLAN系统提供全面的安全保护。这种安全机制由 WAI和WPI两部分组成，分别实现对用户身份的鉴别和对传输的数据加密。WAI采用公开密钥密码体制，利用证书来对WLAN系统中的用户和AP进行认证。证书里面包含有证书颁发者(ASU)的公钥和签名以及证书持有者的公钥和签名，这里的签名采用的就是椭圆曲线ECC算法。
加拿大Certicom公司是国际上最着名的ECC密码技术公司,已授权300多家企业使用ECC密码技术，包括Cisco 系统有限公司、摩托罗拉、Palm等企业。Microsoft将Certicom公司的VPN嵌入微软视窗移动2003系统中。
以下资料摘自：http://www.hids.com.cn/data.asp

⑤ 比如一个很大超过千的数怎么才能快速分解质因数呢举个实际例子

运用Pollard-Rho算法，复杂度为O(n^1/4)，不过这个算法只能够判断2^63以内的，更大
的限于long long int本身的约束，无法进行判断了

⑥ 如何快速简便的判断一个多位数是不是质数

1. 简单的随机算法的话有 Miller-Rabin 算法2. 整数分解现在没有多项式算法，简单算法有Pollard Rho算法，比暴力试除快。

⑦ 为什么要进行大数分解

rho算法其实是一种概率上的算法，虽然是靠概率，但是其准确率非常高（99.9%），更重要的是，该算法效率极高。其主要基于密码学当中的一个“生日悖论“来进行算法的设计。简单来讲就是，我们将N的两个因子x和y（就假设它有两个）从一大堆数里挑出来的概率非常小，但是如果我们挑满足x-y等于某个数的话，概率就要大很多。更进一步，如果我们找gcd(|x-y| ,N)呢？那么概率就会更大，就是这么个道理。
————————————————
版权声明：本文为CSDN博主“the__apollo”的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/The__Apollo/article/details/80279716

⑧ 哪些算法让你感觉醍醐灌顶

贝叶斯定理

比如这样一个问题：你喜欢上一个人的概率，你觉得一个人某方面好的概率，你喜欢上一个人然后觉得这个人某方面好的概率，你觉得一个人某方面好然后喜欢上这个人的概率，这4个之间有什么关系呢？

用数学语言表达：P(喜欢上一个人), P(觉得一个人某方面好), P(觉得这个人某方面好|喜欢上一个人) 和 P(喜欢上这个人|觉得一个人某方面好) 有什么关系呢？

我们生活中遇到的很多概率其实都是条件概率/后验概率(在某一条件下成立的事件的概率)，贝叶斯定理揭示了不同的条件概率之间的关系: )

一瞬间，感觉让你发现了世界运行了某些奥秘

KMP非常优美，SIFT 图像匹配算法很强大，plsa语义相似度计算也让我震撼，不过最让我震撼的还是mathematica里的fullsimplify背后的算法。

Fullsimplify这玩意能搞定很多人都搞不定的公式，我说的搞不定是指该问题本身人可以在三五步之内求解，但却是很难求解的问题，例如某些三角函数的积分需要巧妙地作换元积分才能得解。

从思想上看，最深刻的是递归，以及求泛函极值的最小作用量。基于这两种思想的算法，比如快排、HMM中的Baum-Welch，都是精美的算法，但背后的思想根基并非首创。动态规划、蒙特卡洛类的算法也属此列。

此外，有“道法自然”意味的模拟退火、蚁群、遗传、粒子群这些，思想方法上有创新，但是算法设计上与神经网络、SVM、HMM相比，就略显粗糙。

⑨ 安全质数的释义

安全素数（安全质数）是满足2p+1形式的一类数，在这里p也应是素数。（相反地，素数p叫做索菲热尔曼素数。）详细介绍之所以叫它们是“安全”素数，是因为它们在加密算法中的运用：某些因子分解的算法（如Pollard Rho算法）的计算时间的部份取决于被分解数的质因子减去一的因子大小，而若被分解的数以一个安全素数2p+1作为因子，由于此素数减去一有一个大素数p做为因子，计算时间将会变多。但是很容易理解任何一个小于10的素数都不是真正安全的，因为对于任何一个有着合适算法的现代计算机都能在适当的时间内判断出它的素性，但是这一些小一点的安全素数在加密算法原理的教学中仍然还是很有用的。

⑩ 判断整数是否分解成两个质素的高效算法

这个问题，首先用小质数测试。 通过之后：
然后，尝试用Pollard-Rho算法进行分解因子。当然你必须准备一个好的 素数测试算法。素数测试算法，可用Miller-Rabin对付~