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

Псевдопросты́е чи́сла Ферма́составные числа, проходящие тест Ферма. Названы в честь французского математика Пьера Ферма. В теории чисел псевдопростые числа Ферма составляют важнейший класс псевдопростых чисел.

Определение

[править | править код]

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

[править | править код]

Составное число называется псевдопростым, если оно удовлетворяет некоторому необходимому (но не достаточному) условию простоты числа, то есть если оно обладает некоторыми свойствами простого числа.

Малая теорема Ферма

[править | править код]

Малая теорема Ферма гласит, что если n — простое число, то для каждого числа a взаимно простого с n справедливо сравнение .

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

[править | править код]

Составное число n называется псевдопростым числом Ферма по основанию a (взаимно простому с n), если выполнено сравнение . Иными словами, составное число называют псевдопростым, если оно проходит тест Ферма по основанию a[1]. Число, являющееся псевдопростым Ферма по каждому взаимно простому с ним основанию, называется числом Кармайкла.

Существуют некоторые вариации определения:

  • Некоторые источники требуют, чтобы псевдопростое число было нечетным[2], так как четное число очевидно является составным.
  • Каждое нечётное число удовлетворяет для , поэтому в таком случае новой информации о числе мы не получим. Это исключается в определении, данном Крэндаллом и Померансом[3]: Составное число является псевдопростым числом Ферма по основанию , если и

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

[править | править код]

Существует бесконечно много псевдопростых чисел по данному основанию (более того существует бесконечно много сильных псевдопростых[4] и бесконечно много чисел Кармайкла[5]), но они довольно редки[6]. Есть только три псевдопростых Ферма по основанию 2 меньше 1000, 245 меньше одного миллиона, и только 21 853 меньше, чем 25 миллиардов[4].

Таблицы с некоторыми псевдопростыми числами Ферма

[править | править код]

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

[править | править код]

Наименьшие псевдопростые Ферма для каждого основания a ≤ 200 приведены в таблице ниже; цвета различают числа по количеству различных простых делителей[7].

Числа Пуле

[править | править код]

Псевдопростые Ферма по основанию 2 называют числами Пуле, по имени бельгийского математика Пола Пуле[англ.][8]. Разложение на множители шестидесяти первых чисел Пуле, в том числе тринадцати чисел Кармайкла (выделены жирным шрифтом), ниже в таблице.

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

Первые псевдопростые числа Ферма (до 10000) по основанию a

[править | править код]

Более подробная информация о псевдопростых числах Ферма по основаниям 31 — 100 представлена в статьях A020159A020228 Энциклопедии целочисленных последовательностей[10].

Основания, по которым число является псевдопростым

[править | править код]

Ниже приведена таблица всех оснований b< n, для которых n — псевдопростое число Ферма (все составные числа являются псевдопростыми по основанию 1, а для b > n решение просто сдвигается на k * n, где k > 0), если составное число n не указано в таблице, то оно является псевдопростым только по основанию 1, или по основаниям, которые сравнимы с 1 (mod n), то есть число оснований b равно 1. Таблица составлена для n < 180[11].

Нужно отметить, что если p — простое, то p2 есть псевдопростое Ферма по основанию b тогда и только тогда, когда pпростое число Вифериха по основанию b. Например, 10932 = 1 194 649 — псевдопростое Ферма по основанию 2.

Количество оснований 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 — псевдопростое (или простое):

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).

Слабые псевдопростые

[править | править код]

Составное число n, для которого справедливо сравнение bn = b (mod n), называется слабым псевдопростым числом Ферма по основанию b (здесь b не обязано быть взаимно простым с n)[13]. Наименьшие слабые псевдопростые по основанию b:

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)

Если требуется, чтобы n > b, тогда:

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)

Приложения

[править | править код]

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

Примечания

[править | править код]
  1. Desmedt, Yvo. Encryption Schemes // Algorithms and theory of computation handbook: Special topics and techniques (англ.) / Atallah, Mikhail J.[англ.] & Blanton, Marina. — CRC Press, 2010. — P. 10—23. — ISBN 978-1-58488-820-8.
  2. Weisstein, Eric W. Fermat Pseudoprime (англ.) на сайте Wolfram MathWorld.
  3. Крэндалл, Померанс, 2011, с. 155.
  4. 1 2 Померанс, Селфридж, Вагстафф, 1980, Теорема 1.
  5. W. R. Alford[англ.]; Andrew Granville; Carl Pomerance. There are Infinitely Many Carmichael Numbers (англ.) // Annals of Mathematics : journal. — 1994. — Vol. 139. — P. 703—722. — doi:10.2307/2118576. Архивировано 4 марта 2005 года.
  6. Крэндалл, Померанс, 2011, Теорема 3.4.2, с. 154-155.
  7. последовательность A007535 в OEIS
  8. последовательность A001567 в OEIS
  9. W. Sierpinski. Chapter V.7 // Elementary Theory of Numbers = Teoria Liczb / Ed. A. Schinzel. — 2 Sub edition. — Amsterdam: North Holland, 1988-02-15. — С. 232. — 528 с. — (North-Holland Mathematical Library). — ISBN 9780444866622. Архивировано 8 декабря 2015 года.
  10. См. также таблицу псевдопростых чисел Ферма для оснований до 150 (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).
  11. Более подробная информация для n = 181…5000 есть в таблице (нем.); здесь n не определяют псевдопростым по основаниям сравнимым с 1 или -1 (mod n).
  12. последовательность A063994 в OEIS
  13. Крэндалл, Померанс, 2011, Теорема 3.4.1, с. 154.
  14. Крэндалл, Померанс, 2011, Алгоритм 8.1.2, с. 438.

Литература

[править | править код]