Pollard's rho algorithm

最近Pollardのρアルゴリズムという素因数分解アルゴリズムを知った。wikipedia:en:Pollard's rho algorithm

今、自然数nの約数を見つけたいとする。数列をで定義する。数列はmod pでだいたいぐらいのオーダーでサイクルに入る。よって、をpで割った余りをi=1から順に計算していくと、回目ぐらいで、余りが0になる。

という事実をうまく使う方法らしい。この方法では約数pをぐらいの計算時間で見つけてくれる。
pythonでのサンプルプログラム

def gcd(m,n):
    while 1:
        if n==0:
            return m
        m,n=n,m%n

def f(n):
    return n*n+1

def pollard_rho_factorization(n):
    a=b=2
    while 1:
        a=f(a)%n
        b=f(f(b))%n
        if gcd(a-b,n)!=1:
            return gcd(a-b,n)

n=7479057567604083022181         #=383590706329*19497494189
print pollard_rho_factorization(n)