Algarv
 |
See artikkel vajab toimetamist. Palun aita artiklit toimetada. |
Algarvuks nimetatakse ühest suuremat naturaalarvu, mis jagub vaid arvuga 1 ja iseendaga. Algarvude hulk on lõpmatu, nagu tõestati juba antiikajal (vaata Eukleidese teoreem algarvudest). Naturaalarvust n mitte suuremate algarvude arvu tähistatakse sümboliga π(n).
Sajast väiksemad algarvud (π(100) = 25) on 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ja 97.
Kaksikuteks nimetatakse selliseid algarve, mille vahe on 2, näiteks 101 ja 103 või 1 000 000 007 ja 1 000 000 009. Ei ole teada, kas kaksikuid on lõpmata palju.
On teada, et algarvulisuse kontroll on polünomiaalses ajas lahenduv [1]. Parimad teadaolevad suurte arvude faktoriseerimise algoritmid on eksponentsiaalse keerukusega arvu pikkuse suhtes kahendsüsteemis. Arvatakse, et polünomiaalset algoritmi ei leidu, ja sellel lootusel rajaneb enamik tänapäeval kasutatavaid avalikul võtmel põhinevaid krüpteerimisalgoritme.
[redigeeri] Vaata ka
[redigeeri] Viited
[redigeeri] Välislingid
