Псевдопростые числа Ферма

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

• 1 Определение
• 2 Свойства
  • 2.1 Распределение
  • 2.2 Факторизации
  • 2.3 Наименьшие псевдопростые частицы Ферма
  • 2.4 Список псевдопростых чисел Ферма с фиксированным основанием n
• 3 Какие основания b делают псевдопросто Ферма?
• 4 Слабые псевдопростые числа
• 5 Псевдопростые числа Эйлера – Якоби
• 6 Приложения
• 7 Ссылки
• 8 Внешние ссылки

Маленькая теорема Ферма утверждает, что если p простое, а a взаимно простое с p, то a - 1 делится на p. Для целого числа a>1, если составное целое число x делит a - 1, то x называется псевдопростом Ферма для основания a. Другими словами, составное целое число - это псевдопростое число Ферма для основания a, если оно успешно проходит тест на простоту Ферма для основания a. Ложное утверждение, что все числа, прошедшие тест на простоту Ферма по основанию 2, являются простыми, называется китайской гипотезой.

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

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

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

Целое число x, которое является псевдопростом Ферма для всех значений a, взаимно простых с x, называется числом Кармайкла.

Распределение

Там бесконечно много псевдопростых чисел для любой данной базы a>1. В 1904 году Чиполла показал, как получить бесконечное число псевдопростых чисел с основанием a>1: пусть p будет простым числом, которое не делит a (a - 1). Пусть A = (a - 1) / (a ​​- 1) и пусть B = (a + 1) / (a ​​+ 1). Тогда n = AB составно и является псевдопервичным основанием a. Например, если a = 2 и p = 5, то A = 31, B = 11 и n = 341 является псевдопервичным числом по основанию 2.

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

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

Факторизации

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

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

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

Наименьшие псевдопростые числа Ферма

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

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

Список псевдопростых чисел Ферма с фиксированным основанием n

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

Если составной $n\; \{\backslash \; displaystyle\; n\}$четный, то $n\; \{\backslash \; displaystyle\; n\}$является псевдопростом Ферма для тривиального основания. $б\; \equiv \; 1\; (модуль\; n)\; \{\backslash \; displaystyle\; b\; \backslash \; Equiv\; 1\; \{\backslash \; pmod\; \{n\}\}\}$. Если составной $n\; \{\backslash \; displaystyle\; n\}$является нечетным, то $n\; \{\backslash \; displaystyle\; n\}$является псевдопростом Ферма для тривиальных оснований $b\; \equiv \; \pm \; 1\; (mod\; n)\; \{\backslash \; displaystyle\; b\; \backslash \; Equiv\; \backslash \; pm\; 1\; \{\backslash \; pmod\; \{n\}\}\}$.

Для любого составного $n\; \{\backslash \; displaystyle\; n\}$количество различных оснований $b\; \{\backslash \; displaystyle\; b\}$по модулю $n\; \{\backslash \; displaystyle\; n\}$, для которого $n\; \{\backslash \; displaystyle\; n\}$является Основание псевдопроста Ферма $b\; \{\backslash \; displaystyle\; b\}$, равно

$\prod \; i\; =\; 1\; k\; gcd\; (pi\; -\; 1,\; n\; -\; 1)\; \{\backslash \; displaystyle\; \backslash \; prod\; \_\; \{i\; =\; 1\}\; ^\; \{k\}\; \backslash \; gcd\; (p\_\; \{i\}\; -1,\; n-1)\}$

где $p\; 1,\dots ,\; pk\; \{\backslash \; displaystyle\; p\_\; \{1\},\; \backslash \; dots,\; p\_\; \{k\}\}$- различные простые множители $n\; \{\backslash \; displaystyle\; n\}$. Сюда входят тривиальные основы.

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

Каждая нечетная композиция $n\; \{\backslash \; displaystyle\; n\}$- псевдопростое число Ферма по крайней мере для двух нетривиальных оснований по модулю $n\; \{\backslash \; displaystyle\; n\}$, если не $n\; \{\backslash \; displaystyle\; n\}$- степень числа 3.

Для составного n < 200, the following is a table of all bases b < n which n is a Fermat pseudoprime. If a composite number n is not in the table (or n is in the sequence A209211 ), тогда n является псевдопростом только для тривиального основания 1 по модулю n.

Для получения дополнительной информации (n = от 201 до 5000) см., Эта страница не определяет, что n является псевдопервичным основанием, равным 1 или -1 (mod n). Когда 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 должно делиться $\phi \; \{\backslash \; displaystyle\; \backslash \; varphi\}$ (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 )

Наименьшее число с n значениями 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 ) (тогда и только тогда, когда n равно даже, а не totient из бесквадратное число, тогда n-й член этой последовательности равен 0)

Составное число n, удовлетворяющие тому, что $bn\; \equiv \; b\; (mod\; n)\; \{\backslash \; displaystyle\; b\; ^\; \{n\}\; \backslash \; Equiv\; b\; \{\backslash \; pmod\; \{n\}\}\}$, называется слабым псевдопростом с основанием b . Этому условию удовлетворяет псевдопервичное число, лежащее в основе a (по обычному определению). И наоборот, слабое псевдопростое число, взаимно простое с основанием, является псевдопростом в обычном смысле слова, иначе это может быть, а может и не быть. Наименее слабые псевдопростые числа по основанию 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,... (последовательность A000790 в OEIS )

Все члены меньше или равны наименьшее число Кармайкла, 561. За исключением 561, только полупростые числа могут встречаться в приведенной выше последовательности, но не все полупростые числа меньше 561 встречаются, полупростое число pq (p ≤ q) меньше 561 встречается в приведенных выше последовательностях тогда и только тогда, когда p - 1 делит q - 1. (см. OEIS : A108574 ) Кроме того, наименьшее псевдопростое число по основанию n (также не обязательно, превышающее n) (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,... (последовательность A239293 в OEIS )

Числа Кармайкла являются слабыми псевдопростыми числами для всех оснований.

Наименьшее даже слабое псевдопростое число по основанию 2 - 161038 (см. OEIS : A006935 ).

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

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

• W. Ф. Голуэй и Ян Фейтсма, Таблицы псевдопростых чисел для базы 2 и связанных данных (исчерпывающий список всех псевдопростых чисел для базы 2 ниже 2, включая факторизацию, сильные псевдопростые числа и числа Кармайкла)
• псевдопросто