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

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

Натуральное число называется псевдопростым, если оно обладает некоторыми свойствами простых чисел, являясь тем не менее составным числом. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.

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

Содержание

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

Составное число n называется псевдопростым Ферма по основанию a, если a и n взаимнопросты и a^{n-1} \equiv 1\pmod{n}.[1]

Псевдопростые Ферма по основанию 2 образуют последовательность:

341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, … (последовательность A001567 в OEIS)

а по основанию 3 — последовательность:

91, 121, 286, 671, 703, 949, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, … (последовательность A005935 в OEIS)

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

Псевдопростые Эйлера — Якоби

Нечётное составное число n называется псевдопростым Эйлера — Якоби по основанию a, если оно удовлетворяет сравнению[2]

a^{(n-1)/2} \equiv \left( \frac{a}{n} \right) \pmod{n},

где \left( \frac{a}{n} \right)символ Якоби. Так как из этого сравнения следует, что a^{n-1} \equiv 1\pmod{n}, то всякое псевдопростое Эйлера — Якоби также является псевдопростым Ферма (по тому же основанию).

Псевдопростые Эйлера — Якоби по основанию 2 образуют последовательность:

561, 1105, 1729, 1905, 2047, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, … (последовательность A047713 в OEIS)

а по основанию 3 — последовательность:

121, 703, 1729, 1891, 2821, 3281, 7381, 8401, 8911, 10585, 12403, 15457, 15841, … (последовательность A048950 в OEIS)

Псевдопростые Фибоначчи

Основная статья: Псевдопростое число Фибоначчи (англ.)

Псевдопростые Люка

Основная статья: Псевдопростое число Люка (англ.)

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

Основная статья: Псевдопростое число Перрина (англ.)

Псевдопростые Фробениуса

Основная статья: Псевдопростое число Фробениуса (англ.)

См. также

Примечания

  1. Weisstein, Eric W. Fermat Pseudoprime (англ.) на сайте Wolfram MathWorld.
  2. Weisstein, Eric W. Euler-Jacobi Pseudoprime (англ.) на сайте Wolfram MathWorld.



Wikimedia Foundation. 2010.

Смотреть что такое "Псевдопростое число" в других словарях:

  • псевдопростое число Эйлера по основанию b — — [http://www.rfcmd.ru/glossword/1.8/index.php?a=index d=23] Тематики защита информации EN Euler pseudo prime to the base b …   Справочник технического переводчика

  • Сильно псевдопростое число — …   Википедия

  • Сильное псевдопростое число — …   Википедия

  • 323 (число) — 323 триста двадцать три 320 · 321 · 322 · 323 · 324 · 325 · 326 Факторизация: Римская запись: CCCXXIII Двоичное: 101000011 Восьмеричное: 503 …   Википедия

  • Малая теорема Ферма — Малая теорема Ферма  классическая теорема теории чисел, которая утверждает, что Если p простое число, и не делится на , то …   Википедия

  • Ферма малая теорема — Малая теорема Ферма классическая теорема теории чисел, которая утверждает что Если p простое число и целое a не делится на p, то a p 1 ≡ 1 (mod p)  (или a p 1 1 делится на p). Иная формулировка: Для любого простого …   Википедия

  • Тест Соловея — Штрассена вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью… …   Википедия

  • Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970 х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном.[1] Тест всегда корректно определяет, что простое число является простым, но для составных чисел с некоторой вероятностью он может… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»