【快速因數分解】Pollard's Rho 算法

算法目的

給一個數n，快速提取n的一個因數。

算法根據：生日悖論

講生日悖論之前，先看一個東西。

給出[1…1000]的數，從中任意選出一個數為k的機率是 1 1000 1\over 1000 10001​。

但是假如選出兩個數p,q要求他們的內插補點為k，就是|p-q|=k的機率大概是 1 500 1\over 500 5001​,因為要取絕對值。

繼續向下，選出l個數，使他們之間有兩個數的內插補點為k，那麼機率會随l的變大而變大，最終會趨近于1。

接下來是生日悖論：

我們随機選擇一名學生，他的生日為 4 月 1 日的機率為 [1…365]

這相當于我們在[1…365]中随機選取一個數，該數為 90 的機率是多少？

那麼我們又回到了上面那個問題。

我們随機選取 k(k≥ 2)個人 ，他們的生日相同的機率是多少（就是內插補點為0）？

可以直接用公式計算 p = P 365 k 36 5 n p={P_{365}^k\over{365^n}} p=365nP365k​​

通過計算

我們可以看到，k = 10 的時候大概有 11%的可能性存在兩個人生日相同的情況，

而 k = 23 時，可能性提高至50%，假如一個班級總共有57個人，而l=57時的可能性已達到99%，幾乎可以肯定地說，一個班級裡必定有兩個同學的出生日期是相同的，而這麼多年的求學生涯過來了，這個機率“似乎”是不正确的，這便是悖論了（這個被稱為悖論的原因也是因為人為直覺感覺的機率和實際機率不同）。

Pollard’s Rho 算法

那麼竟然有了這個玄學的悖論，我們就可以随機的快速分解n了,2333。

有一個随機函數f(x)=(x*x+d)%n，d=rand()。然後每次随機出來的數和上一次随機出來的數的內插補點與n去一個最大公因數，然後判斷一下就好了。

但是假如一直找不到符合的數然後死循環了怎麼辦。

我們可以用Floyd發明的機智判環算法，因為我每次a=f(a)，再找一個b=f(f(b))，如果有一個時刻a=b那麼就退出循環，因為b是以兩倍的速度走得，當b追上了a，那麼b至少已經走完一圈了。

複雜度O( n 1 4 n^{1\over 4} n41​)，看上去O(玄學)。

Code

随機函數f

ll f(ll x){
    int u=rand();
    return (cheng(x,x,n)+po)%n;
}
           

Pollard’s Rho 算法

a=0;
    b=1;
    po=rand()%n+1;
    while(1){
    	a=b=rand()%n+1;
	    while(1){
	        a=f(a);
	    	b=f(f(b));
	    	if(a==b)break;
	    	ll ui=abs(b-a);
	    	ll tt=gcd(ui,n);
	    	if(tt==1||tt==n)continue;
	    	if(tt>1){
			    p=tt;
			    break;
			}
		}  
		po--;
		if(p)break;
    }