Pollard的rho启发式因子分解算法 [CodeVS 4939] 欧拉函数:Miller-Rabin + Pollard-rho 质因数分解

本文主要是介绍Pollard的rho启发式因子分解算法 [CodeVS 4939] 欧拉函数:Miller-Rabin + Pollard-rho 质因数分解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Pollard的rho启发式因子分解算法用于给出整数的一个因子。在一定的合理假设下,如果n有一个因子p,可在 O(p) 的期望时间内可找出n的一个因子p。

关于其复杂度,Wikipedia是这样叙述的:

If the pseudo random number x = g(x) occurring in the Pollard ρ algorithm were an actual random number, it would follow that success would be achieved half the time, by the Birthday paradox in O(p^(1/2)) ≤ O (n^(1/4)) iterations. It is believed that the same analysis applies as well to the actual rho algorithm, but this is a heuristic claim, and rigorous analysis of the algorithm remains open.

以下绝大部分来自《算法导论》。

Pollard-rho算法的核心是用递推式 xi+1=(x2i+c)modn 生成一个最终会进入循环的“随机”序列(表示成有向图,看起来就像ρ,这就是算法名字的由来)。虽然只显式地生成了一个序列,实际上同时生成了许多形如ρ的序列(后面将会推证);只要两个指针都进入某个ρ的圈圈里,把它们所指向的值作差,取绝对值,和n求gcd,就能得到n的一个因子。

伪代码如下:

Pollard-Rho(n, c)i = 1k = 2y = x = a random integer in [0, n)d = 1while d == 1i = i+1x = (x*x+c) mod nif x == yreturn nd = gcd(n, abs(x-y))if i == kk = k*2y = xreturn d

它的正确性是显然的。算法可能会失败地返回一个平凡因子n,也可能成功地返回一个n的某个非平凡因子。

xi+1=(x2i+c)modn 的循环大小为C,循环的第一项是 xt ,进入循环后的某一时刻,k会被赋予一个不小于C的值,此时的x被保存为y,再转一圈,y固定不动,x会回到y,算法以失败终止。

必有2的某次幂落在区间[t, 2t]内,因此在不超过第2t步,循环内的某个值将被保存。此时的k可能小于C,无妨,因为必有2的某次幂落在区间[C, 2C]内,2C步之内,有k不小于C成立。于是,至多走(2*min(t, C)+C)步,算法终止。这个算法叫Brent判圈算法(Brent’s cycle finding method),与Floyd判圈算法均为线性,但常数优于后者(至少3C次计算后继结点)。根据Wikipedia,Pollard的原始版本采用Floyd判圈算法,后来由Richard Brant用自己新发明的判圈算法加以改进。

设n有一个因子p,其实我们同时在计算 xi=ximodp ,并且递推式具有相同的形式:

xi+1=xi+1modp=(x2i+c)modnmodp=(x2i+c)modp=((ximodp)2+c)modp=(x2i+c)modp

同样是ρ形。循环内两个数作差,是p的倍数,和n取gcd,因子p或p的某倍便被呈现出来。与上面的论证类似,进入循环后不超过 t 步,循环内的某个值将被保存,下一步,p被呈现。显然 tt CC

假设 {xi} 是随机的,则 t C 都是 O(p) 的。

生日悖论:从n个数中可重复地随机选择k个,当 k2n 时,存在两数相等的概率大于1/2。

用数学期望描述这个命题:相等数对的数目不少于1。这样计算起来会简单一些。

1i<jk 定义指示器随机变量 Xij=I{ij} ,则 E[Xij]=1n

E[i=1kj=i+1kXij]=i=1kj=i+1kE[Xij]=i=1kj=i+1k1n=k(k1)2n

令上式 1 ,得到一个充分条件 k2n

把这个结论运用到我们的问题中来。 t=O(p) C=O(p)

至此,一切都看起来很美好。如果n有某个因子p,则 O(p) 左右次循环后,我们就能找到它。

然而,推导这一切的假设显然不成立。 {xi} 不是随机的。另外,存在这样一种可能:所有ρ的尺寸相同,这将导致只能找到平凡因子n;这种情况需要换一个参数c,《算法导论》告诉我们,除了0和2,其他数都是不错的选择。所以,本算法的名称有定语“启发式”。

CodeVS 4939 欧拉函数

这道题是mhb同学放到CodeVS上的Orz 据其本人所言,当时试除+卡常数,最终把数据范围开到这么变态……真是太神啦……题解页面中提到的qwertyu也很神,感谢Ta的代码。

