Все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют это определить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной.

Метод пробных делений

Этот метод относится к группе детерминированных методов. Пусть n Є N. Как проверить, является ли n простым? Пока не существовало необходимости генерировать большие простые числа, можно было использовать методы проверки, которые достаточно легко реализуемы без применения вычислительной техники и не требуют больших усилий для проверки маленьких чисел. Первым из таких методов является, естественно, полный перебор всех возможных делителей. Чаще всего используют модификацию такого перебора, называемую пробным делением (trial division): чтобы проверить число на простоту, делим его на все простые меньше либо равные корню из этого числа. Если n—составное, то n =ab, где , причем . Поэтому для d = 2, 3, . . ., [] следует проверить, делится ли n на d? Если делитель числа n не будет найден, то n—простое. В противном случае будет найден минимальный простой делитель числа n, т.е. мы даже разложим n на два множителя. Сложность метода составляет C*n1/2 арифметических операций с целыми числами.

В одиночку метод пробных делений не используется из-за большой вычислительной сложности. Пробное деление на маленькие простые числа используется как один из шагов во многих тестах.

Возможны модификации этого метода, которые работают быстрее. Например, мы можем проверить, делится ли n на 2 и на 3 , и если нет, то перебираем далее только числа d вида 1 + 6j и 5+ 6j, j =1, 2, … Сложность метода отличается от предыдущей лишь постоянной в C1(·)

Решето Эратосфена

Для построения простых чисел, меньших какому-либо N, можно воспользоваться так называемым решетом Эратосфена. Если мы хотим составить таблицу всех простых чисел среди чисел 2, 3, . . . , N, то нужно сперва вычеркнуть все числа, делящиеся на 2, кроме 2. Затем взять число 3 и вычеркнуть все последующие числа, делящиеся на3 . Затем взять следующее не вычеркнутое число (т. е. 5) и вычеркнуть все последующие делящиеся на него числа, и так далее. В итоге останутся лишь простые числа. Для реализации метода нужен большой объем памяти ЭВМ, однако для составления таблиц простых чисел он является наилучшим. В книге  описаны эффективные алгоритмы, реализующие решето Эратосфена для построения таблиц простых чисел и вычисление факторных баз.  Этот метод также как и метод пробных делений является детерминированным.

Вероятностные тесты

Пусть n Є N, n нечетно, n > 1. Вероятностный тест на простоту проводится следующим образом. Выбирается случайное a Є N, 1 ≤ a

Малая теорема Ферма

Для проверки простоты чисел n порядка 1030—1040 метод пробных делений уже неприменим, потому что даже на самых мощных компьютерах вычисления займут много времени (несколько лет). В 17 веке французский математик Пьер Ферма выдвинул утверждение, которое лежит в основе практически всех возможных тестов на простоту. Малая теорема Ферма: Если n – простое и a – любое целое, то . В частности, если n не делит a, то .

На основании этой теоремы можно построить эффективный тест на простоту.

Тест Ферма: для n > 1 выбираем a > 1 и проверяем малую теорему Ферма. Если малая теорема Ферма не выполнена, то n – составное. Если же она выполнена, то мы еще не можем сделать вывод о простоте n, поскольку теорема дает лишь необходимое условие. Этот тест является эффективным для обнаружения составных чисел.

Тест Рабина-Миллера и сильно возможно простые числа.

Можно существенно улучшить тест Ферма, заметив, что если n – простое нечетное, то для 1 есть только два квадратных корня по модулю n: 1 и -1. Таким образом, квадратный корень из an-1, a(n-1)/2 равен плюс или минус единице. Если (n – 1)/2 опять нечетно, то мы сможем снова извлечь корень и так далее. Первый вариант алгоритма, предлагает использовать только одно деление:

Тест Леманна (Lehmann): если для какого-либо целого числа a меньшего n не выполняется условие a(n-1)/2 ±1 (mod n), то число n – составное. Если это условие выполняется, то число n – возможно простое, причем вероятность ошибки не превышает 50%. Тест Леманна не используется, так как он хуже аналогичного вероятностного теста Рабина-Миллера. Но этот тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.