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 ja . Suurien puolialkulukujen tekijöihinjako on hyvin työlästä.[1][2]
Puolialkuluvun Eulerin φ-funktio on hyvin yksinkertaista muotoa, nimittäin jos ,[1] ja .
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, ...[3]
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.[4]
RSA Factoring Challenge
[muokkaa | muokkaa wikitekstiä]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.[5][6][7][8]
Lähteet
[muokkaa | muokkaa wikitekstiä]- ↑ a b Semiprime MathWorld. Wolfram Research. Viitattu 28.3.2022. (englanniksi)
- ↑ Rosama, Veera: Aritmeettinen derivaatta (Pro gradu -tutkielma) 2013. Helsingin yliopisto. Viitattu 28.3.2022.
- ↑ A001358 Semiprimes (or biprimes): products of two primes The On-line Encyclopedia of Integer Sequences. Viitattu 28.3.2022. (englanniksi)
- ↑ Oberhaus, Daniel: Extraterrestrial Languages, s. 171. MIT Press, 2019. ISBN 9780262043069 (englanniksi)
- ↑ Kaliski, Burt: RSA factoring challenge groups.google.com. 18.3.1991. Viitattu 28.3.2022. (englanniksi)
- ↑ RSA Challenge List ontko.com. 19.5.1994. Viitattu 28.3.2022. (englanniksi)
- ↑ RSA Number MathWorld. Wolfram Research. Viitattu 28.3.2022. (englanniksi)
- ↑ RSA Honor Roll, As of March 5, 1999 ontko.com. 30.1.2002. Viitattu 28.3.2022. (englanniksi)