Ферма псевдопростое

В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел , вытекающих из малой теоремы Ферма .

Малая теорема Ферма утверждает, что если p — простое число, а a — взаимно простое с p , то a ^{p −1}  − 1 делится на p . Для положительного целого числа a , если составное целое число x делит a ^{x −1}  − 1, то x называется псевдопростым числом Ферма по основанию a . ^{[1] : Опр. 3.32} Другими словами, составное целое число является псевдопростым числом Ферма по основанию a, если оно успешно проходит тест Ферма на простоту для основания a . ^[2] Ложное утверждение, что все числа, проходящие тест Ферма на простоту для основания 2, являются простыми, называется китайской гипотезой .

Наименьшее псевдопростое число Ферма по основанию 2 — это 341. Оно не является простым числом, поскольку равно 11·31, но оно удовлетворяет малой теореме Ферма: 2 ^·340 ≡ 1 (mod 341) и, таким образом, проходит тест Ферма на простоту для основания 2.

Псевдопростые числа с основанием 2 иногда называют числами Сарруса , в честь П. Ф. Сарруса , который открыл, что число 341 обладает этим свойством, числами Пуле , в честь П. Пуле , который составил таблицу таких чисел, или ферматианами (последовательность A001567 в OEIS ).

Псевдопростое число Ферма часто называют псевдопростым числом , при этом подразумевается модификатор Ферма .

Целое число x , которое является псевдопростым числом Ферма для всех значений a , взаимно простых с x, называется числом Кармайкла . ^{[2] [1] : Определение 3.34}

Существует бесконечно много псевдопростых чисел для любого заданного основания a > 1. В 1904 году Чиполла показал, как получить бесконечное количество псевдопростых чисел для основания a > 1: пусть A = ( a ^p - 1)/( a - 1) и пусть B = ( a ^p + 1)/( a + 1), где p — простое число, которое не делит a ( a ² - 1). Тогда n = AB является составным и является псевдопростым числом для основания a . ^{[3] [4]} Например, если a = 2 и p = 5, то A = 31, B = 11, а n = 341 является псевдопростым числом для основания 2.

На самом деле, существует бесконечно много сильных псевдопростых чисел с любым основанием, большим 1 (см. теорему 1 из ^[5] ) и бесконечно много чисел Кармайкла, ^[6] но они сравнительно редки. Существует три псевдопростых числа с основанием 2 ниже 1000, 245 ниже миллиона и 21853 ниже 25·10 ⁹ . Существует 4842 сильных псевдопростых числа с основанием 2 и 2163 числа Кармайкла ниже этого предела (см. таблицу 1 из ^[5] ).

Начиная с 17·257, произведение последовательных чисел Ферма является псевдопростым числом по основанию 2, как и все составные числа Ферма и Мерсенна .

Вероятность того, что составное число n пройдет тест Ферма, стремится к нулю при . В частности, Ким и Померанс показали следующее: вероятность того, что случайное нечетное число n ≤ x является псевдопростым числом Ферма по случайному основанию, меньше 2,77·10 ^-8 для x= 10 ¹⁰⁰ , и не превышает (log x) ^-197 <10 ^{-10 000} для x ≥ 10 ^{100 000} . ^[7]${\displaystyle n\to \infty }$${\displaystyle 1<b<n-1}$

Факторизации 60 чисел Пуле до 60787, включая 13 чисел Кармайкла (выделены жирным шрифтом), приведены в следующей таблице.

(последовательность A001567 в OEIS )

Число Пуле, все делители которого d делят 2 ^d − 2, называется суперчислом Пуле . Существует бесконечно много чисел Пуле, которые не являются суперчислами Пуле. ^[8]

Наименьшее псевдопростое число для каждого основания a ≤ 200 указано в следующей таблице; цвета обозначают количество простых множителей. В отличие от определения в начале статьи, псевдопростые числа ниже a в таблице исключены. (Чтобы разрешить псевдопростые числа ниже a , см. OEIS : A090086 )

(последовательность A007535 в OEIS )

Для получения дополнительной информации (основание от 31 до 100) см. OEIS : A020159 - OEIS : A020228 , а для всех оснований до 150 см. таблицу псевдопростых чисел Ферма (текст на немецком языке), эта страница не определяет n как псевдопростое число по основанию, сравнимому с 1 или -1 (mod n )

