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 ChallengeMuokkaa

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ähteetMuokkaa

  1. a b Semiprime MathWorld. Wolfram Research. Viitattu 28.3.2022. (englanniksi)
  2. Rosama, Veera: Aritmeettinen derivaatta (Pro gradu -tutkielma) 2013. Helsingin yliopisto. Viitattu 28.3.2022.
  3. A001358 Semiprimes (or biprimes): products of two primes The On-line Encyclopedia of Integer Sequences. Viitattu 28.3.2022. (englanniksi)
  4. Oberhaus, Daniel: Extraterrestrial Languages, s. 171. MIT Press, 2019. ISBN 9780262043069. (englanniksi)
  5. Kaliski, Burt: RSA factoring challenge groups.google.com. 18.3.1991. Viitattu 28.3.2022. (englanniksi)
  6. RSA Challenge List ontko.com. 19.5.1994. Viitattu 28.3.2022. (englanniksi)
  7. RSA Number MathWorld. Wolfram Research. Viitattu 28.3.2022. (englanniksi)
  8. RSA Honor Roll, As of March 5, 1999 ontko.com. 30.1.2002. Viitattu 28.3.2022. (englanniksi)