Pollard rho fattorizzazione di interi
-
21-09-2019 - |
Domanda
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.
Soluzione
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
.
Altri suggerimenti
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.