数论小专题——因数的分解

# 数论小专题——因数的分解

### 一、大整数质数探测 Miller_rabin算法

- $p$是质数，费马小定理 $a^{p-1}=1(mod\ p)$

- $p$是质数，$x^2=1(mod\ p)\to x=1\ or\ x=-1$

证明：$(x+1)(x-1)=0(mod\ p)$ 故$x=p-1\ or\ x=1$得证

若要判断p，先套用用费马小定理判断。

如果符合费马小定理那么就将指数$(p-1)$除以2。

如果都符合我们就认为p是质数。

取用2,3,5,7,11,13,17,19,23,29时可以准确判断$3\times 10^{18}$内质数

```c++
#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL n;
//探测底数，可以满足1e18
LL p[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
//int64内) LL p[15] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

//O(1)快速乘
LL mul(LL a, LL b, LL m) {
	LL s = a * b - (LL)((long double)a * b / m + 0.5) * m;
	return s < 0 ? s + m : s;
}

LL fpow(LL x, LL a, LL m) {
	LL ans = 1;
	while(a) {
		if(a & 1) ans = mul(ans, x, m);
		x = mul(x, x, m), a >>= 1;
	}
	return ans;
}

//探测一次
int detect(LL n, LL a) {
    if(n == a) return 1;
    if(a % n == 0) return 1;
    LL now = n - 1, lst = 1;
    if(fpow(a, now, n) != 1) 
        return 0;
    while(!(now & 1)) {
        now /= 2;
        LL p = fpow(a, now, n);
        if(lst == 1 && p != 1 && p != n - 1)
            return 0;
        lst = p;
    }
    return 1;
}

LL MR(LL n) {
	if(n < 2) return 0;
	for(int i = 0; i < 10; ++i) {
		if(!detect(n, p[i])) return 0;
	}
	return 1;
}

int main() {
	LL n;
	while(~scanf("%lld", &n))
		puts(MR(n) ? "Y" : "N");
	return 0;
}
```

### 二、大整数因数探测Pollard_Rho算法

原理：

- 正整数$n$的最大因子不超过$\sqrt{n}$，设它任意一个因子为$p$

- 若随机生成$p$以内的数，期望$\sqrt{p}$次就可以随机到两个一样的数

- 随机生成$[1,n]$的正整数，它们$mod\ p$下可近似看做在$[1,p]$内随机

- 随机生成两个数$a,b(b>a)$，若$b=a(mod\ p)\to p|(b-a)\to gcd(n, b-a)\ge p$

- 那么$gcd(n,b-a)$必为$n$的一个大于$1$的因数，根据上文，期望复杂度为$O(n^{1/4}logn)$

- 令随机数这样生成：$a_0=C,f(x)=x^2+C,a_i=f(a_{i-1})$即跳一步就套用一次$f(x)$

这样做的好处是：若$a_x=a_y(mod\ p)\to a_{x+1}-a_{y+1}=f(a_x)-f(a_y)=(a_x+a_y)(a_x-a_y)=0(mod\ p)$

即任一距离为$d$的随机数$mod\ p$相同，所有距离为$d$的随机数$mod\ p$都相同，这样只需要检查其中一个即可

- 免除记忆化：维护两个数，一个数每次调用两次$f$，一个每次调用一次，如果走完了环，最后两个数一定会相遇。同时也枚举了所有距离。

- 优化：瓶颈在于$gcd$，可以减少取$gcd(n,|a-b|)$的次数，将所有的$|a-b|$乘起来，累计$128$次后再与$n$取$gcd$（前提是$a,b$还没有在环上相遇）复杂度约为$O(n^{1/4})$

```C++
#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL n;

namespace NT {
	LL gcd(LL a, LL b) {
		return b ? gcd(b, a % b) : a;
	}
	LL mul(LL a, LL b, LL m) {
		LL s = a * b - (LL)((long double)a * b / m + 0.5) * m;
		return s < 0 ? s + m : s;
	}
	LL fpow(LL x, LL a, LL m) {
		LL ans = 1;
		while(a) {
			if(a & 1) ans = mul(ans, x, m);
			x = mul(x, x, m), a >>= 1;
		}
		return ans;
	}
}

namespace Miller_Rabin {
	using namespace NT;
	LL p[15] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
	int detect(LL n, LL a) {
		if(n == a) return 1;
		if(a % n == 0) return 1;
		LL now = n - 1, lst = 1;
		if(fpow(a, now, n) != 1) 
			return 0;
		while(!(now & 1)) {
			now /= 2;
			LL p = fpow(a, now, n);
			if(lst == 1 && p != 1 && p != n - 1)
				return 0;
			lst = p;
		}
		return 1;
	}
	
	LL MR(LL n) {
		if(n < 2) return 0;
		for(int i = 0; i < 7; ++i) {
			if(!detect(n, p[i])) 
				return 0;
		}
		return 1;
	}
}

namespace Pollard_Rho {
	using namespace NT;
	using namespace Miller_Rabin;
	LL f(LL x, LL C, LL p) {
		return (mul(x, x, p) + C) % p;
	}
	LL Rand() {return (rand() << 15) + rand();}
	LL Randll() {return (Rand() << 31) + Rand();}
	
	LL PR(LL n) {
		if(n == 4) return 2;
		if(MR(n)) return n;
		while(1) {
			LL C = Randll() % (n - 1) + 1;
			LL s = 0, t = 0;
			LL acc = 1;
			do {
				for(int i = 1; i <= 128; ++i) {
					t = f(f(t, C, n), C, n);
					s = f(s, C, n);
					LL tmp = mul(acc, abs(t - s), n);
					if(s == t || tmp == 0)
						break;
					acc = tmp;
				}
				LL d = gcd(n, acc);
				if(d > 1) return d;
			} while(s != t);
		}
	}
	
	typedef pair<LL, int > pii;
	vector<pii > DCOMP(LL n) {
		vector<pii > ret;
		while(n != 1) {
			LL p = PR(n);
			while(!MR(p)) 
				p = PR(p);
			int c = 0;
			while(n % p == 0) n /= p, ++c;
			ret.push_back(make_pair(p, c));
		}
		return ret;
	}
}

int main() {
	srand(time(0));
	int t;
	LL n;
	cin >> t;
	while(t--) {
		cin >> n;
		auto ans = Pollard_Rho::DCOMP(n);
		sort(ans.begin(), ans.end());
		int c = 0;
		for(auto i : ans)
			c += i.second;
		printf("%d ", c);
		for(auto i : ans)
			while(i.second--) printf("%lld ", i.first);
		puts("");
	}
	return 0;
}
```

Rockdu's Blog

导航

最近发表

大佬们的友链