Каковы типичные сроки выполнения теста на примитивность Миллера-Рабина? - PullRequest
Новая
       0

Каковы типичные сроки выполнения теста на примитивность Миллера-Рабина?

4 голосов
/ 26 июля 2010

Мне хорошо известно, что один тест Миллера-Рабина выполняется за кубическое время. Я знаю о модульном возведении в степень Монтгомери и GNFS, и я не спрашиваю ни о какой из этой причудливой теории. Что меня интересует, так это то, что некоторые репрезентативные среды выполнения для MR (обратите внимание, что это не то же самое, что операция RSA) на характерном оборудовании (например, 2,2 ГГц Opteron или такая-то графическая карта или FPGA).

Ответы [ 2 ]

3 голосов
/ 23 апреля 2014

Один случайный базовый тест Миллера-Рабина, реализованный в GMP, среднее из нескольких простых чисел и нескольких прогонов.i4770K @ 4,3 ГГц, GMP 6.0.0a.Для чисел под 64-битными времена могут быть быстрее с использованием не-GMP реализации (с x86_64 asm mulmod).Эта реализация, похоже, следует большинству других реализаций C + GMP достаточно близко по производительности (для тех же чисел, mpz_sprp mpz_aprcl работает в паре процентов времени ниже).Использование нестандартных вызовов API для выполнения математики Монтгомери может быть быстрее (а может и нет).

  • 20 цифр: 1,1 сШ
  • 40 цифр: 3,4 сС
  • 80 цифр: 14 сШ
  • 200 цифр: 0,11 мС
  • 400 цифр: 0,65 мС
  • 800 цифр: 4,7 мС
  • 1200 цифр: 15 мС
  • 1600 цифр: 31 мс
  • 2000 цифр: 53 мс
  • 4000 цифр: 310 мс

При хорошей реализации, BPSW (база 2MR + [дополнительный] сильный тест Лукаса) в ~ 3 раза дороже одного МР теста.Реализация тестов Lucas значительно отличается по производительности.Тест Фробениуса стоит в 2,5 раза дороже одного МР теста.

2 голосов
/ 13 июня 2011

Один раунд теста Миллера-Рабина может занять около 1 миллисекунды;Вот интерактивная реализация на JavaScript, которую вы можете запустить в своем браузере и проверить время самостоятельно: http://www.javascripter.net/math/primes/millerrabinprimalitytest.htm

...