Pollard rho fattorizzazione di interi

Question

Sto cercando di implementare Pollard Rho fattorizzazione di interi in C / C ++. Google mi dà un'implementazione Java del problema qui .

Non so Java che bene, quindi quello che mi si avvicinò con questo .La mia implemenation in C ++ funziona per la maggior parte dei casi, ma non in pochi come quella "9999", ho usato là.

Sono consapevole che C ++ non ha avuto classe BigInteger quindi non posso avere la piena funzionalità in quanto dà in JAVA ma voglio fattorizzare numeri di 15 cifre che è sufficiente per unsigned long long

Si prega di notare che cosa di sbagliato nella mia implementazione.

Answer 1

Il problema è proprio qui:

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

Ti manca qualche parentesi nella macro abs. Prova:

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

, invece. (Consideriamo cosa accade quando abs(x-xx) viene espanso nel caso x-xx <= 0.)

Inoltre, perché la funzione GCD restituire un int piuttosto che un BigInteger?

Si dovrebbe anche essere consapevoli che (supponendo unsigned long long è di tipo intero a 64 bit) questo codice non funzionerà correttamente per N maggiore 2**32: se x (o xx) è maggiore o uguale a 2**32 poi x*x avvolgerà 2**64 modulo, dando il valore errato per x*x % N.

Answer 2

Ho notato una differenza: il codice Java assegna c e x da new BigInteger(N.bitLength(), random), mentre il codice C ++ utilizza rand() % N, che è una serie casuale più piccolo. Per il valore 9999, il binario è 10.011.100,001111 millions, in modo che il codice Java darà c e x un valore massimo di 16383.