素因子分解的Pollard Rho算法

4210

给定一个正整数 N ，并且它是复合的，找到它的一个除数。 例子：

null
Input: n = 12;Output: 2 [OR 3 OR 4]Input: n = 187;Output: 11 [OR 17]

粗暴的做法： 测试所有小于n的整数，直到找到一个除数。 即兴创作： 测试所有小于的整数√N 足够大的数量仍然意味着大量的工作。 波拉德氏Rho 是一种素因式分解算法，对于具有小素因式的大合数特别快。Rho算法最显著的成功是第八个费马数的因式分解：1238926361552897*9346163977769163558199606896584051237541638188580280321。 Rho算法是一个很好的选择，因为第一个素因子比另一个小得多。 Pollard的Rho算法中使用的概念：

  1. 如果
    1. 它们的绝对差是n的整数倍，
    2. 当它们被n除时，每一个都留下相同的余数。
  2. 这个 最大公约数 是平均分成每个原始数的最大数。
  3. 生日悖论： 即使是对一小部分人来说，两个人生日相同的概率也出人意料地高。
  4. Floyd的循环查找算法： 如果乌龟和兔子在同一点出发，在一个循环中移动，兔子的速度是乌龟速度的两倍，那么它们必须在某个点相遇。

算法 :

  1. 从随机x和c开始。取y等于x，f（x）=x 2. +c。
  2. 而除数是不存在的
    1. 将x更新为f（x）（模n）[乌龟移动]
    2. 将y更新为f（f（y））（模n）[兔子移动]
    3. 计算| x-y |和n的GCD
    4. 如果GCD不是统一的
      1. 如果GCD为n，用另一组x、y和c重复步骤2
      2. 否则GCD就是我们的答案

插图： 让我们假设一下 n=187 针对不同的随机值考虑不同的情况。

  1. 一个随机值的例子，比如 找到结果 : y=x=2，c=1，因此我们的f（x）=x 2. + 1.

PollardRho1

  1. 一个随机值的例子，比如 更快地找到结果 : y=x=110，c=183。因此，我们的f（x）=x 2. + 183.

table

  2. 一个随机值的例子，比如 找不到结果 : x=y=147，c=67。因此，我们的f（x）=x 2. + 67.

PollardRho3

下面是上述算法的C/C++实现：

C++

