Pollard rho integer Faktorisierung

Question

Ich versuche Pollard Rho integer Faktorisierung in C / C ++. Google gibt mir eine Java-Implementierung des Problems hier .

Ich weiß nicht, Java, das gut, so was ich kam mit dieser .My Implemenation in C ++ Arbeiten für die meisten Fälle aber nicht in wenigen wie die „9999“, habe ich es.

Ich bin mir bewusst, dass C ++ nicht BigInteger Klasse hat, damit ich nicht die volle Funktionalität haben kann, wie es in JAVA gibt, aber ich mag 15 Ziffern Zahlen faktorisieren, die für unsigned long long ausreichend ist

Bitte weist darauf hin, was falsch in meiner Implementierung.

Answer 1

Das Problem ist hier:

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

Sie fehlen einige Klammern in Ihrem abs Makro. Versuchen Sie:

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

statt. (Überlegen Sie, was passiert, wenn abs(x-xx) im Fall x-xx <= 0 klappt.)

Auch, warum hat Ihre GCD-Funktion einen int zurückgeben eher als ein BigInteger?

Sie sollten sich auch bewusst sein, dass (vorausgesetzt, dass unsigned long long ist ein 64-Bit-Integer-Typ) Dieser Code wird für N größer als 2**32 nicht korrekt funktionieren: Wenn x (oder xx) größer als oder gleich dann 2**32 x*x wird Modulo 2**64 wickeln Sie den falschen Wert für x*x % N geben.

Answer 2

Ich habe spotted einen Unterschied: die Java-Code Abtretungs c und x new BigInteger(N.bitLength(), random), während der C ++ Code Verwendungen rand() % N zu sein, was ein kleiner Zufallsbereich ist. Für den Wert 9999, ist die binäre 10011100001111, so wird der Java-Code c geben und einen Maximalwert von 16383 x.