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

У математици, полупрост број ( такође се назива бипрост или 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] Сложен број н недељив за просте бројеве   је полупрост број. Различите методе , као што су елиптичке псеудо криве и Голдвосер - Килијанова ЕЦПП теорема се користе за креирање доказа, нечинилаца полупростих бројева са стотинама цифара .[2] Ово се сматра новином , јер изградња њиховог метода може доказати слабост на факторизацији , и зато што је једноставније да се умножавају два проста броја заједно.

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

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

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

φ(n) = φ(p2) = (p − 1) p = p2p = np.

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

  (sequence A117543 in OEIS)
  (sequence A152447 in OEIS)
  (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 колона .

Види јошУреди

РеференцеУреди

  1. ^ Chris Caldwell, The Prime Glossary: semiprime at The Prime Pages.
  2. ^ Broadhurst, David (12 March 2005).
  3. ^ Information Security, Governance, Risk, and Compliance - EMC Архивирано на сајту Wayback Machine (7. мај 2013).

Спољашње везеУреди

  • Weisstein, Eric W., "Semiprime", MathWorld