Замена BigInteger на UInt64 для простых алгоритмов факторизации, где N ‹ 2^63

У меня есть хорошее решение для Prime Factorization, реализованное в VB.Net с BigInteger с использованием обоих Алгоритмы Полларда Ро и Брента (см.: https://stackoverflow.com/a/31978350/44080)

Для N< 2^63 я считаю, что UInt64 должно быть достаточно большим и, возможно, (намного?) быстрее.

Однако мое преобразование UInt64 не выполняется в этой строке:

y = ((y^2) Mod n + c) Mod n 'fails when y^2 > UInt64.Max

Изменение этой строки на

y = CULng((CDbl(y^2) Mod n + c) Mod n)

Убивает производительность, так как преобразование типа находится в цикле.

Пожалуйста, как я могу это исправить?

Я все еще думаю, что UInt64 превзойдет BigInteger, если мы сможем обойти указанную выше проблему.

ИЗМЕНИТЬ:

Я только что нашел это: Библиотека теории чисел Dirichlet .NET, утверждает, что Int128 и Int256 превосходят .Net BigInteger.

Он даже имеет несколько оптимизированных алгоритмов факторизации простых чисел. Могли бы сэкономить мне 2 дня исследований и тестирования.


.net algorithm biginteger prime-factoring uint64
person Charles Okwuagwu    schedule 13.08.2015    source источник
comment
@WDS Еще раз спасибо за то, что указали мне на алгоритм Ро Полларда в связанном решении SO.   -  person Charles Okwuagwu    schedule 13.08.2015
comment
В принципе, вы не можете, но вы можете изменить ограничение на N, чтобы заставить его работать.   -  person harold    schedule 13.08.2015
comment
@harold, ты судишь y^2. Я надеялся, что рефакторинг алгоритма или его варианта устранит необходимость в y^2.   -  person Charles Okwuagwu    schedule 13.08.2015
comment
Вы не можете использовать double... у них нет необходимой точности. Если y равно 64 битам, то y^2 составляет до 128 бит. Не существует целочисленного типа данных 128 бит. Вы можете ограничиться факторингом чисел Int32, тогда у вас не будет никаких проблем.   -  person xanatos    schedule 13.08.2015
comment
@CharlesO теоретически возможно, что вы можете вычислить квадрат, суммируя частичные произведения, а затем вы можете модифицировать их до того, как они переполнятся, но это безумно медленно.   -  person harold    schedule 13.08.2015
comment
Если вам нужна факторизация этих больших чисел, и вы не можете позволить себе BigInteger из соображений производительности, я бы предложил переосмыслить ваше решение. Как часто происходит эта факторизация? Неужели эти Бигинты настолько плохи? Вы занимались профилированием?   -  person Borsunho    schedule 13.08.2015
comment
@harold Uint64 определенно превзошел бы BigInteger. Затем мне нужно будет протестировать N, прежде чем выбирать, какую реализацию использовать.   -  person Charles Okwuagwu    schedule 13.08.2015
comment
да. N ‹ 2^32 должно работать.   -  person harold    schedule 13.08.2015
comment
или переработать алгоритм с учетом UInt64   -  person Charles Okwuagwu    schedule 13.08.2015
comment
@CharlesO, ну нет, не совсем.   -  person harold    schedule 13.08.2015
comment
(y^2) Mod n - Я не математик, но интуиция подсказывает, что это можно как-то оптимизировать.   -  person 500 - Internal Server Error    schedule 13.08.2015

Ответы (1)


arrow_upward
1
arrow_downward

Как выполнить модульное умножение (вычислить квадрат) без переполнения:

Пока модуль хотя бы на один бит меньше максимального, решение состоит в том, чтобы разделить числа на младшие и старшие биты пополам, а затем выполнить арифметические действия по частям, что-то вроде умножения в начальной школе, где вы умножаете на на единицу, затем сдвинуть сумму и умножить на разряд десятков и т. д., за исключением того, что «цифры» — это размер квадратного корня из максимального числа, которое может быть представлено в целочисленном типе данных.

Рассмотрим пример вычисления 56 * 37 по модулю 100 с использованием 8-битной арифметики, поэтому никакая промежуточная сумма не может быть 256 или больше. Начнем с представления a = 56 = 3 * 16 + 8 и b = 37 = 2 * 16 + 5 (обратите внимание, что 16 — это квадратный корень из 256), поэтому:

a1 = 8
a2 = 3
b1 = 5
b2 = 2

Тогда четыре промежуточных продукта с их сдвигами:

p11 = 8 * 5 = 40
p12 = 8 * 2 = 16 > 32 > 64 > 128 (28) > 56
p21 = 3 * 5 = 15 > 30 > 60 > 120 (20) > 40
p22 = 3 * 2 = 6 > 12 > 24 > 48 > 96 > 192 (92) > 184 (84) > 168 (68) > 136 (36)

Мы используем двоичную арифметику, поэтому каждое число удваивается при сдвиге, принимая его по модулю 100. Произведение двух младших половин не сдвигается, произведение младшего и старшего половин сдвигается в 4 раза (поскольку log2 16 = 4), а произведение двух старших -половина числа сдвигается 8 раз. Затем суммируются промежуточные продукты, снова удаляя m каждый раз, когда промежуточная сумма превышает m:

s = 40 + 56 = 96
s = 96 + 40 = 136 (36)
s = 36 + 36 = 72

И это окончательный ответ: 56 * 37 = 2072, то есть 72 (по модулю 100).

Если m находится в пределах одного бита от максимума для целочисленного типа данных, все становится еще более запутанным; основной ответ состоит в том, чтобы разделить на три части, вычислить промежуточные продукты и рекомбинировать.

Код на Scheme см. в мой блог, а также решение на C, использующее несколько иной алгоритм.

person user448810    schedule 13.08.2015
comment
Хотя этот метод частичных произведений будет работать, он значительно замедлит вычисления. - person Charles Okwuagwu; 13.08.2015