Исследуем зависимость времени выполнения программы от количества цифр в числе. Для этого сначала сгенерируем случайные числа длинной от двух до 100 цифр (по десять каждой длинны). Далее начнем проверять числа методом Рабина-Миллера и находить среднее значение выполнения теста для каждых чисел с одинаковым количеством цифр. В результате получим данные, которые затем занесем в программу MS Excel для дальнейшей обработки и построения графика зависимости времени выполнения реализованного теста Рабина-Миллера от количества цифр в числе.

Замечание 1: все числа проходят тест Рабина-Миллера всего один раз. Это делается для того, чтобы уровнять время проверки простых и составных чисел, ведь если количество прохождений увеличить, то первый цикл пройдут не более 25% составных чисел, второй не более 6.25% и т.д. По большому счету, результат проверки в данном исследовании не имеет значения. Важно время, за которое будет найден результат.

Замечание 2: при генерации числа каждая цифра генерируется отдельно. При этом проверяется делимость полученного числа на два и на три. Делается это следующим образом: если сгенерированное число делится на два или на три, то оно увеличивается на единицу. После этого число проверяется на делимость на два и три снова, и так до тех пор, пока оно не будет делиться ни на два, ни на три. Максимально для достижения этой цели может потребоваться три инкапсуляции. Это произойдет тогда, когда число n делится на два, а число (n+1) делится на три. Тогда (n+2) делится на два, а (n+3) не делится ни на два, ни на три.

При возрастании количества проверяемых цифр, среднее время проверки увеличивается. Как видно из графика (рис.ниже) для чисел длинною от 2 до 50 цифр, график зависимости среднего времени прохождения теста Рабина-Миллера от количества цифр в числе напоминает параболу. Причем, в особенности это наблюдается для чисел длинною от 2 до 35.

На рис.3 для чисел длинною от 51 до 100 цифр, зависимость среднего времени прохождения теста Рабина-Миллера от количества цифр в числе почти линейная.

Результат заботы программы, которая генерирует и находит среднее время проверки случайных чисел длинною от 2 до 50 и от 51 до 100 цифр можно наблюдать на рис. 2 и рис. 4 соответственно.

Имея результаты зависимости среднего времени прохождения теста Рабина-Миллера от количества цифр в числе для чисел длинною от 2 до 100, можно спрогнозировать, сколько времени будет рассчитываться число длинною в 317 цифр. Для этого в Excel построим график для всех полученных чисел (от 2 до 100) и построим полиномиальную линию тренда второго порядка.

В параметрах линий тренда укажем в поле прогноз, вперед на 217 единиц. Как видно на рис.16 Excel спрогнозировал время, которое потребуется для числа длинною в 317 цифр. Также была показана формула, по которой производился прогноз.

Она имеет вид:

y = 1,2599x^2 — 8,5687x — 13,328

Где y — время, x — количество цифр.

Подставим вместо x число 317 и проверим, правильно ли Excel построил спрогнозированный график.

y = 1,2599*317^2 — 8,5687*317 — 13,328

y = 126606,0911 — 2716,2779 — 13,328

y = 123876,4852, что примерно равно 123 секунды

В примере №5 (рис.5) проверялось число, состоящее из 317 цифр. Оно было обработано за 558 секунд. Но там тест проходился 5 раз. Тогда один раз тест проходился примерно за 112 секунд. Ошибка составила 11 секунд или 10%.