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

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

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

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

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

[ред. | ред. код]

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

або

для деякого

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

Визначення тривіально виконується, якщо a ≡ ±1 mod n, так що ці тривіальні випадки часто виключаються.

Річард Ґай помилково дав визначення тільки з першою умовою, але йому не задовольняють усі прості числа[1].

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

[ред. | ред. код]

Сильне псевдопросте число за основою a завжди є псевдопростим Ейлера — Якобі[en], псевдопростим Ейлера[en][2] і псевдопростим Ферма за цією основою, але не всі псевдопрості Ейлера і Ферма є сильними псевдопростими. Числа Кармайкла можуть бути сильними псевдопростими за деякими основами, наприклад, 561 є сильними псевдопростим за основою 50, але не за всіма основами.

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

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

Приклади

[ред. | ред. код]

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

2047, 3277, 4033, 4681, 8321, 15841, 29341, 42799, 49141, 52633, 65281, 74665, 80581, 85489, 88357, 90751, … (послідовність A001262 з Онлайн енциклопедії послідовностей цілих чисел, 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, … (послідовність A020229 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

За основою 5

781, 1541, 5461, 5611, 7813, 13021, 14981, 15751, 24211, 25351, 29539, 38081, 40501, 44801, 53971, 79381, … (послідовність A020231 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

За основою 4 див. OEISA020230, а за основами від 6 до 100 див. послідовності від OEISA020232 до OEISA020326.

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

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

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

Найменше сильне псевдопросте за основою 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

Примітки

[ред. | ред. код]
  1. Guy, 1994, с. 27-30.
  2. а б в Pomerance, Selfridge, Wagstaff, 1980, с. 1003–1026.
  3. Monier, 1980, с. 97-108.
  4. Rabin, 1980, с. 128-138.
  5. Arnault, 1995, с. 151–161.
  6. Zhang, Tang, 2003, с. 2085–2097.
  7. SPRP Records. Процитовано 3 червня 2015.

Література

[ред. | ред. код]