63
правки
Изменения
→Алгоритм
====Алгоритм====
Нам нужен детерминированный алгоритм работающий за <tex>p(\log|n|)</tex>, где <tex>p</tex> {{---}} полином. Однако не существует такого эффективного алгоритма. Однако существует эффективный рандомизированный алгоритм.
Формально, нам нужно проверить принадлежит ли число языку <tex>PRIMES = \{ \llcorner N \lrcorner : N -</tex> простое <tex>\}</tex>.Для каждого <tex>N</tex> и <tex>A \in [N - 1]</tex>, определим: <tex> QR_N(A) = \begin{cases} 0 & gcd(A, N) \ne 1\\ +1 & A = B^2 (mod N), gcd(B, N) = 1\\ - 1, & \text{otherwise}\end{cases}</tex>
===Проверка двудольного графа на существование в нем полного паросочетания===
