Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

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

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

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

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

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

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

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

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

image

або

image для деякого image

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

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

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

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

Сильне псевдопросте число за основою a завжди є [en], [en] і за цією основою, але не всі псевдопрості Ейлера і Ферма є сильними псевдопростими. Числа Кармайкла можуть бути сильними псевдопростими за деякими основами, наприклад, 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, … (послідовність 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 див. image A020230, а за основами від 6 до 100 див. послідовності від image A020232 до image A020326.

Якщо перевіряти наведені вище умови за кількома основами, отримуємо більш потужний тест на простоту, ніж за використання тесту за однією основою. Наприклад, існує тільки 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 є простим.

За обережного вибору основи, що не є простою, можна побудувати навіть кращі тести. Наприклад, не існує складених чисел image, сильних псевдопростих за всіма сімама основами 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

Примітки

  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.

Література

  • Richard K. Guy. §A12 in Unsolved Problems in Number Theory // Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes. — 2nd. — New York : Springer-Verlag, 1994.
  • , John L. Selfridge, Samuel S. Wagstaff, Jr. The pseudoprimes to 25•109 // Mathematics of Computation. — 1980. — Т. 35, вип. 151 (7). — DOI:10.1090/S0025-5718-1980-0572872-7.
  • Louis Monier. Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms // Theoretical Computer Science. — 1980. — Т. 12 (17 червня). — DOI:10.1016/0304-3975(80)90007-9.
  • Michael O. Rabin. Probabilistic Algorithm for Testing Primality // Journal of Number Theory. — 1980. — Вип. 12 (17 червня).
  • F. Arnault. Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases // Journal of Symbolic Computation. — 1995. — Т. 20, вип. 2 (8). — DOI:10.1006/jsco.1995.1042.
  • Zhenxiang Zhang, Min Tang.  // Mathematics of Computation. — 2003. — Т. 72, вип. 244 (17 червня). — DOI:10.1090/S0025-5718-03-01545-X.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Jmovirno proste chislo ce chislo yake prohodit test prostoti Silne jmovirno proste chislo ce chislo yake prohodit silnu versiyu testu prostoti Silne psevdoproste chislo ce skladene chislo yake prohodit silnu versiyu testu prostoti Usi prosti chisla prohodyat cej test ale neznachna chastka skladenih chisel takozh cej test prohodit sho robit yih hibno prostimi Na vidminu vid psevdoprostih chisel Ferma dlya yakih isnuyut chisla psevdoprosti za vsima vzayemno prostimi osnovami chisla Karmajkla ne isnuye skladenih chisel silnih psevdoprostih za vsima osnovami Formalne viznachennyaFormalno neparne skladene chislo n d 2s 1 z neparnim d nazivayetsya silnim psevdoprostim chislom Ferma za osnovoyu a yaksho vikonuyetsya odna z umov a d 1 mod n displaystyle a d equiv 1 mod n abo a d 2 r 1 mod n displaystyle a d cdot 2 r equiv 1 mod n dlya deyakogo 0 r lt s displaystyle 0 leq r lt s Yaksho chislo n zadovolnyaye vishenavedenim umovam i mi ne znayemo chi proste vono chi ni tochnishe nazivati jogo silnim jmovirno prostim za osnovoyu a Yaksho zh mi znayemo sho n ne proste mozhna vikoristovuvati termin silne psevdoproste chislo Viznachennya trivialno vikonuyetsya yaksho a 1 mod n tak sho ci trivialni vipadki chasto viklyuchayutsya Richard Gaj pomilkovo dav viznachennya tilki z pershoyu umovoyu ale jomu ne zadovolnyayut usi prosti chisla Vlastivosti silnih psevdoprostih chiselSilne psevdoproste chislo za osnovoyu a zavzhdi ye en en i za ciyeyu osnovoyu ale ne vsi psevdoprosti Ejlera i Ferma ye silnimi psevdoprostimi Chisla Karmajkla mozhut buti silnimi psevdoprostimi za deyakimi osnovami napriklad 561 ye silnimi psevdoprostim za osnovoyu 50 ale ne za vsima osnovami Skladene chislo n ye silnim psevdoprostim za maksimum chvertyu vsih osnov menshih vid n Takim chinom nemaye silnih chisel Karmajkla chisel yaki ye silnimi psevdoprostimi dlya vsih osnov Otzhe yaksho zadano vipadkovu osnovu jmovirnist sho chislo bude silnim psevdoprostim za ciyeyu osnovoyu ne perevishuye 1 4 sho vikoristovuyetsya v poshirenomu testi Millera Rabina Prote Arno naviv 397 znachne skladene chislo yake ye silnim psevdoprostim za bud yakoyu osnovoyu menshoyu vid 307 Odnim zi sposobiv uberegtisya vid ogoloshennya takih chisel jmovirno prostimi polyagaye v kombinuvanni testu na silne mozhlivo proste chislo z testom na yak u Isnuye neskinchenno bagato silnih psevdoprostih za bud yakoyu konkretnoyu osnovoyu PrikladiPershi silni psevdoprosti za osnovoyu 2 2047 3277 4033 4681 8321 15841 29341 42799 49141 52633 65281 74665 80581 85489 88357 90751 poslidovnist A001262 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Za osnovoyu 3 121 703 1891 3281 8401 8911 10585 12403 16531 18721 19345 23521 31621 44287 47197 55969 63139 74593 79003 82513 87913 88573 97567 poslidovnist A020229 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Za osnovoyu 5 781 1541 5461 5611 7813 13021 14981 15751 24211 25351 29539 38081 40501 44801 53971 79381 poslidovnist A020231 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Za osnovoyu 4 div A020230 a za osnovami vid 6 do 100 div poslidovnosti vid A020232 do A020326 Yaksho pereviryati navedeni vishe umovi za kilkoma osnovami otrimuyemo bilsh potuzhnij test na prostotu nizh za vikoristannya testu za odniyeyu osnovoyu Napriklad isnuye tilki 13 chisel menshih vid 25 109 yaki ye silnimi psevdoprostimi za osnovami 2 3 i 5 odnochasno Yih pererahovano v tablici 7 u statti Pomeranca i Selfridzha Najmenshe take chislo 25326001 Ce oznachaye sho pri n menshomu vid 25326001 yaksho n ye silnim jmovirno prostim chislom za osnovami 2 3 i 5 chislo n ye prostim Chislo 3825123056546413051 ye najmenshim chislom sho odnochasno ye silnim psevdoprostim za 9 osnovami 2 3 5 7 11 13 17 19 i 23 Tak sho pri n menshomu vid 3825123056546413051 yaksho n ye silnim jmovirno prostim za cimi 9 osnovami to n ye prostim Za oberezhnogo viboru osnovi sho ne ye prostoyu mozhna pobuduvati navit krashi testi Napriklad ne isnuye skladenih chisel lt 2 64 displaystyle lt 2 64 silnih psevdoprostih za vsima simama osnovami 2 325 9375 28178 450775 9780504 i 1795265022 Najmenshe silne psevdoproste za osnovoyu nn Najmenshe n Najmenshe n Najmenshe n Najmenshe 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 49PrimitkiGuy 1994 s 27 30 Pomerance Selfridge Wagstaff 1980 s 1003 1026 Monier 1980 s 97 108 Rabin 1980 s 128 138 Arnault 1995 s 151 161 Zhang Tang 2003 s 2085 2097 SPRP Records Procitovano 3 chervnya 2015 LiteraturaRichard K Guy A12 in Unsolved Problems in Number Theory Pseudoprimes Euler Pseudoprimes Strong Pseudoprimes 2nd New York Springer Verlag 1994 John L Selfridge Samuel S Wagstaff Jr The pseudoprimes to 25 109 Mathematics of Computation 1980 T 35 vip 151 7 DOI 10 1090 S0025 5718 1980 0572872 7 Louis Monier Evaluation and Comparison of Two Efficient Probabilistic Primality Testing Algorithms Theoretical Computer Science 1980 T 12 17 chervnya DOI 10 1016 0304 3975 80 90007 9 Michael O Rabin Probabilistic Algorithm for Testing Primality Journal of Number Theory 1980 Vip 12 17 chervnya F Arnault Constructing Carmichael Numbers Which Are Strong Pseudoprimes to Several Bases Journal of Symbolic Computation 1995 T 20 vip 2 8 DOI 10 1006 jsco 1995 1042 Zhenxiang Zhang Min Tang Mathematics of Computation 2003 T 72 vip 244 17 chervnya DOI 10 1090 S0025 5718 03 01545 X

Дата публікації:
Топ