Zp - если p - простое, то все элементы Zp будут взаимо просты с p. И тогда для любого ненулевого w в Zp существует такое z, что w*z = 1 mod p (условие для Поля Галуа).
Попробуем подсчитать для простого числа НАПРИМЕР 7: Btw, Это поле является полем Галуа GF[7] = GF[7,1]. сложение по модулю 7: + | 0 1 2 3 4 5 6 ---+-------------- 0 | 0 1 2 3 4 5 6 1 | 1 2 3 4 5 6 0 2 | 2 3 4 5 6 0 1 3 | 3 4 5 6 0 1 2 4 | 4 5 6 0 1 2 3 5 | 5 6 0 1 2 3 4 6 | 6 0 1 2 3 4 5 умножение по модулю 7: * | 0 1 2 3 4 5 6 ---+-------------- 0 | 0 0 0 0 0 0 0 1 | 0 1 2 3 4 5 6 2 | 0 2 4 6 1 3 5 3 | 0 3 6 2 5 1 4 4 | 0 4 1 5 2 6 3 5 | 0 5 3 1 6 4 2 6 | 0 6 5 4 3 2 1 найдем отрицательные и обратные величины: w -w w^(-1) -------------- 0 0 - 1 6 1 2 5 4 3 4 5 4 3 2 5 2 3 6 1 6 Теперь попробуем найти примитивный элемент, т.е. элемент степенями которого можно представить все другие ненулевые элементы: для этого попробуем посчитать степени элементов: a a^N | 1 2 3 4 5 6 ----|------------------- 1 | 1 2 3 4 5 6 2 | 1 4 2 2 4 1 N 3 | 1 1 6 1 6 6 4 | 1 2 4 4 2 1 5 | 1 4 5 2 3 6 6 | 1 1 1 1 1 1 ^ | +--- вот он примитивный элемент
Теорема Ферма (малая теорема Ферма): Если p - простое, а a - положительное целое, то a^(p-1) = 1 mod p a^p = a mod p
таблица степеней: элемент 5 - примитивный его степенями можно представить любой другой ненулевой элемент 5^1 = 5 5^2 = 25 mod 7 = 4 5^3 = 125 mod 7 = 6 5^4 = 625 mod 7 = 2 5^5 = 3125 mod 7 = 3 5^6 = 15625 mod 7 = 1
Дискретные логарифмы: -------------------------------------------- w 5^N 5^N 5^N 5^N -------------------------------------------- 5 1 7 -5 -11 4 2 8 -4 -10 6 3 9 -3 -9 2 4 10 -2 -8 3 5 11 -1 -7 1 6 12 0 -6 -------------------------------------------- умножение - это сложение индексов X^i * X^j = X^(i+j) деление - вычитание индексов X^i / X^j = X^(i-j) на ноль делить нельзя дискретное логарифмирование log N = log(X^i) = i Умножение: 3 * 4 = 12 mod 7 = 5 3 * 4 = 5^5 * 5^2 = 5^(5+2) = 5^7 = 5 Деление: 6 / 2 = 5^3 / 5^4 = 5^(3-4) = 5^(-1) = 3 6 / 3 = 5^3 / 5^5 = 5^(3-5) = 5^(-2) = 2 но зато 6 / 4 = 5^3 / 5^2 = 5^(3-2) = 5^1 = 5 проверим 5 * 4 = 20 mod 7 = 6 все верно 6 / 1 = 5^3 / 5^6 = 5^(3-6) = 5^(-3) = 6 6 / 5 = 5^3 / 5^1 = 5^(3-1) = 5^2 = 4 5 / 3 = 5^1 / 5^5 = 5^(1-5) = 5^(-4) = 4 2 / 2 = 5^4 / 5^4 = 5^0 = 1