Полупростой

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

В математике полупростое число — это натуральное число , которое является произведением ровно двух простых чисел . Два простых числа в произведении могут быть равны друг другу, поэтому полупростые числа включают квадраты простых чисел. Поскольку существует бесконечно много простых чисел, существует также бесконечно много полупростых чисел. Полупростые числа также называются бипростыми числами , ^[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 . Тогда где — функция подсчета простых чисел , а обозначает k- е простое число. ^[4] ${\displaystyle \pi _{2}(n)}$ $${\displaystyle \pi _{2}(n)=\sum _{k=1}^{\pi \left({\sqrt {n}}\right)}\left[\pi \left({\frac {n}{p_{k}}}\right)-k+1\right]}$$ ${\displaystyle \pi (x)}$ ${\displaystyle p_{k}}$

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

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

Для полупростого числа, свободного от квадратов (с ), значение функции Эйлера (количество положительных целых чисел, меньших или равных , которые взаимно просты с ) принимает простую форму Это вычисление является важной частью применения полупростых чисел в криптосистеме RSA . ^[6] Для квадратного полупростого числа формула снова проста: ^[6] ${\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.}$$ ${\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 году на New RSA Factoring Challenge, который был позже отозван в 2007 году. ^[7]

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

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

• Теорема Чена
• Сфеническое число , произведение трех различных простых чисел
• Проблема четности (теория решета)

Ссылки

1. Sloane, N. J. A. (ред.). "Последовательность A001358". Онлайновая энциклопедия целочисленных последовательностей . Фонд OEIS.
2. Новицкий, Анджей (01 июля 2013 г.), Вторые числа в арифметической прогрессии , arXiv : 1306.6424
3. Стюарт, Ян (2010). Кабинет математических редкостей профессора Стюарта. Profile Books. стр. 154. ISBN 9781847651280.
4. Ишмухаметов, Ш. Т.; Шарифуллина, Ф. Ф. (2014). «О распределении полупростых чисел». Российская математика . 58 (8): 43–48. doi :10.3103/S1066369X14080052. MR  3306238. S2CID  122410656.
5. Френч, Джон Хомер (1889). Продвинутая арифметика для средних школ. Нью-Йорк: Harper & Brothers. С. 53.
6. Cozzens, Margaret; Miller, Steven J. (2013). Математика шифрования: элементарное введение. Mathematical World. Том 29. Американское математическое общество. стр. 237. ISBN 9780821883211.
7. "Конкурс RSA Factoring Challenge больше не действует". RSA Laboratories. Архивировано из оригинала 27.07.2013.
8. du Sautoy, Marcus (2011). Загадки чисел: математическая одиссея через повседневную жизнь. St. Martin's Press. стр. 19. ISBN 9780230120280.

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

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