/* C++ program to find a prime factor of composite using
Pollard's Rho algorithm */
#include<bits/stdc++.h>
using namespace std;
/* Function to calculate (base^exponent)%modulus */
long long int modular_pow( long long int base, int exponent,
long long int modulus)
{
/* initialize result */
long long int result = 1;
while (exponent > 0)
{
/* if y is odd, multiply base with result */
if (exponent & 1)
result = (result * base) % modulus;
/* exponent = exponent/2 */
exponent = exponent >> 1;
/* base = base * base */
base = (base * base) % modulus;
}
return result;
}
/* method to return prime divisor for n */
long long int PollardRho( long long int n)
{
/* initialize random seed */
srand ( time (NULL));
/* no prime divisor for 1 */
if (n==1) return n;
/* even number means one of the divisors is 2 */
if (n % 2 == 0) return 2;
/* we will pick from the range [2, N) */
long long int x = ( rand ()%(n-2))+2;
long long int y = x;
/* the constant in f(x).
* Algorithm can be re-run with a different c
* if it throws failure for a composite. */
long long int c = ( rand ()%(n-1))+1;
/* Initialize candidate divisor (or result) */
long long int d = 1;
/* until the prime factor isn't obtained.
If n is prime, return n */
while (d==1)
{
/* Tortoise Move: x(i+1) = f(x(i)) */
x = (modular_pow(x, 2, n) + c + n)%n;
/* Hare Move: y(i+1) = f(f(y(i))) */
y = (modular_pow(y, 2, n) + c + n)%n;
y = (modular_pow(y, 2, n) + c + n)%n;
/* check gcd of |x-y| and n */
d = __gcd( abs (x-y), n);
/* retry if the algorithm fails to find prime factor
* with chosen x and c */
if (d==n) return PollardRho(n);
}
return d;
}
/* driver function */
int main()
{
long long int n = 10967535067;
printf ( "One of the divisors for %lld is %lld." ,
n, PollardRho(n));
return 0;
} 





               










   JAVA  












                        


        


                                                     


        


                          


        


                                                                                






















                         /* Java program to find a prime factor of composite using                       


                                                 Pollard's Rho algorithm */                       


                         import                                     java.util.*;                       


           


                         class                                     GFG{                       


           


                         /* Function to calculate (base^exponent)%modulus */                       


                         static                                     long                                     modular_pow(                                     long                                     base,                                     int                                     exponent,                       


                                                 long                                     modulus)                       


                         {                       


                                                 /* initialize result */                       


                                                 long                                     result =                                     1                                     ;                       


           


                                                 while                                     (exponent >                                     0                                     )                       


                                                 {                       


                                                 /* if y is odd, multiply base with result */                       


                                                 if                                     (exponent %                                     2                                     ==                                     1                                     )                       


                                                 result = (result * base) % modulus;                       


           


                                                 /* exponent = exponent/2 */                       


                                                 exponent = exponent >>                                     1                                     ;                       


           


                                                 /* base = base * base */                       


                                                 base = (base * base) % modulus;                       


                                                 }                       


                                                 return                                     result;                       


                         }                       


           


                         /* method to return prime divisor for n */                       


                         static                                     long                                     PollardRho(                                     long                                     n)                       


                         {                       


                                                 /* initialize random seed */                       


                                                 Random rand =                                     new                                     Random();                       


           


                                                 /* no prime divisor for 1 */                       


                                                 if                                     (n ==                                     1                                     )                                     return                                     n;                       


           


                                                 /* even number means one of the divisors is 2 */                       


                                                 if                                     (n %                                     2                                     ==                                     0                                     )                                     return                                     2                                     ;                       


           


                                                 /* we will pick from the range [2, N) */                       


                                                 long                                     x = (                                     long                                     )(rand.nextLong() % (n -                                     2                                     )) +                                     2                                     ;                       


                                                 long                                     y = x;                       


           


                                                 /* the constant in f(x).                       


                                                 * Algorithm can be re-run with a different c                       


                                                 * if it throws failure for a composite. */                       


                                                 long                                     c = (                                     long                                     )(rand.nextLong()) % (n -                                     1                                     ) +                                     1                                     ;                       


           


                                                 /* Initialize candidate divisor (or result) */                       


                                                 long                                     d = 1L;                       


           


                                                 /* until the prime factor isn't obtained.                       


                                                 If n is prime, return n */                       


                                                 while                                     (d ==                                     1                                     )                       


                                                 {                       


                                                 /* Tortoise Move: x(i+1) = f(x(i)) */                       


                                                 x = (modular_pow(x,                                     2                                     , n) + c + n) % n;                       


           


                                                 /* Hare Move: y(i+1) = f(f(y(i))) */                       


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


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


           


                                                 /* check gcd of |x-y| and n */                       


                                                 d = __gcd(Math.abs(x - y), n);                       


           


                                                 /* retry if the algorithm fails to find prime factor                       


                                                 * with chosen x and c */                       


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


                                                 }                       


           


                                                 return                                     d;                       


                         }                       


                                   


                         // Recursive function to return gcd of a and b                       


                         static                                     long                                     __gcd(                                     long                                     a,                                     long                                     b)                       


                         {                       


                                                 return                                     b ==                                     0                                     ? a:__gcd(b, a % b);                       


                         }                       


           


                         /* driver function */                       


                         public                                     static                                     void                                     main(String[] args)                       


                         {                       


                                                 long                                     n = 10967535067L;                       


                                                 System.out.printf(                                     "One of the divisors for "                                     + n +                                     " is "                                     +                       


                                                 PollardRho(n));                       


                         }                       


                         }                       


           


                         // This code contributed by aashish1995                       












    






               






               










   Python3  












                        


        


                                                     


        


                          


        


                                                                                






















                         # Python 3 program to find a prime factor of composite using                       


                         # Pollard's Rho algorithm                       


                         import                                     random                       


                         import                                     math                       


           


                         # Function to calculate (base^exponent)%modulus                       


                         def                                     modular_pow(base, exponent,modulus):                       


           


                                                 # initialize result                       


                                                 result                                     =                                     1                       


           


                                                 while                                     (exponent >                                     0                                     ):                       


                                   


                                                 # if y is odd, multiply base with result                       


                                                 if                                     (exponent &                                     1                                     ):                       


                                                 result                                     =                                     (result                                     *                                     base)                                     %                                     modulus                       


           


                                                 # exponent = exponent/2                       


                                                 exponent                                     =                                     exponent >>                                     1                       


           


                                                 # base = base * base                       


                                                 base                                     =                                     (base                                     *                                     base)                                     %                                     modulus                       


                                   


                                                 return                                     result                       


           


                         # method to return prime divisor for n                       


                         def                                     PollardRho( n):                       


           


                                                 # no prime divisor for 1                       


                                                 if                                     (n                                     =                                     =                                     1                                     ):                       


                                                 return                                     n                       


           


                                                 # even number means one of the divisors is 2                       


                                                 if                                     (n                                     %                                     2                                     =                                     =                                     0                                     ):                       


                                                 return                                     2                       


           


                                                 # we will pick from the range [2, N)                       


                                                 x                                     =                                     (random.randint(                                     0                                     ,                                     2                                     )                                     %                                     (n                                     -                                     2                                     ))                       


                                                 y                                     =                                     x                       


           


                                                 # the constant in f(x).                       


                                                 # Algorithm can be re-run with a different c                       


                                                 # if it throws failure for a composite.                       


                                                 c                                     =                                     (random.randint(                                     0                                     ,                                     1                                     )                                     %                                     (n                                     -                                     1                                     ))                       


           


                                                 # Initialize candidate divisor (or result)                       


                                                 d                                     =                                     1                       


           


                                                 # until the prime factor isn't obtained.                       


                                                 # If n is prime, return n                       


                                                 while                                     (d                                     =                                     =                                     1                                     ):                       


                                   


                                                 # Tortoise Move: x(i+1) = f(x(i))                       


                                                 x                                     =                                     (modular_pow(x,                                     2                                     , n)                                     +                                     c                                     +                                     n)                                     %                                     n                       


           


                                                 # Hare Move: y(i+1) = f(f(y(i)))                       


                                                 y                                     =                                     (modular_pow(y,                                     2                                     , n)                                     +                                     c                                     +                                     n)                                     %                                     n                       


                                                 y                                     =                                     (modular_pow(y,                                     2                                     , n)                                     +                                     c                                     +                                     n)                                     %                                     n                       


           


                                                 # check gcd of |x-y| and n                       


                                                 d                                     =                                     math.gcd(                                     abs                                     (x                                     -                                     y), n)                       


           


                                                 # retry if the algorithm fails to find prime factor                       


                                                 # with chosen x and c                       


                                                 if                                     (d                                     =                                     =                                     n):                       


                                                 return                                     PollardRho(n)                       


                                   


                                                 return                                     d                       


           


                         # Driver function                       


                         if                                     __name__                                     =                                     =                                     "__main__"                                     :                       


           


                                                 n                                     =                                     10967535067                       


                                                 print                                     (                                     "One of the divisors for"                                     , n ,                                     "is "                                     ,PollardRho(n))                       


                                   


                         # This code is contributed by chitranayal                       












    






               






               










   C#  












                        


        


                                                     


        


                          


        


                                                                                






















                         /* C# program to find a prime factor of composite using                       


                                                 Pollard's Rho algorithm */                       


                         using                                     System;                       


                         class                                     GFG                       


                         {                       


           


                         /* Function to calculate (base^exponent)%modulus */                       


                         static                                     long                                     modular_pow(                                     long                                     _base,                                     int                                     exponent,                       


                                                 long                                     modulus)                       


                         {                       


                                   


                                                 /* initialize result */                       


                                                 long                                     result = 1;                       


           


                                                 while                                     (exponent > 0)                       


                                                 {                       


                                   


                                                 /* if y is odd, multiply base with result */                       


                                                 if                                     (exponent % 2 == 1)                       


                                                 result = (result * _base) % modulus;                       


           


                                                 /* exponent = exponent/2 */                       


                                                 exponent = exponent >> 1;                       


           


                                                 /* base = base * base */                       


                                                 _base = (_base * _base) % modulus;                       


                                                 }                       


                                                 return                                     result;                       


                         }                       


           


                         /* method to return prime divisor for n */                       


                         static                                     long                                     PollardRho(                                     long                                     n)                       


                         {                       


                                   


                                                 /* initialize random seed */                       


                                                 Random rand =                                     new                                     Random();                       


           


                                                 /* no prime divisor for 1 */                       


                                                 if                                     (n == 1)                                     return                                     n;                       


           


                                                 /* even number means one of the divisors is 2 */                       


                                                 if                                     (n % 2 == 0)                                     return                                     2;                       


           


                                                 /* we will pick from the range [2, N) */                       


                                                 long                                     x = (                                     long                                     )(rand.Next(0, -(                                     int                                     )n + 1));                       


                                                 long                                     y = x;                       


           


                                                 /* the constant in f(x).                       


                                                 * Algorithm can be re-run with a different c                       


                                                 * if it throws failure for a composite. */                       


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


           


                                                 /* Initialize candidate divisor (or result) */                       


                                                 long                                     d = 1L;                       


           


                                                 /* until the prime factor isn't obtained.                       


                                                 If n is prime, return n */                       


                                                 while                                     (d == 1)                       


                                                 {                       


                                   


                                                 /* Tortoise Move: x(i+1) = f(x(i)) */                       


                                                 x = (modular_pow(x, 2, n) + c + n) % n;                       


           


                                                 /* Hare Move: y(i+1) = f(f(y(i))) */                       


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


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


           


                                                 /* check gcd of |x-y| and n */                       


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


           


                                                 /* retry if the algorithm fails to find prime factor                       


                                                 * with chosen x and c */                       


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


                                                 }                       


           


                                                 return                                     d;                       


                         }                       


                                   


                         // Recursive function to return gcd of a and b                       


                         static                                     long                                     __gcd(                                     long                                     a,                                     long                                     b)                       


                         {                       


                                                 return                                     b == 0 ? a:__gcd(b, a % b);                       


                         }                       


           


                         /* Driver code */                       


                         public                                     static                                     void                                     Main(String[] args)                       


                         {                       


                                                 long                                     n = 10967535067L;                       


                                                 Console.Write(                                     "One of the divisors for "                                     + n +                                     " is "                                     +                       


                                                 PollardRho(n));                       


                         }                       


                         }                       


           


                         // This code is contributed by aashish1995                       












    






               






               










   Javascript  












                        


        


                                                     


        


                          


        


                                                                                






















                         <script>                       


           


                         /* Javascript program to find a prime factor of composite using                       


                                                 Pollard's Rho algorithm */                       


                                   


                                                 /* Function to calculate (base^exponent)%modulus */                       


                                                 function                                     modular_pow(base,exponent,modulus)                       


                                                 {                       


                                                 /* initialize result */                       


                                                 let  result = 1;                       


                                   


                                                 while                                     (exponent > 0)                       


                                                 {                       


                                                 /* if y is odd, multiply base with result */                       


                                                 if                                     (exponent % 2 == 1)                       


                                                 result = (result * base) % modulus;                       


                                   


                                                 /* exponent = exponent/2 */                       


                                                 exponent = exponent >> 1;                       


                                   


                                                 /* base = base * base */                       


                                                 base = (base * base) % modulus;                       


                                                 }                       


                                                 return                                     result;                       


                                                 }                       


                                   


                                                 /* method to return prime divisor for n */                       


                                                 function                                     PollardRho(n)                       


                                                 {                       


                                                 /* no prime divisor for 1 */                       


                                                 if                                     (n == 1)                       


                                                 return                                     n;                       


                                   


                                                 /* even number means one of the divisors is 2 */                       


                                                 if                                     (n % 2 == 0)                       


                                                 return                                     2;                       


                                   


                                                 /* we will pick from the range [2, N) */                       


                                                 let x=(Math.floor(Math.random() * (-n + 1) ));                       


                                                 let y = x;                       


                                   


                                                 /* the constant in f(x).                       


                                                 * Algorithm can be re-run with a different c                       


                                                 * if it throws failure for a composite. */                       


                                                 let c= (Math.floor(Math.random() * (-n + 1)));                       


                                   


                                                 /* Initialize candidate divisor (or result) */                       


                                                 let d=1;                       


                                                 /* until the prime factor isn't obtained.                       


                                                 If n is prime, return n */                       


                                                 while                                     (d == 1)                       


                                                 {                       


                                                 /* Tortoise Move: x(i+1) = f(x(i)) */                       


                                                 x = (modular_pow(x, 2, n) + c + n) % n;                       


                                   


                                                 /* Hare Move: y(i+1) = f(f(y(i))) */                       


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


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


                                   


                                                 /* check gcd of |x-y| and n */                       


                                                 d = __gcd(Math.abs(x - y), n);                       


                                   


                                                 /* retry if the algorithm fails to find prime factor                       


                                                 * with chosen x and c */                       


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


                                                 }                       


                                   


                                                 return                                     d;                       


                                                 }                       


                                   


                                                 // Recursive function to return gcd of a and b                       


                                                 function                                     __gcd(a,b)                       


                                                 {                       


                                                 return                                     b == 0? a:__gcd(b, a % b);                       


                                                 }                       


                                   


                                                 /* driver function */                       


                                                 let n = 10967535067;                       


                                                 document.write(                                     "One of the divisors for "                                     + n +                                     " is "                                     +                       


                                                 PollardRho(n));                       


                                   


                                   


                                                 //  This code is contributed by avanitrachhadiya2155                       


                                   


                         </script>                       












    






               






               












     输出：   


