Изменения

Перейти к: навигация, поиск

Участник:Zerogerc

50 байт убрано, 08:49, 16 мая 2017
→‎Алгоритм
Дано целое число <tex>N</tex>. Определить является ли оно простым.
====Алгоритм====
Нам нужен детерминированный Существует эффективный рандомизированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Хоть и В то время как не существует такого эффективного детерминированного алгоритма, существует эффективный рандомизированный алгоритмс такой же ассимптотикой.
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>. Предоставим алгоритм который покажет что <tex>PRIMES \in BPP</tex>. Для каждого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex>, определим символ Лежандра:
Zerogerc
63
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/60778»

Навигация