В математике, полупростое число - это натуральное число, которое является произведением двух простых чисел. Два простых числа в произведении могут равняться друг другу, поэтому полупростые числа включают квадраты простых чисел. Поскольку простых чисел бесконечно много, существует также и полупростых чисел. Полупрозрачные частицы также называются бипраймами .
Полупримеры меньше 100:
Полупростые числа, которые не являются квадратными числами, называются дискретными, различными или бесквадратными полупериодами:
Полупримеры - это случай из -почти простые, числа с точными простыми множителями. Однако в некоторых источниках термин «полупростое число» используется для обозначения большего набора numb ers, числа с не более чем двумя простыми делителями (включая единицу (1), простые числа и полупростые числа). Это:
Формула подсчета полупростых чисел была открыта Э. Ноэлем и Дж. Паносом в 2005 году.
Пусть обозначают количество полупростых чисел, меньшее или равное n. Тогда
где - функция подсчета простых чисел, и обозначает k-е простое число.
Полупростые числа не имеют составных чисел в качестве факторов, кроме самих себя. Например, число 26 является полупростым и его единственные множители - 1, 2, 13 и 26, из которых только 26 являются составными.
Для бесквадратного полупростого числа (с ) значение функции totient Эйлера (количество натуральных чисел, меньших или равных , которые являются относительно простое число до ) принимает простую форму
Этот расчет является важной частью приложения. полупростых в криптосистеме RSA. Для полупростого квадрата формула снова проста:
Полупростые числа очень полезны в области криптографии и теория чисел, особенно в криптографии с открытым ключом, где они используются RSA и генераторами псевдослучайных чисел, такими как Блюм Блюм Шуб. Эти методы основаны на том факте, что поиск двух больших простых чисел и их умножение (в результате получается полупростое число) вычислительно просты, тогда как поиск исходных множителей представляется затруднительным. В рамках RSA Factoring Challenge, RSA Security предложили призы за факторинг конкретных крупных полуприцепов, и было вручено несколько призов. Первоначальный запрос RSA Factoring Challenge был выпущен в 1991 году и был заменен в 2001 году новым RSA Factoring Challenge, который позже был отозван в 2007 году.
В 1974 году сообщение Arecibo было отправлено с радиосигнал, направленный на звездное скопление . Он состоял из двоичных цифр, предназначенных для интерпретации как изображение bitmap. Число было выбрано, потому что оно является полупростым и поэтому может быть преобразовано в прямоугольное изображение только двумя различными способами (23 ряда и 73 столбца, или 73 строки и 23 столбца).