BelowLuminous edited 7 年,1 月前
适用范围:给你一个大数n,将它分解它的质因子的乘积的形式。
Miller-Rabin测试
费马小定理:对于素数p和任意整数a,有a^p ≡ a(mod p)(同余)。反过来,满足a^p ≡ a(mod p),p也几乎一定是素数。
伪素数:如果n是一个正整数,如果存在和n互素的正整数a满足 a^n-1 ≡ 1(mod n),我们说n是基于a的伪素数。如果一个数是伪素数,那么它几乎肯定是素数。
Miller-Rabin测试:不断选取不超过n-1的基b(s次),计算是否每次都有b^n-1 ≡ 1(mod n),若每次都成立则n是素数,否则为合数。
伪代码:
Function Miller-Rabin (n : longint) :boolean;
begin
for i := 1 to s do
begin
a := random(n - 2) + 2;
if mod_exp(a, n-1, n) <> 1 then return false;
end;
return true;
end;
大数分解最简单的思想也是试除法,这里就不再展示代码了,就是从2到sqrt(n),一个一个的试验,直到除到1或者循环完,最后判断一下是否已经除到1了即可。
但是这样的做的复杂度是相当高的。一种很妙的思路是找到一个因子(不一定是质因子),然后再一路分解下去。这就是基于Miller_rabin的大数分解法Pollard_rho 大数分解。
Pollard_rho算法的大致流程是 先判断当前数是否是素数(Miller_rabin)了,如果是则直接返回。如果不是素数的话,试图找到当前数的一个因子(可以不是质因子)。然后递归对该因子和约去这个因子的另一个因子进行分解。
那么自然的疑问就是,怎么找到当前数n的一个因子?当然不是一个一个慢慢试验,而是一种神奇的想法。其实这个找因子的过程我理解的不是非常透彻,感觉还是有一点儿试的意味,但不是盲目的枚举,而是一种随机化算法。我们假设要找的因子为p,他是随机取一个x1,由x1构造x2,使得{p可以整除x1-x2 && x1-x2不能整除n}则p=gcd(x1-x2,n),结果可能是1也可能不是1。如果不是1就找寻成功了一个因子,返回因子;如果是1就寻找失败,那么我们就要不断调整x2,具体的办法通常是x2=x2x2+c(c是自己定的)直到出现x2出现了循环==x1了表示x1选取失败重新选取x1重复上述过程。(似乎还存在一个每次找寻范围2的优化,但是不太懂。。。)
因为x1和x2再调整时最终一定会出现循环,形成一个类似希腊字母rho的形状,故因此得名。
int pollard_rho(int n, int c)///c为自己设定的某值
{
int x, y, d, i = 1, k = 2;
x = rand() % (n - 1) + 1;
y = x;
while (true) {
++i;
x = (modular_multi(x, x, n) + c) % n;
d = gcd(y - x, n);
if (1 < d && d < n)
return d;
if (x == y)
return n;
if (i == k)
y = x, k <<= 1;
}
}
大整数分解模板
const int Times = 10;
const int N = 5500;
using namespace std;
typedef long long LL;
LL ct, cnt;
LL fac[N], num[N];
LL gcd(LL a, LL b)
{
return b? gcd(b, a % b) : a;
}
LL multi(LL a, LL b, LL m)
{
LL ans = 0;
a %= m;
while(b)
{
if(b & 1)
{
ans = (ans + a) % m;
b–;
}
b >>= 1;
a = (a + a) % m;
}
return ans;
}
LL quick_mod(LL a, LL b, LL m)
{
LL ans = 1;
a %= m;
while(b)
{
if(b & 1)
{
ans = multi(ans, a, m);
b–;
}
b >>= 1;
a = multi(a, a, m);
}
return ans;
}
bool Miller_Rabin(LL n)
{
if(n == 2) return true;
if(n < 2 || !(n & 1)) return false;
LL m = n - 1;
int k = 0;
while((m & 1) == 0)
{
k++;
m >>= 1;
}
for(int i=0; i<Times; i++)
{
LL a = rand() % (n - 1) + 1;
LL x = quick_mod(a, m, n);
LL y = 0;
for(int j=0; j<k; j++)
{
y = multi(x, x, n);
if(y == 1 && x != 1 && x != n - 1) return false;
x = y;
}
if(y != 1) return false;
}
return true;
}
LL pollard_rho(LL n, LL c)
{
LL i = 1, k = 2;
LL x = rand() % (n - 1) + 1;
LL y = x;
while(true)
{
i++;
x = (multi(x, x, n) + c) % n;
LL d = gcd((y - x + n) % n, n);
if(1 < d && d < n) return d;
if(y == x) return n;
if(i == k)
{
y = x;
k <<= 1;
}
}
}
void find(LL n, int c)
{
if(n == 1) return;
if(Miller_Rabin(n))
{
fac[ct++] = n;
return ;
}
LL p = n;
LL k = c;
while(p >= n) p = pollard_rho(p, c–);
find(p, k);
find(n / p, k);
}
int main()
{
LL n;
while(cin>>n)
{
ct = 0;
find(n, 120);
sort(fac, fac + ct);
num[0] = 1;
int k = 1;
for(int i=1; i<ct; i++)
{
if(fac[i] == fac[i-1])
++num[k-1];
else
{
num[k] = 1;
fac[k++] = fac[i];
}
}
cnt = k;
for(int i=0; i<cnt; i++)
cout<<fac[i]<<”^”<<num[i]<<” “;
cout<<endl;
}
return 0;
}
为什么这些程序没有缩进,我在写blog的时候明明还是有缩进的啊。