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

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

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)));
?? ??? ?}

?? ?}
}