Фермаов тест за просте бројеве

Из Википедије, слободне енциклопедије

Фермаов тест је насумични тест којим се утврђује да ли је број потенцијално прост.

Идеја[уреди]

Мала Фермаова теорема тврди да, ако је p прост број, и 1 \le a < p, онда важи

a^{p-1} \equiv 1 \pmod{p}

Уколико желимо да утврдимо да ли је p прост број, можемо бирати произвољне бројеве a у задатом интервалу и проверавати да ли важи једнакост. Уколико нађемо број a за који једнакост није испуњена, доказали смо да је број p сложен. Са друге стране, уколико је једнакост испуњена за пуно различитих бројева a, можемо рећи да је p вероватно прост број, или псеудопрост број.

Може се десити да у тестирању не изаберемо вредност броја a за коју једакост не би била тачна. Сваки број a за који важи

a^{n-1} \equiv 1 \pmod{n}

када је n сложен, се назива Фермаов лажов. Уколико изаберемо a тако да је

a^{n-1} \not\equiv 1 \pmod{n}

онда се a назива Фермаов сведок за сложеност броја n.

Алгоритам и време извршавања[уреди]

Алгоритам теста може бити формулисан на следећи начин:

Улаз
n: број за који се тестира да ли је прост
k: параметар који задаје колико пута треба тестирати да ли је број прост
Излаз
сложен ако је n сложен, иначе вероватно прост
понови k пута:
изабери произвољан a из интервала (1, n − 1]
ако је an − 1 mod n ≠ 1 врати сложен
врати вероватно прост

Коришћењем брзих алгоритама за модуларно степеновање добија се да је време извршавања овог алгоритма

O(k × log2n × log log n × log log log n),

где k броји колико пута смо тестирали произвољно a, док је n број за који испитујемо да ли је прост.

Мане[уреди]

Постоје извесне вредности броја n, познате као Кармајклови бројеви, за које су сви бројеви a, који су узајамно прости са n, Фермаови лажови. Иако су такви бројеви ретки, има их довољно да се уместо Фермаовог теста за проверу да ли је дати број прост често употребљавају други тестови, као што су Милер-Рабин и Соловеј-Штрасен.

У општем случају, ако n није Кармајклов број, онда бар пола свих бројева

a\in(\mathbb{Z}/n\mathbb{Z})^*

има особину да су Фермаови сведоци. Да би се ово показало, довољно је претпоставити да је a Фермаов сведок, а да су a1, a2, ..., as Фермаови лажови. Онда важи

(a\cdot a_i)^{n-1} \equiv a^{n-1}\cdot a_i^{n-1} \equiv a^{n-1} \not\equiv 1\pmod{n}

што значи да су сви a × ai за i = 1, 2, ..., s Фермаови сведоци.

Употреба[уреди]

Програм за енкрипцију PGP користи овај тест у својим алгоритмима. Вероватноћа да ће PGP изгенерисати Кармајклов број је мања од 1 : 1050, што је више него довољно за практичну употребу.

Литература[уреди]

  • Томас Кормен (Thomas H. Cormen), Чарлс Лејсерсон (Charles E. Leiserson), Роналд Ривест (Ronald L. Rivest) и Клифорд Стин (Clifford Stein). Увод у алгоритме (Introduction to Algorithms), друго издање, MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. стр. 889-890

Види још[уреди]