Сильне псевдопросте число

Ймовірно просте число — це число, яке проходить тест простоти. Сильне ймовірно просте число — це число, яке проходить сильну версію тесту простоти. Сильне псевдопросте число — це складене число, яке проходить сильну версію тесту простоти.

Усі прості числа проходять цей тест, але незначна частка складених чисел також цей тест проходить, що робить їх «хибно простими».

На відміну від псевдопростих чисел Ферма, для яких існують числа, псевдопрості за всіма взаємно простими основами (числа Кармайкла), не існує складених чисел, сильних псевдопростих за всіма основами.

Формальне визначення

Формально, непарне складене число n = d • 2^s + 1 з непарним d називається сильним псевдопростим числом (Ферма) за основою a, якщо виконується одна з умов:

$a^d\equiv 1modn$

або

$a^{d\cdot 2^r}\equiv -1modn$ для деякого $0\le r<s.$

(Якщо число n задовольняє вищенаведеним умовам і ми не знаємо, чи просте воно чи ні, точніше називати його сильним ймовірно простим за основою a. Якщо ж ми знаємо, що n не просте, можна використовувати термін сильне псевдопросте число.)

Визначення тривіально виконується, якщо Шаблон:Math, так що ці тривіальні випадки часто виключаються.

Річард Ґай помилково дав визначення тільки з першою умовою, але йому не задовольняють усі прості числаШаблон:Sfn.

Властивості сильних псевдопростих чисел

Сильне псевдопросте число за основою a завжди є Шаблон:Не перекладено, Шаблон:Не перекладеноШаблон:Sfn і псевдопростим Ферма за цією основою, але не всі псевдопрості Ейлера і Ферма є сильними псевдопростими. Числа Кармайкла можуть бути сильними псевдопростими за деякими основами, наприклад, 561 є сильними псевдопростим за основою 50, але не за всіма основами.

Складене число n є сильним псевдопростим за максимум чвертю всіх основ, менших від nШаблон:SfnШаблон:Sfn. Таким чином, немає «сильних чисел Кармайкла», чисел, які є сильними псевдопростими для всіх основ. Отже, якщо задано випадкову основу, ймовірність, що число буде сильним псевдопростим за цією основою, не перевищує 1/4, що використовується в поширеному тесті Міллера — Рабіна. Проте, АрноШаблон:Sfn навів 397-значне складене число, яке є сильним псевдопростим за будь-якою основою, меншою від 307. Одним зі способів уберегтися від оголошення таких чисел ймовірно простими полягає в комбінуванні тесту на сильне можливо просте число з тестом на псевдопросте число Люка, як у тесті Бейлі — Померанса — Селфриджа — Вогстаффа.

Існує нескінченно багато сильних псевдопростих за будь-якою конкретною основоюШаблон:Sfn.

Приклади

Перші сильні псевдопрості за основою 2

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, … (Шаблон:OEIS).

За основою 3

121, 703, 1891, 3281, 8401, 8911, 10585, 12403, 16531, 18721, 19345, 23521, 31621, 44287, 47197, 55969, 63139, 74593, 79003, 82513, 87913, 88573, 97567, … (Шаблон:OEIS).

За основою 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, … (Шаблон:OEIS).

За основою 4 див. Шаблон:OEIS2C, а за основами від 6 до 100 див. послідовності від Шаблон:OEIS2C до Шаблон:OEIS2C.

Якщо перевіряти наведені вище умови за кількома основами, отримуємо більш потужний тест на простоту, ніж за використання тесту за однією основою. Наприклад, існує тільки 13 чисел, менших від 25·10⁹, які є сильними псевдопростими за основами 2, 3 і 5 одночасно. Їх перераховано в таблиці 7 у статті Померанца і СелфриджаШаблон:Sfn. Найменше таке число — 25326001. Це означає, що при n меншому від 25326001, якщо n є сильним ймовірно простим числом за основами 2, 3 і 5, число n є простим.

Число 3825123056546413051 є найменшим числом, що одночасно є сильним псевдопростим за 9 основами 2, 3, 5, 7, 11, 13, 17, 19 і 23Шаблон:Sfn. Так що при n меншому від 3825123056546413051, якщо n є сильним ймовірно простим за цими 9 основами, то n є простим.

За обережного вибору основи, що не є простою, можна побудувати навіть кращі тести. Наприклад, не існує складених чисел $<2^{64}$, сильних псевдопростих за всіма сімама основами 2, 325, 9375, 28178, 450775, 9780504 і 1795265022.

Найменше сильне псевдопросте за основою n

n	Найменше	n	Найменше	n	Найменше	n	Найменше
1	9	33	545	65	33	97	49
2	2047	34	33	66	65	98	9
3	121	35	9	67	33	99	25
4	341	36	35	68	25	100	9
5	781	37	9	69	35	101	25
6	217	38	39	70	69	102	133
7	25	39	133	71	9	103	51
8	9	40	39	72	85	104	15
9	91	41	21	73	9	105	451
10	9	42	451	74	15	106	15
11	133	43	21	75	91	107	9
12	91	44	9	76	15	108	91
13	85	45	481	77	39	109	9
14	15	46	9	78	77	110	111
15	1687	47	65	79	39	111	55
16	15	48	49	80	9	112	65
17	9	49	25	81	91	113	57
18	25	50	49	82	9	114	115
19	9	51	25	83	21	115	57
20	21	52	51	84	85	116	9
21	221	53	9	85	21	117	49
22	21	54	55	86	85	118	9
23	169	55	9	87	247	119	15
24	25	56	55	88	87	120	91
25	217	57	25	89	9	121	15
26	9	58	57	90	91	122	65
27	121	59	15	91	9	123	85
28	9	60	481	92	91	124	25
29	15	61	15	93	25	125	9
30	49	62	9	94	93	126	25
31	15	63	529	95	1891	127	9
32	25	64	9	96	95	128	49

Література

• Шаблон:Книга
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття
• Шаблон:Стаття