Semiprime

редактировать

В математике, полупростое число - это натуральное число, которое является произведением двух простых чисел. Два простых числа в произведении могут равняться друг другу, поэтому полупростые числа включают квадраты простых чисел. Поскольку простых чисел бесконечно много, существует также и полупростых чисел. Полупрозрачные частицы также называются бипраймами .

Содержание

  • 1 Примеры и варианты
  • 2 Формула для количества полупериодов
  • 3 Свойства
  • 4 Применения
  • 5 См. Также
  • 6 Ссылки
  • 7 Внешние ссылки

Примеры и варианты

Полупримеры меньше 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 {\ displaystyle k = 2}k = 2 из k {\ displaystyle k}к -почти простые, числа с точными k {\ displaystyle k}к простыми множителями. Однако в некоторых источниках термин «полупростое число» используется для обозначения большего набора numb ers, числа с не более чем двумя простыми делителями (включая единицу (1), простые числа и полупростые числа). Это:

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 году.

Пусть π 2 (n) {\ displaystyle \ pi _ {2} (n)}\ pi _ {2} (n) обозначают количество полупростых чисел, меньшее или равное n. Тогда

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

где π (x) {\ displaystyle \ pi (x)}\ pi (x) - функция подсчета простых чисел, и pk {\ displaystyle p_ {k}}p_ {k} обозначает k-е простое число.

Свойства

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

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

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

Этот расчет является важной частью приложения. полупростых в криптосистеме RSA. Для полупростого квадрата n = p 2 {\ displaystyle n = p ^ {2}}{\ displaystyle n = p ^ {2}} формула снова проста:

φ (n) = p (p - 1) = п - п. {\ displaystyle \ varphi (n) = p (p-1) = np.}{\ displaystyle \ varphi (n) = p (p-1) = np.}

Приложения

Сообщение Аресибо

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

В 1974 году сообщение Arecibo было отправлено с радиосигнал, направленный на звездное скопление . Он состоял из 1679 {\ displaystyle 1679}{\ displaystyle 1679} двоичных цифр, предназначенных для интерпретации как изображение 23 × 73 {\ displaystyle 23 \ times 73}{\ displaystyle 23 \ times 73} bitmap. Число 1679 = 23 ⋅ 73 {\ displaystyle 1679 = 23 \ cdot 73}{\ displaystyle 1679 = 23 \ cdot 73} было выбрано, потому что оно является полупростым и поэтому может быть преобразовано в прямоугольное изображение только двумя различными способами (23 ряда и 73 столбца, или 73 строки и 23 столбца).

См. также

Ссылки

  1. ^Sloane, NJA (ed.). «Последовательность A001358». Он-лайн энциклопедия целочисленных последовательностей. Фонд OEIS.
  2. ^Стюарт, Ян (2010). Кабинет математических любопытств профессора Стюарта. Профильные книги. п. 154. ISBN 9781847651280.
  3. ^О распределении полупростых чисел Шамиль Ишмухаметов
  4. ^Вайстейн, Эрик У. Полупростое число: из Wolfram MathWorld
  5. ^French, John Homer ( 1889 г.). Продвинутая арифметика для средних школ. Нью-Йорк: Харпер и братья. п. 53.
  6. ^ Коззенс, Маргарет; Миллер, Стивен Дж. (2013), Математика шифрования: элементарное введение, Mathematical World, 29, Американское математическое общество, стр. 237, ISBN 9780821883211
  7. ^«Запрос факторинга RSA больше не активен». RSA Laboratories. Архивировано из оригинала 27.07.2013.
  8. ^du Sautoy, Marcus (2011). Тайны чисел: Математическая одиссея повседневной жизни. Пресса Св. Мартина. п. 19. ISBN 9780230120280.

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

Последняя правка сделана 2021-06-07 09:48:38
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте