Псевдопростой

Псевдопростое число — это вероятное простое число (целое число , обладающее общим свойством для всех простых чисел ), которое на самом деле не является простым. Псевдопростые числа классифицируются в зависимости от того, какому свойству простых чисел они удовлетворяют.

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

Псевдопростые числа имеют первостепенное значение в криптографии с открытым ключом , которая использует сложность разложения больших чисел на их простые множители. В 1988 году Карл Померанс подсчитал, что разложение числа из 144 цифр обойдется в 10 миллионов долларов, а разложение числа из 200 цифр — в 100 миллиардов долларов (сегодняшние затраты значительно ниже, но все еще непомерно высоки). ^[1]^[2] Но поиск двух больших простых чисел, необходимых для такого использования, также обходится дорого, поэтому используются различные вероятностные тесты на простоту , некоторые из которых в редких случаях ошибочно выдают составные числа вместо простых чисел. С другой стороны, детерминированные тесты на простоту, такие как тест на простоту AKS , не дают ложных срабатываний ; поэтому по отношению к ним нет псевдопростых чисел.

Псевдопростые числа Ферма [ править ]

Маленькая теорема Ферма утверждает, что если $p$ простое и $a$ взаимно просто с $p$ , то $a р -1 -$ делится на p $.$ 1 Для целого числа $a > 1$ , если составное целое число $x$ делит $a х -1 - 1$ , то $x$ называется псевдопростым числом Ферма по основанию $a$ . Отсюда следует, что если $x$ является псевдопростым числом Ферма с основанием $a$ , то $x$ взаимно просто с $a$ . В некоторых источниках используются варианты этого определения, например, позволяющие считать псевдопростыми только нечетные числа. ^[3]

Целое число $x$ , которое является псевдопростым числом Ферма для всех значений $a$ , взаимно простых с $x,$ называется числом Кармайкла .

Классы [ править ]

Ссылки [ править ]

^ Клоусон, Кэлвин К. (1996). Математические загадки: красота и магия чисел . Кембридж: Персей. п. 195. ИСБН 0-7382-0259-2 .
^ Ципра, Барри Артур (23 декабря 1988 г.). «ПК учитывают число самых разыскиваемых людей». Наука . 242 (4886): 1634–1635. Бибкод : 1988Sci...242.1634C . дои : 10.1126/science.242.4886.1634 . ПМИД 17730568 .
^ Вайсштейн, Эрик В. «Псевдопростой Ферма» . Математический мир .

[1] Клоусон, Кэлвин К. (1996). Математические загадки: красота и магия чисел . Кембридж: Персей. п. 195. ИСБН 0-7382-0259-2 .

[2] Ципра, Барри Артур (23 декабря 1988 г.). «ПК учитывают число самых разыскиваемых людей». Наука . 242 (4886): 1634–1635. Бибкод : 1988Sci...242.1634C . дои : 10.1126/science.242.4886.1634 . ПМИД 17730568 .

[3] Вайсштейн, Эрик В. «Псевдопростой Ферма» . Математический мир .

[1]

[2]

[3]

v т и Классы простых чисел
By formula	Fermat ( $2 2 n + 1$ ) Mersenne ( $2 p - 1$ ) Double Mersenne ( $2 2 p -1 - 1$ ) Wagstaff $(2 p + 1)/3$ Proth ( $k \cdot2 n + 1$ ) Factorial ( $n! \pm 1$ ) Primorial ( $p n # \pm 1$ ) Euclid ( $p n # + 1$ ) Pythagorean ( $4 n + 1$ ) Pierpont ( $2 m \cdot3 n + 1$ ) Quartan ( $x 4 + y 4$ ) Solinas ( $2 m \pm 2 n \pm 1$ ) Cullen ( $n \cdot2 n + 1$ ) Woodall ( $n \cdot2 n - 1$ ) Cuban ( $x 3 - y 3)/(x - y$ ) Leyland ( $x y + y x$ ) Thabit ( $3\cdot2 n - 1$ ) Williams ( $(b -1)\cdot b n - 1$ ) Mills ( $⌊ A 3 n ⌋$ )
By integer sequence	Fibonacci Lucas Pell Newman–Shanks–Williams Perrin
By property	Wieferich (pair) Wall–Sun–Sun Wolstenholme Wilson Lucky Fortunate Ramanujan Pillai Regular Strong Stern Supersingular (elliptic curve) Supersingular (moonshine theory) Good Super Higgs Highly cototient Unique
Base-dependent	Palindromic Emirp Repunit $(10 n - 1)/9$ Permutable Circular Truncatable Minimal Delicate Primeval Full reptend Unique Happy Self Smarandache–Wellin Strobogrammatic Dihedral Tetradic
Patterns	Twin ( $p, p + 2$ ) Bi-twin chain ( $n \pm 1, 2 n \pm 1, 4 n \pm 1, \dots$ ) Triplet ( $p, p + 2 or p + 4, p + 6$ ) Quadruplet ( $p, p + 2, p + 6, p + 8$ ) k-tuple Cousin ( $p, p + 4$ ) Sexy ( $p, p + 6$ ) Chen Sophie Germain/Safe ( $p, 2 p + 1$ ) Cunningham ( $p, 2 p \pm 1, 4 p \pm 3, 8 p \pm 7, ...$ ) Arithmetic progression ( $p + a\cdotn, n = 0, 1, 2, 3, ...$ ) Balanced ( $consecutive p - n, p, p + n$ )
By size	Mega (1,000,000+ digits) Largest known list
Complex numbers	Eisenstein prime Gaussian prime
Composite numbers	Pseudoprime Catalan Elliptic Euler Euler–Jacobi Fermat Frobenius Lucas Perrin Somer–Lucas Strong Carmichael number Almost prime Semiprime Sphenic number Interprime Pernicious
Related topics	Probable prime Industrial-grade prime Illegal prime Formula for primes Prime gap
First 60 primes	2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269 271 277 281
List of prime numbers