Если составное число четное, то является псевдопростым числом Ферма по тривиальному основанию . Если составное число нечетное, то является псевдопростым числом Ферма по тривиальному основанию .${\displaystyle n}$${\displaystyle n}$${\displaystyle b\equiv 1{\pmod {n}}}$${\displaystyle n}$${\displaystyle n}$${\displaystyle b\equiv \pm 1{\pmod {n}}}$

Для любого составного числа число различных базисов по модулю , для которых есть псевдопростой базис Ферма , равно ^{[9] : Теория 1, стр. 1392}${\displaystyle n}$${\displaystyle б}$${\displaystyle n}$${\displaystyle n}$${\displaystyle б}$

${\displaystyle \prod _{i=1}^{k}\НОД(p_{i}-1,n-1)}$

где — различные простые множители числа . Это включает тривиальные основания.${\displaystyle p_{1},\точки ,p_{k}}$${\displaystyle n}$

Например, для это произведение равно . Для наименьшее такое нетривиальное основание равно .${\displaystyle n=341=11\cdot 31}$${\displaystyle \НОД(10,340)\cdot \НОД(30,340)=100}$${\displaystyle n=341}$${\displaystyle b=2}$

Каждое нечетное составное число является псевдопростым числом Ферма по крайней мере для двух нетривиальных оснований по модулю, если только оно не является степенью числа 3. ^{[9] : Cor. 1, стр. 1393}${\displaystyle n}$${\displaystyle n}$${\displaystyle n}$

Для составного n < 200, ниже приведена таблица всех оснований b < n , в которых n является псевдопростым числом Ферма. Если составное число n отсутствует в таблице (или n входит в последовательность A209211), то n является псевдопростым только по тривиальному основанию 1 по модулю n .

Для получения дополнительной информации ( n = 201 to 5000), см. b:de:Pseudoprimzahlen: Tabelle Pseudoprimzahlen (15 - 4999) (Таблица псевдопростых чисел 16–4999). В отличие от списка выше, эта страница исключает основания 1 и n −1. Когда p является простым числом, p ² является псевдопростым числом Ферма по основанию b тогда и только тогда, когда p является простым числом Вифериха по основанию b . Например, 1093 ² = 1194649 является псевдопростым числом Ферма по основанию 2, а 11 ² = 121 является псевдопростым числом Ферма по основанию 3.

Число значений b для n равно (Для простого n число значений b должно быть равно n − 1, поскольку все b удовлетворяют малой теореме Ферма )

1, 1, 2, 1, 4, 1, 6, 1, 2, 1, 10, 1, 12, 1, 4, 1, 16, 1, 18, 1, 4, 1, 22, 1, 4, 1, 2, 3, 28, 1, 30, 1, 4, 1, 4, 1, 36, 1, 4, 1, 40, 1, 42, 1, 8, 1, 46, 1, 6, 1, ... (последовательность A063994 в OEIS )

Наименьшее основание b > 1, при котором n является псевдопростым по основанию b (или простым числом), равно

2, 3, 2, 5, 2, 7, 2, 9, 8, 11, 2, 13, 2, 15, 4, 17, 2, 19, 2, 21, 8, 23, 2, 25, 7, 27, 26, 9, 2, 31, 2, 33, 10, 35, 6, 37, 2, 39, 14, 41, 2, 43, 2, 45, 8, 47, 2, 49, 18, 51, ... (последовательность A105222 в OEIS )

Число значений b для данного n должно делиться на ( n ), или A000010( n ) = 1, 1, 2, 2, 4, 2, 6, 4, 6, 4, 10, 4, 12, 6, 8, 8, 16, 6, 18, 8, 12, 10, 22, 8, 20, 12, 18, 12, 28, 8, 30, 16, 20, 16, 24, 12, 36, 18, 24, 16, 40, 12, 42, 20, 24, 22, 46, 16, 42, 20, ... Частное может быть любым натуральным числом, и частное = 1 тогда и только тогда, когда n является простым числом или Число Кармайкла (561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, ... A002997) Частное = 2 тогда и только тогда, когда n находится в последовательности: 4, 6, 15, 91, 703, 1891, 2701, 11305, 12403, 13981, 18721, ... A191311.)${\displaystyle \varphi}$

Наименьшие числа, которые являются псевдопростыми по отношению к k значениям b , равны (или 0, если такого числа не существует)

