当前位置：网站首页>【数论】素数（四）：数的分解（Pollard-rho）

【数论】素数（四）：数的分解（Pollard-rho）

2022-04-22 06:13:00 【default111】

我的数论-素数部分博客共5part：
基本概念、性质、猜想、定理
素数筛法（埃式筛、欧拉筛、区间筛）
素数判断法（朴素法、模6法、Rabin-Miller及改进）
数的分解（Pollard-rho）
梅森素数（Lucas_Lehmer判定法）

数的分解

普通整数分解

  • 枚举因子试除
  • 素数打表试除

大整数分解：Pollard-rho

本质：随机因子检查

Pollard的伪随机数生成器： f ( x ) = ( x 2 + c ) m o d    N f(x)=(x^2+c)\mod N f(x)=(x2+c)modN ，随机数序列： { x , f ( x ) , f ( f ( x ) ) ⋯   } \{x,f(x),f(f(x))\cdots\} { x,f(x),f(f(x))⋯} 。可以修改参数打表画图得到，这个序列会进入循环，常类似 ρ \rho ρ 型，即经过一些数才进入循环

（这是kuangbin的模板）

ll factor[100]; //质因素分解结果（刚返回时时无序的）
int tol;        //质因素的个数，编号 0∼tol-1
//找出一个因子
ll pollard_rho(ll x, ll c)
{
    
    ll i = 1, k = 2;
    srand(time(NULL));
    ll x0 = rand() % (x - 1) + 1;
    ll y = x0;
    while (1)
    {
    
        i++;
        x0 = (multi_add(x0, x0, x) + c) % x;
        ll d = __gcd(y - x0, x);
        if (d != 1 && d != x)
            return d;
        if (y == x0)
            return x;
        if (i == k)
        {
    
            y = x0;
            k += k;
        }
    }
}
//对 n 进行素因子分解，存入 factor; k 设置为 107 左右即可
void findfac(ll n, int k)
{
    
    if (n == 1)
        return;
    if (Miller_Rabin(n))
    {
    
        factor[tol++] = n;
        return;
    }
    ll p = n;
    int c = k;
    while (p >= n)
        p = pollard_rho(p, c--); //值变化，防止死循环 k findfac(p,k);
    findfac(p, k);
    findfac(n / p, k);
}

版权声明
本文为[default111]所创，转载请带上原文链接，感谢
https://blog.csdn.net/default012/article/details/123299940

边栏推荐

猜你喜欢

随机推荐