Библиотека Bignum, генератор медленных простых чисел

Question

Я занимаюсь разработкой библиотеки bignum: http://pastebin.com/nFgF3zjW Я реализовал алгоритм Миллера-Рабина (isprime()), но он очень медленный по сравнению, например, с BSS_Nis_prime_fasttest OpenSSL.

Я пыталсяпрофилирование и функции, которые выполняются чаще всего: bn_shr_atomic и bn_cmp.Любая идея, как я могу сделать это быстрее?

Answer 1

Библиотека GNU Multiple Precision реализует Миллера-Рабина.Его документация находится здесь:

http://gmplib.org/manual/Number-Theoretic-Functions.html#Number-Theoretic-Functions

Я бы посоветовал проверить их реализацию на предмет указателей на ускорение ваших вычислений.Однако арифметика произвольной точности по своей природе будет медленнее, чем работа с числами, которые помещаются в регистры.

Редактировать:

Существует также компромисс между используемым алгоритмом и качествомрезультирующая вероятность.Тем не менее, я не уверен, какой тест использует OpenSSL.

Answer 2

Большое предположение: если вы действительно хотите использовать свою собственную библиотеку, я бы сначала заменил алгоритм деления на длинное деление.

Чтобы подтвердить мои предположения: у вас есть cmp и shr во внутреннем цикле вашего подразделения, являются ли эти вызовы основным вкладчиком в вашем профиле или они приходят откуда-то еще? В общем, когда вы профилируете, вы должны сначала взглянуть на функции более высокого уровня, которые вносят большой вклад, и изменение там алгоритмов обычно более полезно, чем настройка функций низкого уровня.