拉斯维加斯随机化算法求解整数因子分解

作者:神秘网友 发布时间:2020-11-20 12:03:05

拉斯维加斯随机化算法求解整数因子分解

问题描述

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

下面算法split(n)可以对整数因子分割:

int Split(int n)
{
    int m = floor(sqrt(double(n)));
    for (int i=2; i<=m; i++)
    {
        if (n%i==0)
        {
            return i;
        }
    }
    return 1;
}
View Code

算法split(n)是对范围在1~x的所有整数进行了试除而得到范围在1~x^2的任一整数的因子分割。 

 Pollard p - 1 方法由Pollard 于1974 年提出,用来找到给定合数n的一个因子d。Pollard算法用于Split(n)相同工作量就可以得到在1~x^4范围内整数的因子分割。具体过程如下:在开始时选取0~n-1范围内的随机数,然后递归地由
产生无穷序列对于i=2^k,k=0,1,.....以及2^k<j<=2^(k+1),算法计算出xj-xi与n的最大公因子d=gcd(xj-xi,n)。如果d是n的非平凡因子,则实现对n的一次分割,算法输出n的因子d。

     算法具体实现如下:其中gcd(a,b)是求两个整数最大公因素的欧几里得算法。

//随机化算法 拉斯维加斯算法 因子分割问题
#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;
}
View Code
#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);
}
View Code

运行结果:

 对Pollard算法更深入的分析可知,执行算法的while循环约次后,Pollard算法会输出n的一个因子p。由于n的最小素因子,故Pollard算法可在O(n^(1/4))时间内找到n的一个素因子。在上述Polllard算法中还可将产生序列Xi的递归式改作

Xi=(Xi-1^2-c)mod n,其中,c是一个不等于0和2的整数。

参考文献:王晓东《算法设计与分析》第二版

                  https://blog.csdn.net/liufeng_king/article/details/9246821

拉斯维加斯随机化算法求解整数因子分解相关教程

  1. 设计一个求解n皇后问题的拉斯维加斯型概率算法

    设计一个求解n皇后问题的拉斯维加斯型概率算法 #include stdio.h#include stdlib.h//包含产生随机数的库函数 #include time.h#define N 20//最多皇后个数 int q[N];//(i.q[i])为皇后所在坐标,q[i]是皇后所在列号 int num = 0;//拉斯维加斯型概率算法总会存在

  2. 如何在PHP中随机播放/随机化数组

    如何在PHP中随机播放/随机化数组 There are different ways to randomly select elements of an array in PHP. But recurring elements are biggest problem most of them. Here the clean and PHP library supported solution for this. We will use shuffle

  3. 从另一个角度看拉普拉斯变换

    从另一个角度看拉普拉斯变换 从另一个角度看拉普拉斯变换 J Pan 航空工程师 一、奥列弗. 赫维赛德是何许人也 二、傅里叶变换(轻量版拉普拉斯变换) 三、拉普拉斯变换(原来就是那么回事) 拉普拉斯变换可以说是现代工程学使用最广泛的数学工具,它通过数学变

  4. 传递函数拉普拉斯变换的方便理解

    传递函数、拉普拉斯变换的方便理解 拉普拉斯变换的重大意义 将时域的卷积运算转为到复频域(S域)的乘积运算。因为拉普拉斯变换包含傅里叶变换,比傅里叶变换应用范围更广,所以转换一般转为S域内进行卷积,后将结果反变换回时域。以一次变换的开销换取整个

  5. 图像增强之拉普拉斯算子的锐化处理

    图像增强之拉普拉斯算子的锐化处理 一、前述 在大致了解图像增强之拉普拉斯算子对图像的细节具有增强作用后(尤其是点、细线或线端点的增强),基于matlab编写脚本来实现掩模运算。本博客不具体介绍原理,具体可自行科普。 二、思路与实现 由于拉普拉斯算子对

  6. 高斯金字塔与拉普拉斯金字塔(python实现)

    高斯金字塔与拉普拉斯金字塔(python实现) 一、高斯金字塔: 高斯金子塔的思路非常简单,就是将原始图像当作金子塔的最底层,然后进行按图像长宽各减少二分之一,面积减少四分之一,进行下采样。在进行下采样之前需要进行高斯滤波。 import numpy as npimpor

  7. 高斯金字塔与拉普拉斯金字塔的原理与python构建

    高斯金字塔与拉普拉斯金字塔的原理与python构建 转载自:https://zhuanlan.zhihu.com/p/94014493 高斯金字塔和拉普拉斯金字塔【1】在图像相关领域应用广泛,尤其是图像融合和图像分割方面。本文从理论和opencv实现两个方面对两种金字塔进行了介绍,并给出了二

  8. 使用OpenCV进行模糊检测(拉普拉斯算子)

    使用OpenCV进行模糊检测(拉普拉斯算子) 点击上方“3D视觉工坊”,选择“星标” 干货第一时间送达 来源:Opencv视觉实践 本文翻译自光头哥哥的博客:【Blur detection with OpenCV】。 本文仅作学习分享,原文链接: https://www.pyimagesearch.com/2015/09/