Puolialkuluku

Puolialkuluku tarkoittaa lukuteoriassa sellaista yhdistettyä lukua, joka on täsmälleen kahden alkuluvun tulo eli pq, missä p ja q ovat alkulukuja (samoja tai eri lukuja). Puolialkulukuja ovat esimerkiksi $9=3\cdot 3$ ja $301=7\cdot 43$. Suurien puolialkulukujen tekijöihinjako on hyvin työlästä.

Puolialkuluvun Eulerin φ-funktio on hyvin yksinkertaista muotoa, nimittäin $\phi (pq)=(p-1)(q-1)$ jos $p\ne q$, ja $\phi (p^2)=p(p-1)$.

Kuten alkulukuja, on myös puolialkulukuja olemassa äärettömästi. Suuruusjärjestyksessä niiden luettelo alkaa seuraavasti:

4, 6, 9, 10, 14, 15, 21, 22, 25, 26, 33, 34, 35, 38, 39, ...

Arecibon radioteleskoopilla lähetettiin vuonna 1 679 bittiä pitkä Arecibo-viesti. Viestin pituus on puolialkuluku, minkä tarkoituksena oli vihjata vastaanottajalle, että viesti tulee tulkita bittikarttakuvaksi, jossa on 73 riviä ja 23 saraketta.

RSA Factoring Challenge

RSA-salaus perustuu hyvin suurten kokonaislukujen jakamiseen tekijöihin. Edistääkseen tekijöihinjaon ja laskennallisen lukuteorian tutkimusta RSA Data Security julisti maaliskuussa 1991 kilpailun, jossa se julkaisi luettelon erikokoisia puolialkulukuja, 100-numeroisesta 500-numeroiseen, ja lupasi rahapalkinnot niiden tekijöihin jakamisesta. Pienimmän saivat Mark Manasse ja Arjen Lenstra jaettua tekijöihin jo huhtikuussa 1991. Kyseessä oli luku

1522605027 9225333605 3561837813 2637429718 0681149613 8068865790 8494580122 9632589528 9765400035 0692006139,

ja sen alkutekijähajotelma oli

4009469095 0920881030 6837352927 6146838921 4899724061 · 3797522793 6943673922 8088727554 4562785456 5536638199.

Seuraava, 110-numeroinen luku saatiin jaettua tekijöihin vuotta myöhemmin. Luettelon suurimpia lukuja ei ole saatu jaettua tekijöihin.