Полупервоклассный

В математике число полупростое — это натуральное число , которое является произведением ровно двух простых чисел . Два простых числа в произведении могут равняться друг другу, поэтому полупростые числа включают в себя квадраты простых чисел.Поскольку существует бесконечно много простых чисел, существует также бесконечно много полупростых чисел. Полупростые числа также называют бипростыми числами . ^[1] поскольку они включают в себя два простых числа или вторые числа , ^[2] по аналогии с тем, как «простой» означает «первый».

Примеры и вариации

Полупростые числа меньше 100:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, 46, 49, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94 и 95 (последовательность A001358 в OEIS )

Полупростые числа, не являющиеся квадратными числами, называются дискретными, различными или бесквадратными полупростыми числами:

6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39, 46, 51, 55, 57, 58, 62, 65, 69, 74, 77, 82, 85, 86, 87, 91, 93, 94, 95, ... (последовательность A006881 в OEIS )

Полупростые числа - это тот случай $k=2$ принадлежащий $k$ - почти простые числа , числа с точностью $k$ основные факторы. Однако в некоторых источниках слово «полупростое» используется для обозначения большего набора чисел, чисел с не более чем двумя простыми делителями (включая единицу (1), простые и полупростые числа). ^[3] Это:

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 37, 38, 39, 41, 43, 46, 47, 49, ... (последовательность A037143 в OEIS )

Формула количества полупростых чисел

Полупростая формула счета была открыта Э. Ноэлем и Г. Паносом в 2005 г. Пусть $\pi _{2}(n)$ обозначают количество полупростых чисел, меньших или равных n. Затем $\pi _{2}(n)=\sum _{k=1}^{\pi ({\sqrt {n}})}[\pi (n/p_{k})-k+1]$ где $\pi (x)$ — функция подсчета простых чисел и $p_{k}$ обозначает k-е простое число. ^[4]

Характеристики

Полупростые числа не имеют составных чисел в качестве множителей, кроме самих себя. ^[5] Например, число 26 является полупростым, и его делителями являются только 1, 2, 13 и 26, из которых только 26 является составным.

Для бесквадратного полупростого числа $n=pq$ (с $p\neq q$ )значение функции Эйлера $\varphi (n)$ (количество натуральных чисел, меньших или равных $n$ которые относительно просты для $n$ ) принимает простую форму $\varphi (n)=(p-1)(q-1)=n-(p+q)+1.$ Этот расчет является важной частью применения полупростых чисел в криптосистеме RSA . ^[6]Для квадратного полупростого числа $n=p^{2}$ , формула снова проста: ^[6] $\varphi (n)=p(p-1)=n-p.$

Приложения

Полупростые числа очень полезны в области криптографии и теории чисел , особенно в криптографии с открытым ключом , где они используются RSA и генераторами псевдослучайных чисел, такими как Blum Blum Shub . Эти методы основаны на том факте, что найти два больших простых числа и умножить их вместе (что дает полупростое число) вычислительно просто, тогда как найти исходные множители кажется трудным. В конкурсе RSA Factoring Challenge компания RSA Security предложила призы за факторинг конкретных крупных полупростых компаний, и было вручено несколько призов. Первоначальный конкурс RSA Factoring Challenge был выпущен в 1991 году и был заменен в 2001 году новым конкурсом RSA Factoring Challenge, который позже был отменен в 2007 году. ^[7]

В 1974 году сообщение Аресибо было отправлено с радиосигналом, направленным на звездное скопление . Он состоял из $1679$ двоичные цифры, предназначенные для интерпретации как $23\times 73$ растровое изображение. Число $1679=23\cdot 73$ был выбран потому, что он является полупростым и поэтому может быть преобразован в прямоугольное изображение только двумя различными способами (23 строки и 73 столбца или 73 строки и 23 столбца). ^[8]

См. также

Теорема Чена
Сфеническое число — произведение трёх различных простых чисел.

