Тест на простоту

Алгоритм определения, является ли число простым

Тест на простоту — это алгоритм для определения того, является ли входное число простым . Среди других областей математики он используется в криптографии . В отличие от факторизации целых чисел , тесты на простоту обычно не выдают простые множители , а только сообщают, является ли входное число простым или нет. Факторизация считается вычислительно сложной задачей, тогда как проверка на простоту сравнительно проста ( время ее выполнения полиномиально зависит от размера входных данных). Некоторые тесты на простоту доказывают, что число является простым, в то время как другие, такие как Миллер–Рабин, доказывают, что число является составным . Поэтому последние можно было бы точнее назвать тестами на составность, а не тестами на простоту.

Простые методы

Простейшим тестом на простоту является пробное деление : дано входное число, , проверяется, делится ли оно на любое простое число от 2 до (т. е. не дает ли деление остатка ). Если да, то является составным . В противном случае оно является простым. ^[1] Для любого делителя должен быть другой делитель , и простой делитель , и поэтому достаточно поиска не более простых делителей . ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n}$ ${\displaystyle p\geq {\sqrt {n}}}$ ${\displaystyle n/p\leq {\sqrt {n}}}$ ${\displaystyle q}$ ${\displaystyle n/p}$ ${\displaystyle {\sqrt {n}}}$

Например, рассмотрим число 100, делителями которого являются следующие числа:

1, 2, 4, 5, 10, 20, 25, 50, 100.

Когда все возможные делители до проверены, некоторые делители будут обнаружены дважды . Чтобы увидеть это, рассмотрим список пар делителей 100: ${\displaystyle n}$

${\displaystyle 1\times 100,\;2\times 50,\;4\times 25,\;5\times 20,\;10\times 10,\;20\times 5,\;25\times 4,\;50\times 2,\;100\times 1}$.

Прошлые продукты являются обратными по отношению к продуктам, которые появились ранее. Например, и являются обратными друг другу. Кроме того, из двух делителей, и . Это наблюдение обобщается на все : все пары делителей содержат делитель, меньший или равный , поэтому алгоритму нужно искать только делители, меньшие или равные , чтобы гарантировать обнаружение всех пар делителей. ^[1] ${\displaystyle 10\times 10}$ ${\displaystyle 5\times 20}$ ${\displaystyle 20\times 5}$ ${\displaystyle 5\leq {\sqrt {100}}=10}$ ${\displaystyle 20\geq {\sqrt {100}}=10}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Кроме того, 2 является простым числом, делящим 100, что немедленно доказывает, что 100 не является простым числом. Каждое положительное целое число, кроме 1, делится по крайней мере на одно простое число по Основной теореме арифметики . Поэтому алгоритму нужно искать только простые делители, меньшие или равные . ${\displaystyle {\sqrt {n}}}$

В качестве другого примера рассмотрим, как этот алгоритм определяет простоту числа 17. Имеется , и единственные простые числа — 2 и 3. Ни одно из них не делит 17, что доказывает, что 17 — простое число. В качестве последнего примера рассмотрим 221. Имеется , и простые числа — 2, 3, 5, 7, 11 и 13. Проверив каждое из них, обнаруживаем, что , что доказывает, что 221 не является простым числом. ${\displaystyle 4<{\sqrt {17}}<5}$ ${\displaystyle \leq {\sqrt {17}}}$ ${\displaystyle 14<{\sqrt {221}}<15}$ ${\displaystyle \leq {\sqrt {221}}}$ ${\displaystyle 221/13=17}$

В случаях, когда невозможно вычислить список простых чисел , можно также просто (и медленно) проверить все числа между и на наличие делителей. Довольно простая оптимизация — проверить делимость на 2 и только на нечетные числа между 3 и , поскольку делимость на четное число подразумевает делимость на 2. ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle 2}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Этот метод можно улучшить еще больше. Обратите внимание, что все простые числа, большие 3, имеют вид для неотрицательного целого числа и . Действительно, каждое целое число имеет вид для положительного целого числа и . Так как 2 делит , и , а 3 делит и , единственными возможными остатками по модулю 6 для простого числа, большего 3, являются 1 и 5. Таким образом, более эффективным тестом на простоту для является проверка того, делится ли на 2 или 3, а затем проверка всех чисел вида и , которые являются . Это почти в три раза быстрее проверки всех чисел до . ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{1,5\}}$ ${\displaystyle 6k+i}$ ${\displaystyle k}$ ${\displaystyle i\in \{0,1,2,3,4,5\}}$ ${\displaystyle 6k,6k+2}$ ${\displaystyle 6k+4}$ ${\displaystyle 6k}$ ${\displaystyle 6k+3}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle 6k+1}$ ${\displaystyle 6k+5}$ ${\displaystyle \leq {\sqrt {n}}}$ ${\displaystyle {\sqrt {n}}}$

