Проверка числа на простоту

6Существует много способов проверить простоту числа.

Перебор возможного делителя

Это основной способ проверить простоту числа за $O(\sqrt{n})$. Пусть $n$ - составное число, наименьший неединичный делитель которого равен $a$.

Утверждение. $a\le \sqrt{n}$.

Доказательство. Пусть это не так, тогда $a>\sqrt{n}$. Посмотрим на $n/a$. Это также делитель $n$, и он больше $a$, ведь не равен 1, а среди таких $a$ - наименьшее число. Тогда $a\ast (n/a)>\sqrt{n}\ast \sqrt{n}⟹n>n$, что правдой не является.

Тогда, если число $n$ составное, то оно имеет делитель, меньший $\sqrt{n}$, а значит перебрав все числа от 2 до $\sqrt{n}$ и просто проверив делимость $n$ на них, мы найдем какой-то делитель, если он существует. Это основной способ гарантировать простоту числа, все следующие тесты утверждают число простым с некоторой вероятностью, хотя и довольно большой, но не абсолютной.

Тест Миллера-Рабина на простоту числа

Тест используют факт, доказанный теоремой Эйлера:

$$a^{p-1}\mathrm{mod}p\equiv 1$$

при простом $p$ и $a<p$. Тогда пусть $p-1=2^{s}d$, где $d$ - нечетное число. Возьмем случайное $a$ от 2 до $p-1$ и проверим будет ли сравнимо по модулю $n$ с -1 хотя бы одно из чисел: $a^d$, $a^{2d}$, $a^{4d}$ $\dots$ $a^{2^{s-1}d}$, или с 1 число $a^d$. Для простого числа это будет верно при любом $a$, ведь:

$$a^{p-1}\mathrm{mod}p\equiv 1⟹a^{p-1}-1\mathrm{mod}p\equiv 0⟹(\sqrt{a^{p-1}}+1)(\sqrt{a^{p-1}}-1)\mathrm{mod}p\equiv 0$$

Из последнего равенства становится ясно, что либо $a^{2^{s-1}d}\mathrm{mod}p=1$, либо $a^{2^{s-1}d}\mathrm{mod}p=-1$. В первом случае мы можем повторить наши рассуждения и перейти к меньшей степени, а второй случай придется проверить. Если число удовлетворяет данным условиям, то оно называется свидетелем простоты. Если же число $n$ является составным, то вероятность того, что выбранное нами число окажется свидетелем простоты очевидно не превышает $\frac{\varphi (n)}{n}$, ведь это кол-во взаимнопростых с $n$ чисел, а если число не взаимнопростое, то и не сможет быть сравнимо с 1 по модулю $n$ ни в какой степени. Но по теореме Рабина было доказано, что таких чисел у составного числа не может быть более $\frac{\varphi (n)}{4}$, а значит и вероятность того, что случайное выбранное $a$ окажется свидетелем простоты составного числа не более $0,25$%. Если выбрать большое кол-во таких чисел, то можно быть статистически уверенным в простоте данного числа, но проверить его на подлинную простоту можно только за $O(\sqrt{n})$. Рекомендуют брать около ${\log }_{2}n$ чисел, чтобы при увеличении $n$ кол-во свидетелей простоты также росло.