Pollard's Rho Method

暇つぶしにKnuth先生のThe Art of（以下略）を読んでいたら、良い感じのアルゴリズムを見つけたので実装してました。

Pollard's Rho Methodは素因数分解をする高速なアルゴリズム。とりあえず理論は後回しにして、先生の言うとおりに実装したら完成しました。

走らせてみたら、これが滅茶苦茶速くて吹いた。10桁ぐらいの数でも一瞬で答えが出てきます。

これでUVaの11476 (15秒以内に10^16未満の数を800個素因数分解しなさい) が解けるぞー！と思って適当に15桁ぐらいの数を突っ込んでみたら、何故か上手くいかない。

これはもともと確率的なアルゴリズムなので失敗すること自体は不思議ではないのですが、妙に失敗率が高い。それも大きな数を入れたときに限って。

変だなーと思ってプログラムを良く見直したら、a = (a*a+1)%n という式でオーバーフローしてることが発覚しました。

さてどうしたものか。もともと long long で計算しているのでこれ以上ビット数は増やせないし、このためだけに自前のBigInteger使うのも遅くなりそうで嫌だし。
いい方法は無いものだろうか。