ポラード・ロー整数因数分解

Question

Pollard Rho の整数因数分解を C/C++ で実装しようとしています。Google で問題の Java 実装が提供されます。 ここ.

私はJavaをあまり知らないので、私が思いついたこと これC++ での私の実装はほとんどの場合に機能しますが、私がそこで使用した「9999」のようないくつかの場合には機能しません。

C++ には Biginteger クラスがないため、JAVA のような完全な機能を使用することはできませんが、十分な 15 桁の数値を因数分解したいと考えています。 unsigned long long

私の実装のどこが間違っているかを指摘してください。

Answer 1

問題はここにあります:

#define abs(x) (x>0)?(x):(-x)

括弧がいくつかありません abs 大きい。試す：

#define abs(x) ((x)>0 ? (x) : -(x))

その代わり。（次の場合に何が起こるかを考えてみましょう abs(x-xx) ケース内で展開されています x-xx <= 0.)

また、gcd 関数が BigInteger ではなく int を返すのはなぜですか?

(unsigned long long が 64 ビット整数型であると仮定すると) このコードは、次の場合には正しく機能しないことにも注意する必要があります。 N より大きい 2**32:もし x （または xx) 以上です 2**32 それから x*x モジュロをラップします 2**64, 、間違った値が与えられます x*x % N.

Answer 2

違いが 1 つ見つかりました。Java コードが割り当てる c そして x することが new BigInteger(N.bitLength(), random), 、一方、C++ コードでは rand() % N, 、これはより小さなランダム範囲です。値 9999 の場合、バイナリは 10011100001111 であるため、Java コードは次のようになります。 c そして x 最大値は 16383 です。