One of the divisors for 10967535067 is 104729


     这是怎么回事？      允许     n是复合（非素数）    因为n是复合的，所以它有一个非平凡的因子     F       f<=√N    .      现在假设我们必须从[0，n-1]范围内选择两个数字x和y。我们得到x=y模n的唯一时间是当x和y相同时。然而，由于f   生日悖论    ).      首先，我们从集合{0，1，…，n-1}中随机选择x并替换，以形成序列s       1.      s       2.      s       3.      …定义       &萨库特；         我        =s         我        模f      ，我们的序列现在有了每个&sacute；       我      属于{0，1，…，f-1}。因为这两个集合都是有限的，最终这两个集合中都会有一个重复的整数。我们希望在&sacute；       我      ，因为f            现在，说吧&sacute；       我      =&sacute；       J      因为我≠ j、 那么，s       我      =s       J      模d，因此，|s       我      –s       J      |将是f的倍数。根据上述假设，n也是f的倍数。这意味着| s的GCD       我      –s       J      |n是f的正整数倍，也是       候选除数d！      这里的问题是，我们只知道n必须有一个除数，我们甚至不关心它的值。一旦我们撞上       我      和s       J      （我们最后的x和y）然后序列中的每个元素都以s开头       我      将与从s开始的序列中的相应元素的模f全等       J      ，从而形成一个循环。如果我们绘制序列s       我      ，我们将观察希腊字母Rho（ρ）的形状。      Rho算法的核心是提取随机值并评估GCD。为了减少成本高昂的GCD计算，我们可以用弗洛伊德的周期检测实现波拉德的Rho（这可以用乌龟-兔子类比来理解，乌龟一次一个地通过每个元素，兔子从同一点开始，但速度是乌龟的两倍）。我们将有一些多项式f（x），从随机x开始       0      Y       0      =x       0      ，然后计算x       i+1      =f（x）       我      )还有y       i+1      =f（f（y）       我      )). 由于我们对d了解不多，多项式的一个典型选择是f（x）=x       2.      +c（模n）（是的，’c’       也可以随机选择      ).          注：         


    

  1.    算法将无限期地运行素数。  
    2. 

  2.    该算法可能无法找到因子并返回复合n的失败。在这种情况下，我们使用不同的x、y和c集，然后重试。  
    3. 

  3.    上述算法只找到一个除数。为了找到主要因素，我们可以       递归分解      除数d，d和n/d的运行算法。循环长度通常为√D  
    4. 



     时间复杂性分析：      该算法在运行时间和找到因子的概率之间进行权衡。素数因子的概率约为0.5，单位为O(√d） <=O（n）     1/4    )迭代。这是一个启发性的主张，对算法的严格分析仍然是开放的。    本文由     亚什·瓦里亚尼    。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论   


 


                    

        
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
技术文章
    

    
喜欢就支持一下吧
点赞10
        分享

        

            

                
                
