BelowLuminous edited 7 年，5 月前
适用范围：给你一个大数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的时候明明还是有缩进的啊。