Ймовірно просте число — це число, яке проходить тест простоти. Сильне ймовірно просте число — це число, яке проходить сильну версію тесту простоти. Сильне псевдопросте число — це складене число, яке проходить сильну версію тесту простоти.
Усі прості числа проходять цей тест, але незначна частка складених чисел також цей тест проходить, що робить їх «хибно простими».
На відміну від псевдопростих чисел Ферма, для яких існують числа, псевдопрості за всіма взаємно простими основами (числа Кармайкла), не існує складених чисел, сильних псевдопростих за всіма основами.
Формальне визначення Формально, непарне складене число n = d • 2s + 1 з непарним d називається сильним псевдопростим числом (Ферма) за основою a, якщо виконується одна з умов:
або
для деякого
(Якщо число n задовольняє вищенаведеним умовам і ми не знаємо, чи просте воно чи ні, точніше називати його сильним ймовірно простим за основою a. Якщо ж ми знаємо, що n не просте, можна використовувати термін сильне псевдопросте число.)
Визначення тривіально виконується, якщо , так що ці тривіальні випадки часто виключаються.
Річард Ґай помилково дав визначення тільки з першою умовою, але йому не задовольняють усі прості числа.
Властивості сильних псевдопростих чисел Сильне псевдопросте число за основою a завжди є , і псевдопростим Ферма за цією основою, але не всі псевдопрості Ейлера і Ферма є сильними псевдопростими. Числа Кармайкла можуть бути сильними псевдопростими за деякими основами, наприклад, 561 є сильними псевдопростим за основою 50, але не за всіма основами.
Складене число n є сильним псевдопростим за максимум чвертю всіх основ, менших від n. Таким чином, немає «сильних чисел Кармайкла», чисел, які є сильними псевдопростими для всіх основ. Отже, якщо задано випадкову основу, ймовірність, що число буде сильним псевдопростим за цією основою, не перевищує 1/4, що використовується в поширеному тесті Міллера — Рабіна. Проте, Арно навів 397-значне складене число, яке є сильним псевдопростим за будь-якою основою, меншою від 307. Одним зі способів уберегтися від оголошення таких чисел ймовірно простими полягає в комбінуванні тесту на сильне можливо просте число з тестом на псевдопросте число Люка, як у тесті Бейлі — Померанса — Селфриджа — Вогстаффа.
Існує нескінченно багато сильних псевдопростих за будь-якою конкретною основою.
Приклади Перші сильні псевдопрості за основою 2
2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, … ().
За основою 3
121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, … ().
За основою 5
781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, … ().
За основою 4 див. , а за основами від 6 до 100 див. послідовності від до .
Якщо перевіряти наведені вище умови за кількома основами, отримуємо більш потужний тест на простоту, ніж за використання тесту за однією основою. Наприклад, існує тільки 13 чисел, менших від 25·109, які є сильними псевдопростими за основами 2, 3 і 5 одночасно. Їх перераховано в таблиці 7 у статті Померанца і Селфриджа. Найменше таке число — 25326001. Це означає, що при n меншому від 25326001, якщо n є сильним ймовірно простим числом за основами 2, 3 і 5, число n є простим.
Число 3825123056546413051 є найменшим числом, що одночасно є сильним псевдопростим за 9 основами 2, 3, 5, 7, 11, 13, 17, 19 і 23. Так що при n меншому від 3825123056546413051, якщо n є сильним ймовірно простим за цими 9 основами, то n є простим.
За обережного вибору основи, що не є простою, можна побудувати навіть кращі тести. Наприклад, не існує складених чисел , сильних псевдопростих за всіма сімама основами 2, 325, 9375, 28178, 450775, 9780504 і 1795265022.
Найменше сильне псевдопросте за основою n nНайменшеnНайменшеnНайменшеnНайменше1933545653397492204734336665989312135967339925434136356825100957813796935101256217383970691021337253913371910351894039728510415991412173910545110942451741510615111334321759110791291449761510891138545481773910991415469787711011115168747657939111551615484980911265179492581911135718255049829114115199512583211155720215251848511692122153985211174922215455868511892316955987247119152425565588871209125217572589912115269585790911226527121591591912385289604819291124252915611593251259304962994931262531156352995189112793225649969512849
Примітки
Література