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

Существует частный случай переборного варианта поиска первообразных элементов; модуль т является простым числом р (в этом случае первообразные элементы называются примитив­ ными). В качестве вариантов первообразных корней рассматрива­ ются все числа а = 2, р-1, которые удовлетворяют условиям: 1) взаимной простоты чисел а и р\ НОД (а,р) = 1; 2) так как функция Эйлера, вычисляемая от простого числа, равна (р(/?) = р~ 1, то = 1 mod р или а''''m o d s 1; 3) для V/- = 1, р-\, являюидегося делителем числа <(>(/) =р~ 1 , т.е. г\р - 1, выполняется условие а' Ф 1 mod р. Теорема 2.1. Число а, а-2, р-\, будет первообразным эле­ ментом по простому модулю р, если выполняется условие: г-1 а Ф 1 mod р для V/ = 0, к~ \, где число р - 1 представлено в виде канонического разложения А-1 /? - 1 = П РГ' простых сомножителей; а, - натуральные числа. /=(| Приводимые формулировки теорем разд. 2.3 взяты из ра­ бот [4, 11]. Пример 2.8. Проверить с помощью теоремы 2.1, что число а= 10 является первообразным элементом по простому модулю р= 19. Число р - 1 = 19 - 1 = 18 можно разложить в канонический вид:/?- 1 = 18 = 2x3^; (р~])/р, = 18/2 = 9; {р~\)1р. = 18/3 = 6. £ _1 Проверим, что а '' Ф 1 mod р , / = 1, 2. Запишем промежуточные результаты вычислений (схема Тер­ нера, см. разд. 1.7); lO'mod 19= 1000 mod 19= 12; 51