结合Miller-Rabin、Pollard-rho两个算法可以进行质因数分解。如果n是素数,返回;否则,求n的一个非平凡因子d,递归。由于本题计算的是欧拉函数值,只需要知道有哪些质因子,而不需要知道每个质因子的指数,所以可以将n中的d全部除掉再递归。质因子的数目算上重复的也不超过 ceiling(log2n) ,所以数组不用开很大。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <algorithm>
typedef long long ll;
const int s = 10, MAX_F = 70;
ll cnt, f[MAX_F];inline ll mul_mod(ll a, ll b, ll m)
{ll c = a*b-(ll)((long double)a*b/m+0.5)*m;return c<0 ? c+m : c;
}ll fast_exp(ll a, ll x, ll m)
{ll b = 1;while (x) {if (x & 1)b = mul_mod(b, a, m);a = mul_mod(a, a, m);x >>= 1;}return b;
}bool MR(ll n)
{if (!(n&1))return n == 2;ll t = 0, u;for (u = n-1; !(u&1); u >>= 1)++t;for (int i = 0; i < s; ++i) {ll a = rand()%(n-2)+2, x = fast_exp(a, u, n);for (ll j = 0, y; x != 1 && j < t; ++j, x = y) {y = mul_mod(x, x, n);if (y == 1 && x != n-1)return false;}if (x != 1)return false;}return true;
}inline ll abs(ll x)
{return x<0 ? -x : x;
}ll gcd(ll a, ll b)
{return b ? gcd(b, a%b) : a;
}ll PR(ll n, ll a)
{ll x = rand()%n, y = x, k = 1, i = 0, d = 1;while (d == 1) {if ((x = (mul_mod(x, x, n)+a)%n) == y)return n;d = gcd(n, abs(y-x));if (++i == k) {k <<= 1;y = x;}}return d;
}void decomp(ll n)
{if (n == 1)return;if (MR(n)) {f[cnt++] = n;return;}ll d = n, c = n-1;while (d == n)d = PR(n, c--);do {n /= d;} while (!(n%d));decomp(d);decomp(n);
}int main()
{srand(time(0));ll n;while (scanf("%lld", &n), n) {cnt = 0;decomp(n);std::sort(f, f+cnt);cnt = std::unique(f, f+cnt)-f;ll ans = n;for (int i = 0; i < cnt; ++i) {printf("%lld\n", f[i]);ans = ans/f[i]*(f[i]-1);}printf("%lld\n", ans);}return 0;
}

这篇关于Pollard的rho启发式因子分解算法 [CodeVS 4939] 欧拉函数:Miller-Rabin + Pollard-rho 质因数分解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/249430

相关文章

PyTorch中cdist和sum函数使用示例详解

《PyTorch中cdist和sum函数使用示例详解》torch.cdist是PyTorch中用于计算**两个张量之间的成对距离(pairwisedistance)**的函数,常用于点云处理、图神经网... 目录基本语法输出示例1. 简单的 2D 欧几里得距离2. 批量形式(3D Tensor)3. 使用不

MySQL 字符串截取函数及用法详解

《MySQL字符串截取函数及用法详解》在MySQL中,字符串截取是常见的操作,主要用于从字符串中提取特定部分,MySQL提供了多种函数来实现这一功能,包括LEFT()、RIGHT()、SUBST... 目录mysql 字符串截取函数详解RIGHT(str, length):从右侧截取指定长度的字符SUBST

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

Springboot实现推荐系统的协同过滤算法

《Springboot实现推荐系统的协同过滤算法》协同过滤算法是一种在推荐系统中广泛使用的算法,用于预测用户对物品(如商品、电影、音乐等)的偏好,从而实现个性化推荐,下面给大家介绍Springboot... 目录前言基本原理 算法分类 计算方法应用场景 代码实现 前言协同过滤算法(Collaborativ

Kotlin运算符重载函数及作用场景

《Kotlin运算符重载函数及作用场景》在Kotlin里,运算符重载函数允许为自定义类型重新定义现有的运算符(如+-…)行为,从而让自定义类型能像内置类型那样使用运算符,本文给大家介绍Kotlin运算... 目录基本语法作用场景类对象数据类型接口注意事项在 Kotlin 里,运算符重载函数允许为自定义类型重

Pandas中统计汇总可视化函数plot()的使用

《Pandas中统计汇总可视化函数plot()的使用》Pandas提供了许多强大的数据处理和分析功能,其中plot()函数就是其可视化功能的一个重要组成部分,本文主要介绍了Pandas中统计汇总可视化... 目录一、plot()函数简介二、plot()函数的基本用法三、plot()函数的参数详解四、使用pl

Python的time模块一些常用功能(各种与时间相关的函数)

《Python的time模块一些常用功能(各种与时间相关的函数)》Python的time模块提供了各种与时间相关的函数,包括获取当前时间、处理时间间隔、执行时间测量等,:本文主要介绍Python的... 目录1. 获取当前时间2. 时间格式化3. 延时执行4. 时间戳运算5. 计算代码执行时间6. 转换为指

Python正则表达式语法及re模块中的常用函数详解

《Python正则表达式语法及re模块中的常用函数详解》这篇文章主要给大家介绍了关于Python正则表达式语法及re模块中常用函数的相关资料,正则表达式是一种强大的字符串处理工具,可以用于匹配、切分、... 目录概念、作用和步骤语法re模块中的常用函数总结 概念、作用和步骤概念: 本身也是一个字符串,其中

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各