Обобщая далее, все простые числа, большие, чем ( c primorial ), имеют вид для положительных целых чисел, и взаимно просты с . Например, рассмотрим . Все целые числа имеют вид для целых чисел с . Теперь, 2 делит , 3 делит , и 5 делит . Таким образом, все простые числа, большие 30, имеют вид для . Конечно, не все числа вида с взаимно простым с являются простыми. Например, не является простым, хотя 17 взаимно просто с . ${\displaystyle c\#}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<c\#}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 6\#=2\cdot 3\cdot 5=30}$ ${\displaystyle 30k+i}$ ${\displaystyle i,k}$ ${\displaystyle 0\leq i<30}$ ${\displaystyle 0,2,4,\dots ,28}$ ${\displaystyle 0,3,6,\dots ,27}$ ${\displaystyle 0,5,10,\dots ,25}$ ${\displaystyle 30k+i}$ ${\displaystyle i\in \{1,7,11,13,17,19,23,29\}}$ ${\displaystyle c\#\cdot k+i}$ ${\displaystyle i}$ ${\displaystyle c\#}$ ${\displaystyle 19\cdot 23=437=210\cdot 2+17=2\cdot 7\#+17}$ ${\displaystyle 7\#=2\cdot 3\cdot 5\cdot 7}$

По мере роста доля взаимно простых остатков к остаткам уменьшается, и поэтому время проверки уменьшается (хотя по-прежнему необходимо проверять делимость на все простые числа, которые меньше ). Наблюдения, аналогичные предыдущим, можно применять рекурсивно , давая решето Эратосфена . ${\displaystyle c}$ ${\displaystyle n}$ ${\displaystyle c}$

Один из способов ускорить эти методы (и все остальные, упомянутые ниже) — предварительно вычислить и сохранить список всех простых чисел до определенной границы, например, все простые числа до 200. (Такой список можно вычислить с помощью решета Эратосфена или алгоритма, который проверяет каждое инкрементное число против всех известных простых чисел ). Затем, перед проверкой на простоту с помощью крупномасштабного метода, можно сначала проверить делимость на любое простое число из списка. Если оно делится на любое из этих чисел, то оно является составным, и любые дальнейшие проверки можно пропустить. ${\displaystyle m}$ ${\displaystyle \leq {\sqrt {m}}}$ ${\displaystyle n}$ ${\displaystyle n}$

Простой, но очень неэффективный тест на простоту использует теорему Уилсона , которая утверждает, что является простым тогда и только тогда, когда: ${\displaystyle p}$

${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$

Хотя этот метод требует около модульных умножений, что делает его непрактичным, теоремы о простых числах и модульных остатках составляют основу многих более практичных методов. ${\displaystyle p}$

Эвристические тесты

Это тесты, которые, кажется, хорошо работают на практике, но не доказаны и, следовательно, технически говоря, вообще не являются алгоритмами. Тест Ферма и тест Фибоначчи — простые примеры, и они очень эффективны в сочетании. Джон Селфридж предположил, что если p — нечетное число, и p ≡ ±2 (mod 5), то p будет простым, если выполняются оба следующих условия:

• 2 ^{p −1} ≡ 1 (mod p ),
• f _{p +1} ≡ 0 (mod p ),

где f _k - k -е число Фибоначчи . Первое условие - это тест Ферма на простоту с использованием основания 2.

В общем случае, если p ≡ a (mod x ² +4), где a — квадратичный невычет (mod x ² +4), то p должно быть простым, если выполняются следующие условия:

• 2 ^{p −1} ≡ 1 (mod p ),
• f ( 1 ) _{p +1} ≡ 0 (mod p ),

f ( x ) _k — k - й полином Фибоначчи в точке x .

Селфридж, Карл Померанс и Сэмюэл Вагстафф вместе предлагают 620 долларов за контрпример. ^[2]

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

Вероятностные тесты более строги, чем эвристики, в том смысле, что они предоставляют доказуемые границы вероятности быть обманутым составным числом. Многие популярные тесты на простоту являются вероятностными тестами. Эти тесты используют, помимо тестируемого числа n , некоторые другие числа a , которые выбираются случайным образом из некоторого выборочного пространства ; обычные рандомизированные тесты на простоту никогда не сообщают о простом числе как о составном, но составное число может быть сообщено как о простом. Вероятность ошибки можно уменьшить, повторив тест с несколькими независимо выбранными значениями a ; для двух обычно используемых тестов для любого составного числа n по крайней мере половина a ' s обнаруживает составность n ' , поэтому k повторений уменьшают вероятность ошибки максимум до 2 ^{− k} , которую можно сделать произвольно малой, увеличив k .

Базовая структура рандомизированных тестов на простоту выглядит следующим образом:

1. Случайным образом выберите число a .
2. Проверить равенство (соответствующее выбранному тесту) с участием a и заданного числа n . Если равенство не выполняется, то n является составным числом, а a является свидетелем составности, и тест останавливается.
3. Возвращайтесь к первому шагу, пока не будет достигнута необходимая точность.

Если после одной или нескольких итераций n не окажется составным числом, то его можно объявить, вероятно, простым .

Тест Ферма на простоту

Самый простой вероятностный тест на простоту — это тест Ферма на простоту (на самом деле тест на составность). Он работает следующим образом:

Дано целое число n , выберите некоторое целое число a, взаимно простое с n , и вычислите a ^{n − 1} по модулю n . Если результат отличается от 1, то n является составным числом. Если он равен 1, то n может быть простым числом.

Если a ^{n −1} (по модулю n ) равно 1, но n не является простым, то n называется псевдопростым по основанию a . На практике, если a ^{n −1} (по модулю n ) равно 1, то n обычно является простым. Но вот контрпример: если n = 341 и a = 2, то

${\displaystyle 2^{340}\equiv 1{\pmod {341}}}$

хотя 341 = 11·31 является составным. Фактически, 341 является наименьшим псевдопростым числом по основанию 2 (см. рисунок 1 из ^[3] ).

Существует всего 21853 псевдопростых числа с основанием 2, которые меньше 2,5 × 10¹⁰ (см. стр. 1005 ^[3] ). Это означает, что для n до 2,5 × 10¹⁰ , если 2 ^{n −1} (по модулю n ) равно 1, то n является простым числом, если только n не является одним из этих 21853 псевдопростых чисел.

Некоторые составные числа ( числа Кармайкла ) обладают свойством, что a ^{n − 1} равно 1 (по модулю n ) для любого a , которое взаимно просто с n . Наименьшим примером является n = 561 = 3·11·17, для которого a ⁵⁶⁰ равно 1 (по модулю 561) для всех a, взаимно простых с 561. Тем не менее, тест Ферма часто используется, если требуется быстрая проверка чисел, например, на этапе генерации ключей криптографического алгоритма с открытым ключом RSA .

Тест на простоту Миллера-Рабина и Соловея-Штрассена

Тест на простоту Миллера–Рабина и тест на простоту Соловея–Штрассена являются более сложными вариантами, которые обнаруживают все составные числа (еще раз, это означает: для каждого составного числа n по крайней мере 3/4 (Миллер–Рабин) или 1/2 (Соловей–Штрассен) чисел a являются свидетелями составности n ). Это также тесты на составность.

Тест Миллера-Рабина на простоту работает следующим образом: дано целое число n , выбираем некоторое положительное целое число a  <  n . Пусть 2 ^s d = n  − 1, где d нечетно. Если

${\displaystyle a^{d}\not \equiv \pm 1{\pmod {n}}}$

и

${\displaystyle a^{2^{r}d}\not \equiv -1{\pmod {n}}}$для всех ${\displaystyle 0\leq r\leq s-1,}$

тогда n является составным, а a является свидетелем составности. В противном случае n может быть или не быть простым. Тест Миллера–Рабина является сильным вероятным тестом на простоту (см. PSW ^[3] стр. 1004).

Тест на простоту Соловея-Штрассена использует другое равенство: дано нечетное число n , выберите некоторое целое число a  <  n , если

${\displaystyle a^{(n-1)/2}\not \equiv \left({\frac {a}{n}}\right){\pmod {n}}}$, где символ Якоби , ${\displaystyle \left({\frac {a}{n}}\right)}$

тогда n является составным, а a является свидетелем составности. В противном случае n может быть или не быть простым. Тест Соловея–Штрассена является тестом Эйлера на вероятное простое число (см. PSW ^[3] стр. 1003).

Для каждого отдельного значения a тест Соловея–Штрассена слабее теста Миллера–Рабина. Например, если n = 1905 и a = 2, то тест Миллера–Рабина показывает, что n является составным, а тест Соловея–Штрассена — нет. Это потому, что 1905 является псевдопростым числом Эйлера по основанию 2, но не сильным псевдопростым числом по основанию 2 (это показано на рисунке 1 PSW ^[3] ).

Тест Фробениуса на простоту

Тесты простоты Миллера–Рабина и Соловея–Штрассена просты и намного быстрее других общих тестов простоты. Одним из методов дальнейшего повышения эффективности в некоторых случаях является тест псевдопростоты Фробениуса ; раунд этого теста занимает примерно в три раза больше времени, чем раунд Миллера–Рабина, но достигает границы вероятности, сравнимой с семью раундами Миллера–Рабина.

Тест Фробениуса является обобщением теста Люка на вероятное простое число .

Тест простоты Бейли-ПСВ

Тест простоты Бейли-ПСВ — это вероятностный тест простоты, который объединяет тест Ферма или Миллера-Рабина с вероятным тестом простоты Люка, чтобы получить тест простоты, который не имеет известных контрпримеров. То есть, нет известных составных n , для которых этот тест сообщает, что n , вероятно, является простым. ^{[4] [5]} Было показано, что нет контрпримеров для n . ${\displaystyle <2^{64}}$

Другие тесты

Леонард Адлеман и Минг-Дэ Хуан представили безошибочный (но ожидаемо полиномиальный по времени) вариант теста простоты эллиптической кривой . В отличие от других вероятностных тестов, этот алгоритм выдает сертификат простоты и, таким образом, может использоваться для доказательства того, что число является простым. ^[6] На практике алгоритм работает непозволительно медленно.

Если бы квантовые компьютеры были доступны, простота могла бы быть проверена асимптотически быстрее , чем с помощью классических компьютеров. Сочетание алгоритма Шора , метода факторизации целых чисел, с тестом на простоту Поклингтона могло бы решить проблему в . ^[7] ${\displaystyle O((\log n)^{3}(\log \log n)^{2}\log \log \log n)}$

Быстрые детерминированные тесты

Ближе к началу 20-го века было показано, что следствие малой теоремы Ферма может быть использовано для проверки простоты. ^[8] Это привело к тесту Поклингтона на простоту . ^[9] Однако, поскольку этот тест требует частичной факторизации n  − 1, время выполнения в худшем случае все еще было довольно медленным. Первым детерминированным тестом на простоту, значительно более быстрым, чем наивные методы, был тест циклотомии ; можно доказать, что его время выполнения равно O ( (log  n ) ^{c  log log log  n} ), где n — число для проверки простоты, а c — константа, не зависящая от n . Было сделано много дальнейших улучшений, но ни одно из них не могло иметь полиномиальное время выполнения. (Время выполнения измеряется в терминах размера входных данных, который в данном случае равен ~ log  n , что является числом бит, необходимых для представления числа n .) Можно доказать, что  тест на простоту эллиптической кривой выполняется за O((log n ) ⁶ ), если верны некоторые предположения из аналитической теории чисел . ^{[ which? ]} Аналогично, при обобщенной гипотезе Римана можно доказать , что детерминированный тест Миллера , который составляет основу вероятностного теста Миллера–Рабина, выполняется за Õ ((log  n ) ⁴ ). ^[10] На практике этот алгоритм медленнее двух других для размеров чисел, с которыми вообще можно иметь дело. Поскольку реализация этих двух методов довольно сложна и создает риск ошибок программирования, часто предпочитают более медленные, но простые тесты.

В 2002 году Маниндра Агравал , Нирадж Кайал и Нитин Саксена изобрели первый доказуемо безусловный детерминированный полиномиальный тест на простоту . Тест на простоту AKS выполняется за Õ((log  n ) ¹² ) (улучшенный до Õ((log  n ) ^7.5 ) ^[11] в опубликованной редакции их статьи), который может быть дополнительно сокращен до Õ((log  n ) ⁶ ) , если гипотеза Софи Жермен верна. ^[12] Впоследствии Ленстра и Померанс представили версию теста, которая выполняется за время Õ((log  n ) ⁶ ) безусловно. ^[13]

Агравал, Каяль и Саксена предлагают вариант своего алгоритма, который будет работать за Õ((log  n ) ³ ), если гипотеза Агравала верна; однако эвристический аргумент Хендрика Ленстры и Карла Померанса предполагает, что она, вероятно, ложна. ^[11] Модифицированная версия гипотезы Агравала, гипотеза Агравала–Поповича ^[14] , все еще может быть верна.

Сложность

В теории вычислительной сложности формальный язык, соответствующий простым числам, обозначается как PRIMES. Легко показать, что PRIMES принадлежит Co-NP : его дополнение COMPOSITES принадлежит NP, поскольку можно определить составность, недетерминированно угадывая фактор.

В 1975 году Воан Пратт показал, что существует сертификат простоты, который можно проверить за полиномиальное время, и, таким образом, PRIMES входит в NP , а значит, и в ⁠ ⁠ ${\displaystyle {\mathsf {NP\cap coNP}}}$ . Подробности см. в сертификате простоты .

Последующее открытие алгоритмов Соловея–Штрассена и Миллера–Рабина поместило PRIMES в coRP . В 1992 году алгоритм Адлемана–Хуанга ^[6] снизил сложность до ⁠ ⁠ ${\displaystyle {\mathsf {{\color {Blue}ZPP}=RP\cap coRP}}}$ , что превзошло результат Пратта.

Тест простоты Адлемана –Померанса–Румели, разработанный в 1983 году, поместил PRIMES в QP ( квазиполиномиальное время ), которое, как известно, не сопоставимо с упомянутыми выше классами.

Из-за его практической податливости, полиномиальных алгоритмов, предполагающих гипотезу Римана, и других подобных доказательств, долгое время подозревалось, но не было доказано, что простота может быть решена за полиномиальное время. Существование теста простоты AKS наконец решило этот давний вопрос и поместило PRIMES в P . Однако, неизвестно, является ли PRIMES P-полным , и неизвестно, лежит ли он в классах, лежащих внутри P, таких как NC или L . Известно, что PRIMES не находится в AC 0 . ^[15]

Теоретико-числовые методы

Существуют некоторые методы теории чисел для проверки того, является ли число простым, например, тест Лукаса и тест Прота . Эти тесты обычно требуют факторизации n  + 1, n − 1 или аналогичной величины, что означает, что они бесполезны для универсальной проверки простоты, но они часто бывают довольно мощными, когда известно, что проверяемое число n имеет специальную форму.

Тест Лукаса основан на том факте, что мультипликативный порядок числа a по модулю n равен n − 1 для простого числа n , когда a является примитивным корнем по модулю n . Если мы можем показать, что a является примитивным для n , мы можем показать, что n является простым.

Ссылки

1. Riesel (1994) стр.2-3
2. Джон Селфридж#Гипотеза Селфриджа о проверке простоты .
3. Pomerance, Carl ; Selfridge, John L. ; Wagstaff, Samuel S. Jr. (июль 1980 г.). "Псевдопростые числа до 25·109" (PDF) . Mathematics of Computation . 35 (151): 1003–1026. doi : 10.1090/S0025-5718-1980-0572872-7 .
4. Бейли, Роберт; Вагстафф, Сэмюэл С. младший (октябрь 1980 г.). «Псевдопростые числа Лукаса» (PDF) . Математика вычислений . 35 (152): 1391–1417. doi : 10.1090/S0025-5718-1980-0583518-6 . MR  0583518.
5. Бейли, Роберт; Фиори, Эндрю; Вагстафф, Сэмюэл С. младший (июль 2021 г.). «Усиление теста простоты Бейли-ПСВ». Математика вычислений . 90 (330): 1931–1955. arXiv : 2006.14425 . doi : 10.1090/mcom/3616. S2CID  220055722.
6. Adleman, Leonard M. ; Huang, Ming-Deh (1992). Проверка простоты и абелевы многообразия над конечным полем . Конспект лекций по математике. Том 1512. Springer-Verlag . ISBN 3-540-55308-8.
7. Чау, Х. Ф.; Ло, Х.-К. (1995). «Проверка простоты с помощью квантовой факторизации». arXiv : quant-ph/9508005 .
8. Поклингтон, ХК (1914). «Определение простой или составной природы больших чисел с помощью теоремы Ферма». Cambr. Phil. Soc. Proc . 18 : 29–30. JFM  45.1250.02.
9. Вайсштейн, Эрик В. «Теорема Поклингтона». MathWorld .
10. Гэри Л. Миллер (1976). «Гипотеза Римана и тесты на простоту». Журнал компьютерных и системных наук . 13 (3): 300–317. doi : 10.1016/S0022-0000(76)80043-8 .
11. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «Простые числа находятся в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 .
12. Агравал, Маниндра; Каял, Нирадж; Саксена, Нитин (2004). «ПРАЙМС находится в P» (PDF) . Анналы математики . 160 (2): 781–793. дои : 10.4007/анналы.2004.160.781 .
13. Карл Померанс и Хендрик В. Ленстра (20 июля 2005 г.). «Проверка простоты с гауссовыми периодами» (PDF) .
14. Попович, Роман (30 декабря 2008 г.). «Заметка о гипотезе Агравала» (PDF) .
15. Аллендер, Эрик; Сакс, Майкл; Шпарлинский, Игорь (2001). «Нижняя граница простоты». Журнал компьютерных и системных наук . 62 (2): 356–366. doi :10.1006/jcss.2000.1725.

Источники

• Крэндалл, Ричард ; Померанс, Карл (2005). Простые числа: вычислительная перспектива (2-е изд.). Springer. ISBN 0-387-25282-7.Глава 3: Распознавание простых и составных чисел, стр. 109–158. Глава 4: Доказательство простоты, стр. 159–190. Раздел 7.6: Доказательство простоты эллиптической кривой (ECPP), стр. 334–340.
• Кнут, Дональд (1997). "раздел 4.5.4". Искусство программирования . Том 2: Получисленные алгоритмы (3-е изд.). Эддисон–Уэсли. стр. 391–396. ISBN 0-201-89684-2.
• Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001). "Раздел 31.8: Проверка простоты". Введение в алгоритмы (второе изд.). MIT Press, McGraw–Hill. стр. 887–896. ISBN 0-262-03293-7.
• Пападимитриу, Христос Х. (1993). «Раздел 10.2: Первичность». Computational Complexity (1-е изд.). Эддисон Уэсли. стр. 222–227. ISBN 0-201-53082-1. Збл  0833.68049.
• Ризель, Ганс (1994). Простые числа и компьютерные методы факторизации . Прогресс в математике. Т. 126 (второе изд.). Бостон, Массачусетс: Birkhäuser. ISBN 0-8176-3743-5. Збл  0821.11001.

Внешние ссылки

• Solovay-Strassen (computacion.cs.cinvestav.mx) в archive.today (архив 2012-12-20) – Реализация теста простоты Solovay-Strassen в Maple
• Различение простых чисел от составных, DJ Bernstein (cr.yp.to)
• Главные страницы (primes.utm.edu)
• Тест на простоту Люка с разложением N − 1 (MathPages.com) в веб-архиве Библиотеки Конгресса (архив 2010-08-06)
• PRIMABOINCA — это исследовательский проект, который использует подключенные к Интернету компьютеры для поиска контрпримера к некоторым гипотезам. Первая гипотеза ( гипотеза Агравала ) стала основой для формулировки первого детерминированного алгоритма проверки простых чисел за полиномиальное время ( алгоритм AKS ).