Primaarvud

Primaarv ehk algarv on naturaalne arv suurem kui 1, millel on täpselt kaks erinevat positiivset jagajat: 1 ja iseend. Näited: 2, 3, 5, 7, 11, 13. Arv 1 ei ole primaarv ning iga arv, mis on jagatav mõne teise arvuga, ei ole primaarv. 2 on ainus paarisarv, mis on primaar, mistõttu kõik ülejäänud paarisarvud ei ole primaarid.

Primaarvud moodustavad aritmeetika aluse. Üks olulisemaid tulemusi on fundamentaalne faktoriatsiooniteoreem: iga arv suurem kui 1 saab unikaalselt kirjutada primaarvude korrutisena (korrutuste järjekorda võidakse vahetada). See fakt annab aritmeetika struktuuri ja lubab mõista arvude jaguvust põhjalikult.

On tõestatud, et primaarvud on lõpmatu arv. Iga antud arvust suurem primaar arv leiab alati olemas. Primaaride arvu pi(x) määrab kui palju primaararve on väiksem kui või võrdne x. Pi(x) kasv on umbes x / log x suuruste x puhul; see tuleneb kihtisest mõistest nimega primaaride mingit tasakaalu kirjeldav teoreem. Täpseid väärtusi prognoositakse ja arvutatakse erinevate algoritmidega.

Primalaaride kontrollimiseks kasutatakse nii lihtsaid kui ka keerukamaid meetodeid. Lihtne kontroll jagajateni ruutjuure n-ni võib leida väikeste arvude korral; suurte arvude jaoks kasutatakse deterministlikke ja probabilistlikke testide kombinatsioone, nagu Miller–Rabin, ning mõningatel juhtudel spetsiaalseid deterministlikke teste.

Kasutused ja tähtsus. Primaarvud mängivad suurt rolli krüptograafias: suurte võtmete loomine RSA, Diffie–Hellman ja elliptic curve krüptograafia jaoks tugineb primaaride omadustele ja nende faktoreerimise raskusele. Primaaride uurimine seob teooria ja rakendused ning jätkuv töö hõlmab nii jaotuse mõistmist kui ka praktilist arvutustegevust.