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

Произведение двух простых чисел

В математике полупростое число — это натуральное число , которое является произведением ровно двух простых чисел . Два простых числа в произведении могут равняться друг другу, поэтому полупростые числа включают в себя квадраты простых чисел. Поскольку существует бесконечно много простых чисел, существует также бесконечно много полупростых чисел. Полупростые числа также называются бипростыми , ^[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 )

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

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 году. Обозначим через число полупростых чисел, меньших или равных n. Затем ${\displaystyle \pi _{2}(n)}$

$${\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi ({\sqrt {n}})}[\pi (n/p_{k})-k+1]}$$

функция подсчета простых чиселk-^[4] ${\displaystyle \pi (x)}$ ${\displaystyle p_{k}}$

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

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

Для полупростого числа без квадратов (с ) значение функции Эйлера (количество натуральных чисел, меньших или равных этому, являются относительно простыми с ) принимает простую форму ${\displaystyle n=pq}$ ${\displaystyle p\neq q}$ ${\displaystyle \varphi (n)}$ ${\displaystyle n}$ ${\displaystyle n}$

$${\displaystyle \varphi (n)=(p-1)(q-1)=n-(p+q)+1.}$$

криптосистеме RSA^[6][6] ${\displaystyle n=p^{2}}$

$${\displaystyle \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 году сообщение Аресибо было отправлено с радиосигналом, направленным на звездное скопление . Он состоял из двоичных цифр, предназначенных для интерпретации как растровое изображение. Число было выбрано потому, что оно полупростое и, следовательно, его можно расположить в прямоугольное изображение только двумя различными способами (23 строки и 73 столбца или 73 строки и 23 столбца). ^[8] ${\displaystyle 1679}$ ${\displaystyle 23\times 73}$ ${\displaystyle 1679=23\cdot 73}$

Смотрите также

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

Рекомендации

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

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

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