Полупрост број

Полупрост број (исто така наречен двопрост или 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 ). Полупростите броеви кои не се совршени квадрати се нарекуваат дискретни или различни полупрости броеви.

По дефиниција, полупростите броеви немаат сложени множители освен себеси. На пример, бројот 26 е полупрост број и него единствени множители се 1, 2 , 13 и 26.

Својства

Вкупниот број на прости множители Ω(n) за полупрост број n е два, по дефиниција. Полупрост број е или квадратен или бесквадратен број. Квадратот на кој било прост број е полупрост број, па затоа најголемиот познат полупрост број е секогаш квадратот на најголемиот познат прост број, освен ако множителите на полупростиот број не се непознати. Тоа е замисливо, но веројатно не е начин да се докаже поголем полупрост број без да се знаат два множители. Сложен број n што е неделив за прости броеви ${\displaystyle \leq {\sqrt[{3}]{n}}}$ е полупрост број. Различни методи, како што се елиптичните псевдокриви и теоремата Голдвасер-Килијан ECPP, се користени за создавање докази за немножителите на полупростите броеви со стотици цифри. Ова се смета за ново, бидејќи изградбата на нивниот метод може да докаже слабост во факторизацијата, и затоа што е поедноставно меѓусебно да се помножат два прости броеви.

За полупрости броеви n = pq, вредностите на Ојлеровата тотиентна функција (бројот на позитивни цели броеви помали или еднакви на n се релативните прости броеви на n) се особено едноставни кога p и q се различни:

φ(n) = (p − 1) (q − 1) = p q − (p + q) + 1 = n − (p + q) + 1.

Ако p и q се исти,

φ(n) = φ(p²) = (p − 1) p = p² − p = n − p.

Концептот на почетната функција зета може да се приспособи на полупрости броеви, кои дефинираат константи како:

${\displaystyle \sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0.1407604}$ (sequence A117543 in OEIS)

${\displaystyle \sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0.17105}$ (sequence A152447 in OEIS)

${\displaystyle \sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0.28360}$ (sequence A154928 in OEIS)

Апликации

Полупростите броеви се многу корисни во областите на криптографијата и теоријата на броевите, особено во криптографијата со јавен клуч, каде што се користат RSA и генератори на псевдослучајни броеви како што е Блум Блум Шуб. Овие методи се потпираат на фактот дека наоѓањето на два големи прости броеви и нивното множење (што резултира со полупрости броеви) е пресметковно едноставно, додека наоѓањето на изворните множители изгледа тешко. Во факторскиот предизвик RSA, RSA сигурност понудил награди за специфични множители на големи полупрости броеви и неколку биле наградени. Последниот таков предизвик бил во 2007 година.^[1]

Во практичната криптографија, не е доволно да се избере кој било полупрост број. Добар број мора да избегне голем број познати алгоритми со посебна намена кои се од одреден облик. Множителите p и q на n треба да бидат многу големи, од ист ред на големина како квадратниот корен од n. Ова ги прави пребројувањето на делителите и Полард-Роовиот алгоритам непрактични. Во исто време, тие не мора да бидат преблизу, бидејќи бројот може брзо да се факторизира со методот на факторизација на Фертман. Бројот може да се избере така што ниту еден од p − 1, p + 1, q − 1, или q + 1 не е мазен број, и да се заштити од алгоритмот p − 1 на Полард или алгоритмот p + 1 на Вилијамс. Сепак, овие проверки не можат да ги земат предвид идните алгоритми или тајните на алгоритмите и ја воведуваат можноста дека бројот што се користи денес може да биде пробиен од алгоритми со посебна намена.

Во1974 година, со радиосигнал била испратена Арејсиб порака во ѕвеѕдено јато. Таа се состоела од 1679 двоични (бинарни) цифри со намера да се толкуваат како 23 × 73 битмапирани слики. Бројот 1679 = 23 × 73 бил избран бидејќи е полупрост број и затоа може да биде разложен само долу во ​​23 реда и 73 колони , или 73 реда и 23 колони.

Поврзано

• Ченова теорема
• Прост број
• Сложен број
• Клинест број