Poluprost broj

U matematici, poluprost broj ( takođe se naziva biprost ili 2 - skoro prost broj  , ili pku broj) je prirodni broj koji je proizvod dva (ne obavezno različita) prosta broja. U poluprosti brojevi manji od 100 su 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 , i 95. ( sekvenca A001358 u OEIS ) . Poluprosti brojevi koji nisu savršeni kvadrati se zovu diskretni , ili različiti, poluprosti brojevi . 

 Po definiciji , poluprosti brojevi nemaju složene činoce osim sebe . Na primer, broj 26 je poluprost broj i njegovi jedini činioci su 1, 2 , 13, i 26.

Karakteristike

Ukupan broj prostih činilaca Ω (n) za poluprost broj n je dva, po definiciji . Poluprost broj je ili kvadrat ili beskvadratni broj. Kvadrat bilo kog prostog broj je poluprost broj , tako da je najveći poznati poluprost broj uvek kvadrat najvećeg poznatog prostog broja , osim ako činioci poluprostog broja nisu poznati . To je zamislivo, ali verovatno ne i da način da se dokaže veći poluprosti broj a ne znajući dva činilac. Složen broj n nedeljiv za proste brojeve $\leq {\sqrt[{3}]{n}}$ je poluprost broj. Različite metode , kao što su eliptičke pseudo krive i Goldvoser - Kilijanova ECPP teorema se koriste za kreiranje dokaza, nečinilaca poluprostih brojeva sa stotinama cifara . Ovo se smatra novinom , jer izgradnja njihovog metoda može dokazati slabost na faktorizaciji , i zato što je jednostavnije da se umnožavaju dva prosta broja zajedno.

Za poluproste brojeve n = pq vrednosti Eulerovog totient funkcije (broj pozitivnih celih brojeva manjih ili jednakih za n su relativni prosti brojevi n ) su posebno jednostavne kada se  p i q razlikuju : 

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

Ako su p i q isti , 

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

Koncept početne funkcije zeta se može prilagoditi poluprostim brojevima, koji definišu konstante kao

$\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)

Aplikacije

Poluprosti brojevi su veoma korisni u oblasti kriptografije i teorije brojeva , posebno u kriptografiju javnog ključa , gde se koristi RSA i generatora pseudoslučajnih brojeva kao što je Blum Blum Šub . Ove metode se oslanjaju na činjenicu da je pronalaženje dva velika prosta brojeva i njihovo množenje ( što je rezultiralo poluproste brojeve) računski jednostavno, a pronalaženje originalnih činilaca izgleda teško. U RSA činilačnom izazovu, RSA sigurnost je nudio nagrade za specifičnih činilačne velike poluproste brojeve i nekoliko ih je i dodeljeno. Poslednji takav izazov je bio 2007.godine.

U praktičnoj kriptografiji , nije dovoljno izabrati samo bilo koji poluprost broj; dobar broj mora da izbegne veliki broj poznatih specijalnih namena algoritama koji su u određenoj formi. Činioci p i q  n i treba da budu vrlo veliki, istog reda veličine kao i kvadratnog korena iz n ; ovo čini prebrajanje delilaca i Polard Roov algoritam nepraktičnim. U isto vreme oni ne treba da budu preblizu, jer broj može biti brzo faktorisan metodom Fertmanove faktorizacije . Broj može takođe biti izabran tako da niko od p − 1, p + 1, q − 1, , ili q + 1 ne budu uglađeni brojevi, i da štite od Polardovogp − 1algoritma ili Vilijamsovog p + 1 algoritma . Međutim , ove provere ne mogu da uzmu buduće algoritme ili tajne algoritama u obzir, a pri tom uvodeći mogućnost da danas broj u upotrebi može biti razlomljen specijalnim namenama algoritama.

Godine 1974. Arejsib poruka je poslata sa radio signalom u zvezdano jato . Ona se sastojala od 1679 binarnih cifara nameravanih da se tumači kao 23 × 73 bitmapirane slike . Broj 1679 = 23 × 73 je izabran jer je to poluprost broj i stoga može biti razlomljen samo dole u ​​23 redova i 73 kolona , ili 73 redova i 23 kolona .

Vidi još

• Čenova teorema

Spoljašnje veze

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