1, 3, 28, 5, 66, 7, 232, 45, 190, 11, 276, 13, 1106, 0, 286, 17, 1854, 19, 3820, 891, 2752, 23, 1128, 595, 2046, 0, 532, 29, 1770, 31, 9952, 425, 1288, 0, 2486, 37, 8474, 0, 742, 41, 3486, 43, 7612, 5589, 2356, 47, 13584, 325, 9850, 0, ... (последовательность A064234 в OEIS ) ( если и только если k четно и не является коэффициентом бесквадратного числа , то k -й член этой последовательности равен 0.)

Составное число n , удовлетворяющее , называется слабым псевдопростым числом по основанию b . Для любого заданного основания b все псевдопростые числа Ферма являются слабыми псевдопростыми числами, а все слабые псевдопростые числа, взаимно простые с b , являются псевдопростыми числами Ферма. Однако это определение также допускает некоторые псевдопростые числа, которые не являются взаимно простыми с b . ^[10] Например, наименьшее четное слабое псевдопростое число по основанию 2 равно 161038 (см. OEIS : A006935 ).${\displaystyle b^{n}\equiv b{\pmod {n}}}$

Наименее слабые псевдопростые числа по основаниям b = 1, 2, ...:

4, 341, 6, 4, 4, 6, 6, 4, 4, 6, 10, 4, 4, 14, 6, 4, 4, 6, 6, 4, 4, 6, 22, 4, 4, 9, 6, 4, 4, 6, 6, 4, 4, 6, 9, 4, 4, 38, 6, 4, 4, 6, 6, 4, 4, 6, 46, 4, 4, 10, ... OEIS : A000790

Числа Кармайкла являются слабыми псевдопростыми числами по всем основаниям, поэтому все члены в этом списке меньше или равны наименьшему числу Кармайкла, 561. За исключением 561 = 3⋅11⋅17, в указанной выше последовательности могут встречаться только полупростые числа . Встречаются не все полупростые числа, меньшие 561; полупростое число pq ( p ≤ q ), меньшее 561, встречается в указанных выше последовательностях тогда и только тогда, когда p − 1 делит q − 1 (см. OEIS : A108574 ). Наименьшее псевдопростое число Ферма по основанию b (также не обязательно превышающее b ) ( OEIS : A090086 ) обычно является полупростым, но не всегда; первый контрпример — A090086(648) = 385 = 5 × 7 × 11.

Если мы требуем n > b , то наименьшими слабыми псевдопростыми числами (для b = 1, 2, ...) являются:

4, 341, 6, 6, 10, 10, 14, 9, 12, 15, 15, 22, 21, 15, 21, 20, 34, 25, 38, 21, 28, 33, 33, 25, 28, 27, 39, 36, 35, 49, 49, 33, 44, 35, 45, 42, 45, 39, 57, 52, 82, 66, 77, 45, 55, 69, 65, 49, 56, 51, ... OEIS : A239293

Другой подход заключается в использовании более тонких понятий псевдопростоты, например, сильных псевдопростых чисел или псевдопростых чисел Эйлера–Якоби , для которых нет аналогов чисел Кармайкла . Это приводит к вероятностным алгоритмам, таким как тест простоты Соловея–Штрассена , тест простоты Бейли–ПСВ и тест простоты Миллера–Рабина , которые производят то, что известно как простые числа промышленного класса . Простые числа промышленного класса — это целые числа, простота которых не была «сертифицирована» (т. е. строго доказана), но которые прошли проверку, такую ​​как тест Миллера–Рабина, который имеет ненулевую, но произвольно низкую вероятность неудачи.

Редкость таких псевдопростых чисел имеет важные практические последствия. Например, алгоритмы криптографии с открытым ключом, такие как RSA, требуют возможности быстрого нахождения больших простых чисел. Обычный алгоритм генерации простых чисел заключается в генерации случайных нечетных чисел и проверке их на простоту. Однако детерминированные тесты на простоту медленные. Если пользователь готов допустить произвольно малую вероятность того, что найденное число не является простым числом, а является псевдопростым, можно использовать гораздо более быстрый и простой тест Ферма на простоту .

• WF Galway и Jan Feitsma, Таблицы псевдопростых чисел с основанием 2 и связанных с ними данных (полный список всех псевдопростых чисел с основанием 2 ниже 2 ⁶⁴ , включая факторизацию, сильные псевдопростые числа и числа Кармайкла)
• Исследование псевдопростых чисел