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

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

Этот метод относится к группе детерминированных методов. Пусть 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, и для него проверяется выполнение некоторых условий. Если какое-то из условий не выполнено, то число n—составное, поскольку для простых чисел эти условия являются необходимыми. Если же все условия выполнены, то из этого еще не следует простота n. Однако можно будет считать, что «n —простое число с некоторой вероятностью». Кроме того, обычно доказывают оценку снизу для этой вероятности. Чем больше значений 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%. Тест Леманна не используется, так как он хуже аналогичного вероятностного теста Рабина-Миллера. Но этот тест можно естественным образом улучшить, если извлекать корень по модулю не один раз, а столько, сколько получится.