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

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

Идеја

Мала Фермаова теорема тврди да, ако је p прост број, и $1\leq 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]

ако је a^{n − 1} mod n ≠ 1 врати сложен

врати вероватно прост

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

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

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

Мане

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

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

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

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

$(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 × a_i за i = 1, 2, ..., s Фермаови сведоци.

Употреба

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

Литература

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

Види још

• Мала Фермаова теорема