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

Question

Я пытаюсь реализовать целочисленную факторизацию Полларда Ро в C / C ++. Google дает мне Java-реализацию задачи здесь .

Я не очень хорошо знаю Java, поэтому то, что я придумал , это . Моя реализация на C ++ работает в большинстве случаев, но не в некоторых, как та, которую я использовал там "9999". 1007 *

Мне известно, что в 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?

Вы также должны знать, что (при условии, что длинная строка без знака является 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.