Још неки алгебарски алгоритми¶
Заинтересованим читаоцима предлажемо неколико тема као следеће кораке за самостално проучавање.
Брзи тест прималности¶
Као што смо научили, провера да ли је дати број \(n\) прост у општем случају захтева време сразмерно са \(\sqrt n\). Није познат егзактан алгоритам за овај проблем, који је асимптотски ефикаснији од \(\Theta(\sqrt n)\). Зато је од практичног значаја познавање алгоритама који дају одговор веома брзо, мада не гарантују увек тачан резултат. Један такав алгоритам се заснива на малој Фермаовој теореми, а познат је као Фермаов тест за просте бројеве. Проблему ефикасног, мада не сасвим поузданог утврђивања прималности бројева је посвећен и задатак Велики прости пројеви у Петљиној онлајн збирци задатака.
Ојлерова функција и Ојлерова теорема¶
Ојлерова фи функција је тема задатка Ојлерова функција из Петљине онлајн збирке. Ова функција се појављује у Ојлеровој теореми, која је значајна јер се на њу ослања чувени RSA алгоритам.
Дефиниција: За дато \(n\), Ојлерова функција \(\varphi(n)\) једнака је броју природних бројева мањих или једнаких од \(n\) и узајамно простих са \(n\):
Ова функција има једну важну особину, а то је да за узајамно просте \(a, b\) важи \(\varphi(a \cdot b)=\varphi(a) \cdot \varphi(b)\). Ова особина функције \(\varphi\) се назива мултипликативност. Захваљујући мултипликативности, вредност функције за било које \(n\) може брзо да се израчуна када су познате вредности функције \(\varphi(p^k)\) за просте бројеве \(p\) и природне бројеве \(k\). Наиме, ако је позната факторизација броја \(n\), \(n=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdots p_m^{\alpha_m}\), тада је
Поред функције \(\varphi(n)\), постоје и друге мултипликативне функције. Вредности свих таквих функција се по правилу знатно ефикасније рачунају када се аргумент функције \(n\) растави на просте чиниоце. Наравно, пре тога је потребно доказати мултипликативност функције и одредити вредности функције за аргументе који су степени простих бројева.
Предлажемо читаоцима да покушају да докажу мултипликативност функције \(\varphi\) и да одреде њене вредности за \(\varphi(p^k)\), где је \(p\) прост број. У случају потребе, додатна упутства могу да се нађу у решењу поменутог задатка из Петљине онлајн збирке. Након тога, до ефикасног решења задатка се долази факторизацијом броја \(n\).
RSA алгоритам¶
RSA алгоритам смо поменули и у уводу поглавља о алгебарским алгоритмима, због његовог великог значаја у савременим комуникационим технологијама. Овај алгоритам и његове модификације су у основи многих комуникационих протокола, као што је безбедно слање порука, доказивање аутентичности учесника у комуникацији, дигитално потписивање докумената и слично. Нешто више о самом алгоритму можете да прочитате у поглављу Криптографија Петљиног курса за четврти разред гимназије. Детаљан опис RSA алгоритма је пар страница даље, али цело поглавље може да буде занимљиво. На пример, на страници Kриптографијa и хеширање је објашњено како помоћу RSA алгоритма може да се потврди аутентичност поруке, односно како RSA алгоритам у комбинацији са хеширањем може да се искористи за пружање разних услуга у комуникацији на интернету, као што су:
провера веродостојности порука и фајлова
генерисање и верификација дигиталног потписа
верификација лозинки (без памћења самих лозинки)