Садржај
Израчунавање примитивних корена је корисна вештина у криптографији и теорији бројева. Број "г" је примитивни корен за дани прост број "п" ако г мод п има модул реда п-1. То значи да листа "г1 мод п", "г2 мод п" до "г (п-1) мод п" садржи све бројеве од 1 до (п-1). Не постоји познати алгоритам за ефикасно израчунавање примитивних коријена. Најједноставнији метод је пробати сваки могући број од 2 до (п-1).
Упутства
-
Изаберите прост број, "п", као пет. Примарни број нема делиоце изван себе и једног. На пример, четири нису прости број, јер "4/2 = 2", има 2 као један од његових делитеља.
-
Израчунајте "2 ^ н мод п" за сваки цео број "н" од 1 до (п-1). Користећи пример, "п" је 5, затим израчунајте "2 ^ н мод 5" за "н" од 1 до 4. Ово даје листу:
2 ^ 1 = 2 мод 5 = 2 2 ^ 2 = 4 мод 5 = 4 2 ^ 3 = 8 мод 5 = 1
-
Побрините се да листа бројева садржи све могуће трагове од пет. Листа 2, 4, 3 и 1 се квалификује, тако да је 2 примитивни корен са остатком 5. Ако је, уместо тога, листа била 2,1,4 и 1, што је листа за 4, онда 4 не би било примитивни корен јер број 3 недостаје са листе.
-
Поновите претходни корак за све бројеве мање од пет. Број три је такође примитивни коријен остатка пет, али четири нису; онда два и пет су примитивни корени за пет.