Целочисленная факторизация Полларда Ро

Question

Я пытаюсь реализовать целочисленную факторизацию Полларда Ро в 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 возвращает int, а не BigInteger?

Вы также должны знать, что (при условии, что unsigned long long является 64-битным целочисленным типом) этот код не будет работать правильно для N больше, чем 2**32:если x (или xx) Больше или равно 2**32 затем x*x обернем по модулю 2**64, давая вам неправильное значение для x*x % N.

Answer 2

Я заметил одно отличие:код Java назначает c и x быть new BigInteger(N.bitLength(), random), тогда как код C++ использует rand() % N, что представляет собой меньший случайный диапазон.Для значения 9999 двоичный код равен 10011100001111, поэтому код Java выдаст c и x максимальное значение 16383.