Увод¶

Теорија бројева, као област, већ хиљадама година заокупља пажњу математичара, а у последњим деценијама сведоци смо да су неки од њених резултата постали изузетно значајни у свакодневном животу. Овде се пре свега мисли на чувени алгоритам RSA и сродне алгоритме, који су у основи многих протокола комуникације, као што је безбедно слање порука, доказивање аутентичности учесника у комуникацији, дигитално потписивање докумената и слично.

Ово поглавље је осврт на елементарну теорију бројева, из угла алгоритмике. Централни појмови теорије бројева су дељивост, односно прости бројеви, а основна питања којима ћемо се бавити су:

• провера да ли је дати број прост (тест прималности броја)

• растављање броја на просте чиниоце (факторизација броја)

• одређивање највећег заједничког делиоца (НЗД) два или више бројева

• одређивање најмањег заједничког садржаоца (НЗС) два или више бројева

• решавање линеарних диофантских једначина

• проналажење свих простих бројева мањих од датог броја

Најпре ћемо проћи кроз познате алгоритме за решавање наведених проблема, са посебним освртом на њихову ефикасност. У наставку ћемо вежбати примене ових алгоритама у решавању разних проблемских задатака.