Пјер де Ферма: Разлика помеѓу преработките
| [проверена преработка] | [проверена преработка] |
Избришана содржина Додадена содржина
с правопис: т → д |
поврзница |
||
Ред 51:
===Малата теорема на Ферма===
Една од најважните компоненти на асиметричната криптографија е теоремата на Ферма, уште позната и како малата теорема на Ферма.
Малата теорема на Ферма гласи: ако p е прост број, и m е било кој цел број што не е делив со p, тогаш m на степен p-1 дава [[остаток (математика)|остаток]] 1 кога ќе се подели со p. Малата теорема на Ферма може да се искористи за да се провери дали еден број е прост или не е, т.е. послужила како основа за тестот на Ферма за прости броеви.
Според тестот на Ферма, ако m^p (mod p)≠m (mod p) тогаш p не е прост, ако m^p(mod p)=m (mod p) тогаш p може да биде прост. Тогаш се извршува следниот циклус и тоа к-пати, се бира произволен m и доколку m^(p-1) (mod p)≠1 тогаш бројот е сложен, инаку веројатно е прост. Ако циклусот се повтори доволен број к-пати, веројатноста дека p e прост број станува 100%.
| |||