Тест Миллера — Рабина — вероятностный полиномиальный тест простоты. Тест Миллера — Рабина, наряду с тестом Ферма и тестом Соловея — Штрассена, позволяет эффективно определить, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее тест Миллера — Рабина часто используется в криптографии для получения больших случайных простых чисел.
Вопрос определения того, является ли натуральное число 
простым, известен как проблема простоты.
Тест Пепина — тест простоты для чисел Ферма. Тест назван в честь французского математика Феофила Пепина.
Псевдопростое число — натуральное число, обладающее некоторыми свойствами простых чисел, являясь тем не менее составным. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.
В теории алгоритмов классом сложности BPP называется класс предикатов, быстро вычислимых и дающих ответ с высокой вероятностью. Задачи, решаемые вероятностными методами и лежащие в BPP, возникают на практике очень часто.
Тест или испытание — способ изучения глубинных процессов деятельности системы, посредством помещения системы в разные ситуации и отслеживание доступных наблюдению изменений в ней.
Вероятно простое число — это число, которое проходит тест простоты. Сильное вероятно простое число — это число, которое проходит сильную версию теста простоты. Сильное псевдопростое число — это составное число, которое проходит сильную версию теста простоты.
GIMPS — широкомасштабный проект добровольных вычислений по поиску простых чисел Мерсенна.
Михаэль Озёр Рабин — израильский учёный в области теории вычислительных систем, математик, лауреат премии Тьюринга.
Тест Аграва́ла — Кая́ла — Саксе́ны — единственный известный на данный момент универсальный полиномиальный, детерминированный и безусловный тест простоты чисел, основанный на обобщении малой теоремы Ферма на многочлены.
Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может дать неверный ответ. Основное преимущество теста заключается в том, что он, в отличие от теста Ферма, распознает числа Кармайкла как составные.
Тест Миллера — детерминированный полиномиальный тест простоты, предложенный Миллером и впервые опубликованный в 1976 году .
В теории чисел тест простоты Люка — это тест простоты натурального числа n; для его работы необходимо знать разложение 
на множители. Для простого числа n простые множители числа вместе с некоторым основанием a составляют сертификат Пратта, который позволяет подтвердить за полиномиальное время, что число n является простым.
В теории чисел, вероятно простым числом называется целое число, которое удовлетворяет некоторым условиям, которым удовлетворяют все простые числа. Различные типы вероятно простых имеют различные условия. Поскольку вероятно простое может быть составным, условие выбирается так, чтобы сделать эти исключения редкими.
В теории чисел псевдопростым числом Фробениуса называется псевдопростое число, прошедшее трехшаговый тест принадлежности к вероятно простым числам, разработанный Джоном Грантамом в 1996 году.
Фо́лькер Штра́ссен — немецкий математик, почетный профессор кафедры математики и статистики Констанцского университета.
Га́ри Ли Ми́ллер — американский математик, профессор информатики университета Карнеги — Меллона.
Тест Бейли — Померанца — Селфриджа — Уогстаффа — вероятностный алгоритм проверки на простоту, который определяет, является число составным или вероятно простым. Назван по фамилиям его изобретателей — Роберта Бэйли, Карла Померанца, Джона Селфриджа, Сэмюэля Вагстаффа.
В математике и информатике сертификат простоты — это строгое доказательство того, что число является простым. Наличие сертификата простоты позволяет проверить, что число простое, не прибегая к тестам простоты.
