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

У математици, полупрост број ( такође се назива бипрост или 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. ( секвенца А001358 у ОЕИС ) . Полупрости бројеви који нису савршени квадрати се зову дискретни , или различити, полупрости бројеви .

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

Карактеристике[уреди | уреди извор]

Укупан број простих чинилаца Ω (н) за полупрост број н је два, по дефиницији . Полупрост број је или квадрат или бесквадратни број. Квадрат било ког простог број је полупрост број , тако да је највећи познати полупрост број увек квадрат највећег познатог простог броја , осим ако чиниоци полупростог броја нису познати . То је замисливо, али вероватно не и да начин да се докаже већи полупрости број а не знајући два чинилац.^[1] Сложен број н недељив за просте бројеве $\leq {\sqrt[{3}]{n}}$ је полупрост број. Различите методе , као што су елиптичке псеудо криве и Голдвосер - Килијанова ЕЦПП теорема се користе за креирање доказа, нечинилаца полупростих бројева са стотинама цифара .^[2] Ово се сматра новином , јер изградња њиховог метода може доказати слабост на факторизацији , и зато што је једноставније да се умножавају два проста броја заједно.

За полупросте бројеве n = pq вредности Еулеровог тотиент функције (број позитивних целих бројева мањих или једнаких за н су релативни прости бројеви н ) су посебно једноставне када се 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.

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

\sum _{\Omega (n)=2}{\frac {1}{n^{2}}}\approx 0.1407604

(sequence A117543 in OEIS)

\sum _{\Omega (n)=2}{\frac {1}{n(n-1)}}\approx 0.17105

(sequence A152447 in OEIS)

\sum _{\Omega (n)=2}{\frac {\ln n}{n^{2}}}\approx 0.28360

(sequence A154928 in OEIS)

Апликације[уреди | уреди извор]

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

У практичној криптографији , није довољно изабрати само било који полупрост број; добар број мора да избегне велики број познатих специјалних намена алгоритама који су у одређеној форми. Чиниоци 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 колона .