Algarv

Allikas: Vikipeedia

See artikkel vajab toimetamist.

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 kasutatavad avalikul võtmel põhinevaid krüpteerimisalgoritme.


[redigeeri] Vaata ka

  • Kordarv
  • Eukleidese teoreem algarvudest
  • Gaussi algarv
  • Fermat' algarv

[redigeeri] Viited

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

[redigeeri] Välislingid