63
правки
Изменения
→Алгоритм
====Алгоритм====
Нам нужен детерминированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Хоть и не существует такого эффективного детерминированного алгоритма, существует эффективный рандомизированный алгоритм.
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>. Для каждого <tex>N</tex> и <tex>A \in [1 .. N - 1]</tex>, определим:
