Fator de Pollard Rho inteiro

Question

Estou tentando implementar a fatorização inteira Pollard Rho em C/C ++. O Google me dá uma implementação Java do problema aqui.

Eu não conheço Java tão bem, então o que eu inventei isto.My My Implemenation em C ++ funciona para a maioria dos casos, mas não em poucos como o "9999", eu usei lá.

Estou ciente de que o C ++ não tinha aula de Biginteger, então não posso ter a funcionalidade completa, como dá em Java, mas quero fatorar 15 dígitos números que são suficientes para unsigned long long

Por favor, aponte o que errado na minha implementação.

Answer 1

O problema está aqui:

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

Você está perdendo alguns parênteses em seu abs macro. Tentar:

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

em vez de. (Considere o que acontece quando abs(x-xx) é expandido no caso x-xx <= 0.)

Além disso, por que sua função GCD retorna um int e não um biginteger?

Você também deve estar ciente de que (assumindo que não assinam longos longos é um tipo inteiro de 64 bits), esse código não funcionará corretamente para N maior que 2**32: E se x (ou xx) é maior que ou igual a 2**32 então x*x irá embrulhar o módulo 2**64, dando a você o valor errado para x*x % N.

Answer 2

Eu vi uma diferença: o código java atribui c e x ser new BigInteger(N.bitLength(), random), enquanto o código C ++ usa rand() % N, que é uma faixa aleatória menor. Para o valor 9999, o binário é 10011100001111, então o código Java dará c e x Um valor máximo de 16383.