Вычисления в конечных полях

li-i определения слсдуст, что для любых чисел г - 1, Р{а) ~ 1 (натуральных, чисел, меньших Я(а)) не должно выполняться срав­ нение вида а S 1 modw/. Пример 2.7. Найти значение РцСЗ). Число 5 может быть пока­ зателем числа 3, так как 3'^ mod 11 = (З"* х 3) mod 11 = (4x3) mod 11 = 1, т.е. 3^ S 1 modi 1. А для чисел г = 1, 4 не выполняется условие 3 ' ' s lmod l l , т.е. 3' mod 11^1: З' mod 11 = 3 ^ 1 ; 3'mod 11 = 9 ^ 1 ; 3'mod 11 =27 mod 11 =5 ^ 1; З"' mod 1 = (27x3) mod 11 = (5x3) mod 11=4^1 . Ответ: показатель степени для числа 3 по модулю 11 равен РиО) = 5. Число а, где НОД («, w) = 1, называется первообразным элементом (первообразным корнем, порождающим элементом) по модулю т , если показатель а по этому модулю равен ц>(т), т.е. Р(а) - ф(ш). Таким образом, первообразным элементом является чиело а, для которого выполняется фавнение: а''""" s 1 mod т , где (^{т) = Р„,(й). Существует следующий переборный вариант поиска перво­ образных элементов. В качестве кандидатов в первообразные эле­ менты рассматриваются все числа а-2, rn- l, которые удовлетво­ ряют следующим условиям: 1) взаимной простоты чисел а и т: НОД (а,т ) = 1; 2) л''""" 3 1 mod т или сг'""" mod т = 1; 3) для\/г = 1, ф(/;г)~1, являющегося делителем числа ф(т) (т.е. г I ф(/н)), выполняется условие а'' ^ ImodM?. Замечание 2.1, Число 1 в качестве варианта первообразного элемента не рассматривается, так как при любой степени единицы и любом модуле будет выполняться условие 1''""" s 1 mod »;. 50