Ссылки

^ Слоан, Нью-Джерси (ред.). «Последовательность A001358» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.
^ Новицкий, Анджей (01 июля 2013 г.), Вторые числа в арифметической прогрессии , arXiv : 1306,6424
^ Стюарт, Ян (2010). Кабинет математических раритетов профессора Стюарта . Профильные книги. п. 154. ИСБН 9781847651280 .
^ Ишмухаметов, Ш. Т.; Шарифуллина, Ф.Ф. (2014). «О распределении полупростых чисел». Русская математика . 58 (8): 43–48. дои : 10.3103/S1066369X14080052 . МР 3306238 . S2CID 122410656 .
^ Френч, Джон Гомер (1889). Продвинутая арифметика для средних школ . Нью-Йорк: Харпер и братья. п. 53.
^ Jump up to: Перейти обратно: ^а ^б Коззенс, Маргарет; Миллер, Стивен Дж. (2013). Математика шифрования: элементарное введение . Математический мир. Том. 29. Американское математическое общество. п. 237. ИСБН 9780821883211 .
^ «Конкурс RSA Factoring Challenge больше не активен» . Лаборатории РСА. Архивировано из оригинала 27 июля 2013 г.
^ дю Сотуа, Маркус (2011). Загадки чисел: математическая одиссея через повседневную жизнь . Пресса Святого Мартина. п. 19. ISBN 9780230120280 .

Внешние ссылки

Вайсштейн, Эрик В. «Полупростой» . Математический мир .

[1] Слоан, Нью-Джерси (ред.). «Последовательность A001358» . Электронная энциклопедия целочисленных последовательностей . Фонд ОЭИС.

[2] Новицкий, Анджей (01 июля 2013 г.), Вторые числа в арифметической прогрессии , arXiv : 1306,6424

[3] Стюарт, Ян (2010). Кабинет математических раритетов профессора Стюарта . Профильные книги. п. 154. ИСБН 9781847651280 .

[4] Ишмухаметов, Ш. Т.; Шарифуллина, Ф.Ф. (2014). «О распределении полупростых чисел». Русская математика . 58 (8): 43–48. дои : 10.3103/S1066369X14080052 . МР 3306238 . S2CID 122410656 .

[5] Френч, Джон Гомер (1889). Продвинутая арифметика для средних школ . Нью-Йорк: Харпер и братья. п. 53.

[moe-6] Jump up to: Перейти обратно: ^а ^б Коззенс, Маргарет; Миллер, Стивен Дж. (2013). Математика шифрования: элементарное введение . Математический мир. Том. 29. Американское математическое общество. п. 237. ИСБН 9780821883211 .

[7] «Конкурс RSA Factoring Challenge больше не активен» . Лаборатории РСА. Архивировано из оригинала 27 июля 2013 г.

[8] дю Сотуа, Маркус (2011). Загадки чисел: математическая одиссея через повседневную жизнь . Пресса Святого Мартина. п. 19. ISBN 9780230120280 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

v т и Наборы целых чисел на основе делимости
Overview	Integer factorization Divisor Unitary divisor Divisor function Prime factor Fundamental theorem of arithmetic
Factorization forms	Prime Composite Semiprime Pronic Sphenic Square-free Powerful Perfect power Achilles Smooth Regular Rough Unusual
Constrained divisor sums	Perfect Almost perfect Quasiperfect Multiply perfect Hemiperfect Hyperperfect Superperfect Unitary perfect Semiperfect Practical Erdős–Nicolas
With many divisors	Abundant Primitive abundant Highly abundant Superabundant Colossally abundant Highly composite Superior highly composite Weird
Aliquot sequence-related	Untouchable Amicable (Triple) Sociable Betrothed
Base-dependent	Equidigital Extravagant Frugal Harshad Polydivisible Smith
Other sets	Arithmetic Deficient Friendly Solitary Sublime Harmonic divisor Descartes Refactorable Superperfect

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