Alkulukugeneraattori verkossa

Mikä on alkuluku?

Alkuluku on 1:tä suurempi luonnollinen luku, joka on jaollinen vain ykkösellä ja itsellään. Pienimmät alkuluvut ovat 2, 3, 5, 7, 11, 13, 17, 19, 23, 29… Luku 2 on ainoa parillinen alkuluku – kaikki muut parilliset luvut ovat jaollisia kahdella.

Luvut kuten 4 (= 2 × 2), 6 (= 2 × 3) tai 15 (= 3 × 5) eivät ole alkulukuja – niitä kutsutaan yhdistetyiksi luvuiksi.

Miten generaattori toimii?

Kaikkien alueen alkulukujen listaamiseen käytämme Eratostheneen seulaa – yhtä vanhimmista ja tehokkaimmista algoritmeista, jonka kreikkalainen matemaatikko Eratosthenes Kyreneläinen kuvaili noin vuonna 240 eaa.

Algoritmi poistaa peräkkäin jokaisen löydetyn alkuluvun kerrannaiset. Jäljelle jääneet ovat alkulukuja. Koko laskenta tapahtuu suoraan selaimessasi – tietoja ei lähetetä palvelimelle.

Satunnaista valintaa varten generaattori rakentaa ensin luettelon kaikista alueen alkuluvuista ja valitsee sitten niistä satunnaisesti halutun määrän kryptografisesti turvallisella generaattorilla (crypto.getRandomValues()).

Generaattorin toiminnot

• Kaikki alkuluvut – listaa jokaisen alkuluvun annetulta alueelta (max. 10 000)
• Satunnainen valinta – valitsee N satunnaista alkulukua alueelta (sopii suurille alueille)
• Lajittelu – lajittelee tulokset nousevaan järjestykseen
• Erotin – valitse, miten numerot erotetaan toisistaan kopioitaessa
• Pikaesivalinnat – yleisimmät alueet yhdellä napsautuksella

Missä alkulukuja käytetään?

Kryptografia ja tietoturva

Alkuluvut ovat modernin kryptografian perusta. RSA:n kaltaiset algoritmit perustuvat siihen, että kahden suuren alkuluvun tulo on helppo laskea, mutta niiden takaisin alkutekijöiksi hajottaminen on laskennallisesti erittäin vaativaa.

• RSA-salaus – avaimet generoidaan kahdesta suuresta alkuluvusta
• Diffie-Hellman – avainten vaihto alkulukuun perustuvan moduulin avulla
• Tiiviste-funktiot – alkuluvut maagisina vakioina (SHA, MD5)

Matematiikka ja tiede

• Lukuteoria – kokonaislukujen perustavat rakennuspalikat
• Goldbachin konjektuuri – jokainen parillinen luku > 2 voidaan ilmaista kahden alkuluvun summana (ei vielä todistettu)
• Riemannin hypoteesi – yksi Hilbertin ongelmista, koskee alkulukujen jakautumista

Käytännön sovellukset

• Tiiviste-taulukot – taulukon koko alkulukuna vähentää törmäyksiä
• Pseudosatunnaislukugeneraattorit – lineaarinen kongruenssi alkulukumoduulin kanssa
• Musiikki ja rytmi – polyrytmia alkulukupituisten syklien kanssa

Alkulukujen jakautuminen

Alkuluvut ovat jakautuneet luonnollisten lukujen joukkoon epäsäännöllisesti, mutta niiden tiheys pienenee alueen kasvaessa. Tätä kuvaa alkulukuteoreema: alkulukujen määrä lukuun N asti on noin N / ln(N).

Eratostheneen seula askel askeleelta

Alue 2–30:
[2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]

1. Valitse 2, poista sen kerrannaiset: 4, 6, 8, 10, 12...
2. Valitse 3, poista sen kerrannaiset: 9, 15, 21, 27...
3. Valitse 5, poista sen kerrannaiset: 25...
4. √30 ≈ 5.5 → valmis

Alkuluvut: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29

Eratostheneen seula koodissa

JavaScript

function sieve(to) {
  const composite = new Uint8Array(to + 1);
  const primes = [];
  for (let p = 2; p <= to; p++) {
    if (composite[p]) continue;
    primes.push(p);
    for (let j = p * p; j <= to; j += p) composite[j] = 1;
  }
  return primes;
}

Python

def sieve(n):
    composite = bytearray(n + 1)
    primes = []
    for p in range(2, n + 1):
        if not composite[p]:
            primes.append(p)
            for j in range(p * p, n + 1, p):
                composite[j] = 1
    return primes

Usein kysytyt kysymykset (UKK)