Пример 1. Алгоритм Монте-Карло проверки числа на простоту

Алгоритмы Монте-Карло.

В алгоритме Монте-Карло случайным образом выбираются некоторые значения и с этими значениями производятся вычисления.

Алгоритмы Монте Карло всегда выдают какие-либо результаты, однако вероятность того, что результат правильный, возрастает при увеличении времени работы алгоритма. Иногда такие алгоритмы возвращают неправильные ответы.

Алгоритм называется р-правильным, если он возвращает правильный ответ с вероятностью р (1/2 <р <1).

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

Результаты алгоритма Монте-Карло можно улучшить двумя способами. Во-первых, можно увеличить время его работы. Во-вторых, можно повторять его несколько раз. Вторая возможность реализуется только, если алгоритм стойкий. В этом случае алгоритм можно вызывать много раз и выбирать тот ответ, который встречается чаще всего.

Задача проверки простоты числа - пример задачи, которую относили к классу NP. Лишь в 2002 г. был найден полиномиальный алгоритм и тем самым, доказано, что задача относится к классу Р. Тест Агравала — Каяла — Саксены (или тест AKS) — это полиномиальный детерминированный тест простоты чисел, предложенный индийскими учёным Маниндрой Агравалом (англ.) и его двумя студентам. Однако сложность предложенного алгоритма , (n – тестируемое число), поэтому на практике он практически не используется. В настоящее время разрабатываются модификации теста с меньшей сложностью.

Задача факторизации натурального числа – разложения на простые множители является более сложной задачей. На настоящий момент неизвестны полиномиальные алгоритмы факторизации чисел, хотя и не доказано, что таких алгоритмов не существует. На сегодняшний момент задача относится к классу NP. На предполагаемой большой вычислительной сложности задачи факторизации базируется криптосистема RSA и некоторые другие. Факторизация с полиномиальной сложностью возможна на квантовом компьютере с помощью алгоритма Шора.

Детерминированный алгоритм проверки числа на простоту (экспоненциальный): Выбираем все числа от 2 до и делим n на эти числа, пока не будет найден делитель:

begin;

i:=2;

j:= true;

while (i*i < n and j) do

if (n mod I =0) then j:= false

else i:=i+1;

if j then writeln («Это простое число»)

else writeln («Это составное число»);

end;

Время работы алгоритма . Асимптотическая сложность алгоритма – экспоненциальная относительно битовой длины n.

Пример: для чисел , сложность для больших чисел .

Вероятностный метод Монте-Карло:

В этом случае мы генерируем случайное число между 2 и и проверяем, делится ли N на это число. Если да, то число N составное, в противном случае мы не можем ничего сказать.

Это не очень хороший алгоритм, потому что он возвращает отрицательны ответ слишком часто. Например, для числа 60 329, которое является произведением трех простых чисел 23, 43 и 61, алгоритм будет генерировать случайное число между 2 и 245, но только три числа из этого интервала привели бы к правильному результату. Вероятность успеха всего 1.2%.

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

Для алгоритма, основанного на методе Монте-Карло, малой теореме Ферма и Китайской теореме об остатках справедлива:

Теорема. Если - простое, то описанный выше алгоритм всегда (с вероятностью 1) выдает ответ « - простое». Если - составное, то ответ « - составное» будет получен с вероятностью .

Замечание. Чтобы получить полиномиальный вероятностный алгоритм проверки простоты числа, нужно дважды применить приведенный алгоритм, тогда вероятность ошибки будет меньше 1/4.

Дата добавления: 2014-01-03