CPPKU的头像-yiteyi-C++库

                
            

            
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因-yiteyi-C++库
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp line:925的原因
VS调试报错：f:\dd\vctools\vc7libs\ship\atlmfc\src\occcont.cpp li...
8年前 2.6W+
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案
7年前 9287
Easylogging++入门教程（三）Easylogging++ 配置-yiteyi-C++库
Easylogging++入门教程（三）Easylogging++ 配置
Easylogging++入门教程（三）Easylogging++ 配置
9年前 9054
常见的小波基函数有哪些？如何选择合适的小波基函数？-yiteyi-C++库
常见的小波基函数有哪些？如何选择合适的小波基函数？
常见的小波基函数有哪些？如何选择合适的小波基函数？
8年前 8484
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？-yiteyi-C++库
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
TiXmlDocument变量LoadFile()加载XML文档失败的原因有哪些？
10年前 6675
Easylogging++入门教程（一）Easylogging++日志库简介-yiteyi-C++库
Easylogging++入门教程（一）Easylogging++日志库简介
Easylogging++入门教程（一）Easylogging++日志库简介
9年前 6608

        

    
    

        
    



            

                
相关推荐

            
ISRO | ISRO CS 2017 |问题6-yiteyi-C++库
ISRO | ISRO CS 2017 |问题6
ISRO | ISRO CS 2017 |问题6
3年前 466
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）-yiteyi-C++库
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
比特屏蔽和动态编程|集1（计算方法，为每个人分配唯一的上限）
3年前 284
SAP位置编码问题-yiteyi-C++库
SAP位置编码问题
SAP位置编码问题
3年前 283
2018年NSIT德里协会黑客团队Geeksforgeks-yiteyi-C++库
2018年NSIT德里协会黑客团队Geeksforgeks
2018年NSIT德里协会黑客团队Geeksforgeks
3年前 276
STD:：C++中的NExtx置换和Pype置换-yiteyi-C++库
STD:：C++中的NExtx置换和Pype置换
STD:：C++中的NExtx置换和Pype置换
3年前 275
抗锯齿线|吴小林算法-yiteyi-C++库
抗锯齿线|吴小林算法
抗锯齿线|吴小林算法
3年前 170