wizen-coder
10/5/2018 - 1:51 AM

问题描述      设n>1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式：***。其中，p1<p2<…<pk是k个素数，m1,m2,…,mk是k个正整数。如果n是一个合数，则n必有一个非平凡因子x，1<x<n，使得x可以整除n。给定一个合数n，求n的一个非平

问题描述 设n>1是一个整数。关于整数n的因子分解问题是找出n的如下形式的唯一分解式：***。其中，p1<p2<…<pk是k个素数，m1,m2,…,mk是k个正整数。如果n是一个合数，则n必有一个非平凡因子x，1<x<n，使得x可以整除n。给定一个合数n，求n的一个非平凡因子的问题称为整数n的因子分割问题。 求解思路 整数因子分解最直观的方法当数“试除法”，数论中的Mertens定理告诉我们76%的奇数都有小于100的素因子，因此对于大多数整数，“试除法”已经足够，但

Pollard.cpp
content_copyfile_download
//随机化算法 拉斯维加斯算法 因子分割问题
#include "stdafx.h"
#include "RandomNumber.h"
#include <iostream>
using namespace std;
 
//求整数a和b最大公因数的欧几里得算法
int gcd(int a,int b)
{
	if(b==0)
	{
		return a;
	}
	else
	{
		return gcd(b,a%b);
	}
}
 
//求整数n因子分割的拉斯维加斯算法
void Pollard(int n)
{
	RandomNumber rnd;
	int i = 1;
	int x = rnd.Random(n);			//随机整数
	int y = x;
	int k = 2;
 
	while(true)
	{
		i++;
		x = (x*x - 1) % n;			//x[i]=(x[i-1]^2-1) mod n
		int d = gcd(y-x,n);			//求n的非平凡因子
 
		if((d>1) && (d<n))
		{
			cout<<d<<endl;//因子分割问题：求n的[一]个非平凡因子的问题
			return;
		}
 
		if(i == k)
		{
			y = x;
			k *= 2;
		}
	}
}
 
int main()
{
	int n = 1024;
	cout<<n<<"的非平凡因子："<<endl;
	Pollard(n);
	return 0;
}
RandomNumber.h
content_copyfile_download
#include"time.h"
//随机数类
const unsigned long maxshort = 65536L;
const unsigned long multiplier = 1194211693L;
const unsigned long adder = 12345L;
 
class RandomNumber
{
	private:
		//当前种子
		unsigned long randSeed;
	public:
		RandomNumber(unsigned long s = 0);//构造函数，默认值0表示由系统自动产生种子
		unsigned short Random(unsigned long n);//产生0：n-1之间的随机整数
		double fRandom(void);//产生[0,1)之间的随机实数
};
 
RandomNumber::RandomNumber(unsigned long s)//产生种子
{
	if(s == 0)
	{
		randSeed = time(0);//用系统时间产生种子
	}
	else
	{
		randSeed = s;//由用户提供种子
	}
}
 
unsigned short RandomNumber::Random(unsigned long n)//产生0：n-1之间的随机整数
{
	randSeed = multiplier * randSeed + adder;//线性同余式
	return (unsigned short)((randSeed>>16)%n);
}
 
double RandomNumber::fRandom(void)//产生[0,1)之间的随机实数
{
	return Random(maxshort)/double(maxshort);
}