C#，因数分解（质因子分解）Pollard‘s Rho算法的源代码

2026/8/16 21:22:41 拓冰建站浏览量

因数分解（也称为质因子分解）：将一个大整数分解它的质因子之乘积的算法。

Pollard Rho算法的基本思路：先判断当前数是否是素数（质数），如果是，则直接返回。如果不是，继续找到当前数的一个因子（可以不是质因子）。然后递归对该因子和约去这个因子的另一个因子进行分解。

运行效果：

源代码：

using System;
using System.Collections;
using System.Collections.Generic;

namespace Legalsoft.Truffer.Algorithm
{
   /// <summary>
   /// 用Pollard-Rho算法求合成质数因子
   /// </summary>
   public static class Prime_Factorization
   {
       /// <summary>
       /// 随机数发生器
       /// </summary>
       private static Random rand = new Random((int)DateTime.Now.Ticks);

       /// <summary>
       /// 计算 x 幂取模
       /// </summary>
       /// <param name="x"></param>
       /// <param name="exponent"></param>
       /// <param name="modulus"></param>
       /// <returns></returns>
       private static long ModularPow(long x, int exponent, long modulus)
       {
           long result = 1;
           while (exponent > 0)
           {
               // 如果 y 是奇数！
               if ((exponent % 2) == 1)
               {
                   result = (result * x) % modulus;
               }
               exponent = (exponent >> 1);

               x = (x * x) % modulus;
           }
           return result;
       }

       /// <summary>
       /// 计算 n 的分解质因子（除）算法
       /// </summary>
       /// <param name="n"></param>
       /// <returns></returns>
       public static long PollardRho(long n)
       {
           if (n == 1)
           {
               return n;
           }
           // 偶数
           if ((n % 2) == 0)
           {
               return 2;
           }

           // 设置一个取值范围
           long x = (long)(rand.Next(0, -(int)n + 1));
           long y = x;

long c = (long)(rand.Next(1, -(int)n));

           // 初始化候选除数（或结果），直到未获得素数因子。
           long d = 1L;
           while (d == 1)
           {
               x = (ModularPow(x, 2, n) + c + n) % n;

y = (ModularPow(y, 2, n) + c + n) % n;
y = (ModularPow(y, 2, n) + c + n) % n;

d = GCD(Math.Abs(x - y), n);

               if (d == n)
               {
                   return PollardRho(n);
               }
           }

return d;
}

       public static long GCD(long a, long b)
       {
           return ((b == 0) ? a : GCD(b, (a % b)));
       }

}
}

---------------------------------------------------------------------

POWER BY 315SOFT.COM

TRUFFER.CN

using System;
using System.Collections;
using System.Collections.Generic;namespace Legalsoft.Truffer.Algorithm
{/// <summary>/// 用Pollard-Rho算法求合成质数因子/// </summary>public static class Prime_Factorization{/// <summary>/// 随机数发生器/// </summary>private static Random rand = new Random((int)DateTime.Now.Ticks);/// <summary>/// 计算 x 幂取模/// </summary>/// <param name="x"></param>/// <param name="exponent"></param>/// <param name="modulus"></param>/// <returns></returns>private static long ModularPow(long x, int exponent, long modulus){long result = 1;while (exponent > 0){// 如果 y 是奇数！if ((exponent % 2) == 1){result = (result * x) % modulus;}exponent = (exponent >> 1);x = (x * x) % modulus;}return result;}/// <summary>/// 计算 n 的分解质因子（除）算法/// </summary>/// <param name="n"></param>/// <returns></returns>public static long PollardRho(long n){if (n == 1){return n;}// 偶数if ((n % 2) == 0){return 2;}// 设置一个取值范围long x = (long)(rand.Next(0, -(int)n + 1));long y = x;long c = (long)(rand.Next(1, -(int)n));// 初始化候选除数（或结果），直到未获得素数因子。long d = 1L;while (d == 1){x = (ModularPow(x, 2, n) + c + n) % n;y = (ModularPow(y, 2, n) + c + n) % n;y = (ModularPow(y, 2, n) + c + n) % n;d = GCD(Math.Abs(x - y), n);if (d == n){return PollardRho(n);}}return d;}public static long GCD(long a, long b){return ((b == 0) ? a : GCD(b, (a % b)));}}
}

建站实战干货

C#，因数分解（质因子分解）Pollard‘s Rho算法的源代码