63
правки
Изменения
→Алгоритм
{{---}} Для каждого нечетного составного <tex>N, |\{A \in [N - 1]: gcd(N, A) = 1 \,and\,(\frac{N}{A}) = A^{\frac{N - 1}{2}}\}| \le \frac{1}{2}</tex> <tex>\,| \{A \in [N - 1]: gcd(N, A) = 1\}|</tex>
Собирая эти факты вместе, получаем просто алгоритм. Для данного <tex>N</tex> выбираем случайное число <tex>A: 1 \le A < N</tex>, если <tex>gcd(N,A) > 1</tex> или <tex>(\frac{N}{A}) \ne A^{\frac{N - 1}{2}} (mod \, N)</tex> тогда говорим что число составное, иначе говорим что оно простое. Этот алгоритм всегда скажет что число простое, если оно действительно простое. Однако если число составное, то алгоритм скажет что оно составное с вероятностью <tex> \ge \frac{1}{2}</tex>.
Заметим что повторяя этот алгоритм несколько раз можно увеличить вероятность правильного ответа.
===Проверка двудольного графа на существование в нем полного паросочетания===
