Algarv

Allikas: Vikipeedia

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.


Vaata ka[muuda | redigeeri lähteteksti]

Viited[muuda | redigeeri lähteteksti]

  1. http://www.math.princeton.edu/~annals/issues/2004/Sept2004/Agrawal.pdf

Välislingid[muuda | redigeeri lähteteksti]