Вопросы к экзамену Определение поля и примеры полей
 Скачать 0.63 Mb.
|
|
Фундаментальная и компьютерная алгебра Вопросы к экзамену 1. Определение поля и примеры полей. 2. Характеристика поля. Теорема о том, что характеристика простое число. 3. Алгебраическое расширение. Теорема о структуре простого алгебраиче- ского расширения, как фактор кольца. 4. Простое поле. Простое поле нулевой характеристики.(Поле рациональ- ных чисел). 5. Простое поле Галуа. Теорема о существовании.(Кольцо вычетов). 6. Теорема о существовании поля GF (p n ). 7. Структура подполей поля Галуа. 8. Теорема описания неприводимых многочленов над полем Галуа. 9. Теорема о существовании примитивного элемента в полях Галуа. 10. Алгоритм нахождения примитивного элемента. 11. Решение уравнений в конечных полях. Логарифм Якоби. Пример. 12. Функция Эйлера. Группа обратимых элементов кольца вычетов Z n 13. Алгебраические расширения полей любой характеристики. Алгебраиче- ские числа. 14. Норма и след элементов поля Галуа. 15. Примитивные элементы колец вычетов порядка p n и 2p n . Идея доказа- тельства и примеры. 16. Линейные регистры сдвига с обратной связью. 17. Длина периода. Матричная запись. 18. Решение линейного уравнения в кольце вычетов. 19. Решение системы линейных уравнений по разным модулям. 20. Алгоритм шифрования RSA. Пример вычислений. 21. Алгоритм шифрования AES. нахождение обратных элементов в поле GF (2 8 ). Преобразование, нелинейная замена. 22. Алгоритм AES - замена столбцов. Структура простого алгебраического расширения Пусть P - поле, α - алгебраический элемент. По определению алгебраиче- ского элемента, f (x) = x n + a n−1 x n−1 + ... + a n корнем которого он является. Так как такой многочлен не единственный, а нам нужна определенность. Разложим f (x) на неприводимые множители, тогда α - будет корнем од- ного из них. На самом деле, единственный будет такой многочлен и его 1 называют минимальным. Пусть напротив таких многочленов 2: g 1 (x)g 2 (x) т.к они неприводимы, найдем (g 1 , g 2 ) = 1. По следствию из алгоритма Ев- клида ∃h 1 , h 2 так что h 1 g 1 + h 2 g 2 = 1 h 1 (α)g 1 (α) + h 2 (α)g 2 (α) = 1 ⇒ 0 + 0 = 1 (противоречие) Минимальное поле, которое содержит α и называется P (α) простым алгеб- раическим расширением. Как устроено это поле P (α)? 1. Абстрактное строение: Рассмотрим идеал, порождаемый многочленом f (x), то есть I = ug(f (x)) = e(x)|e(x) = f (x)h(x), h(x) ∈ P [x] Рассмотрим фактор кольцо P [x]/ug(x) (из теоремы о построении поля раз- ложения) многочлен f (x) имеет хотя бы один корень и пусть это будет α 2. Символьное описание простого расширения: p(α) = b 0 + b 1 α + ... + b n−1 α n−1 |b j ∈ P - это поле является векторным про- странством размерности n над полем P . Базис (1, α, ..., α n−1 ), f (α) = 0 α n = −a n−1 α n−1 − ... − a n - это соотношение задает умножение в поле. Теорема Простое алгебраическое расширение P (α) изоморфно P [x]/ug(f (x))P (α) = b 0 + b 1 α + ... + b n−1 α n−1 |b j ∈ P Обобщение α 1 , α 2 , ..., α k P (α 1 , α 2 , ..., α k ) (P (α 1 ))(α 2 ))(α 3 ) - алгебраическое расширение P (α 1 , α 2 , ..., α k ) строится ин- дуктивно. Если поле непроизвольное, а поле рациональных чисел, то алгебраические расширения называются алгебраическими числами. Вся теория полей родилась из алгебраических чисел. Структура полей Галуа Определение Поле Галуа - это любое конечное поле. Так как конечное поле имеет ненулевую характеристику, то у поля Галуа характеристика P - простое число. Теорема Z p = 0, 1, ..., p − 1 = GF (p) - единственное простое поле, то есть не содер- жит подполей. 2 Доказательство Так как любое подполе содержит единицу по умножению. {1, 1 + 1, 1 + 1 + 1...} = Z p Теорема о существовании простого поля Галуа Теорема Для любого простого числа p и натурального числа n существует поле, содержащее p n элементов. x p n − x - по теореме о поле разложения, разлагается на множители. Доказательство Пусть α, β ∈ F - корни этого многочлена, то есть α p n − α = 0 β p n − β = 0 1. Проверим, что α + β - корень (α + β) p n − (α + β) так как характеристика поля = p, pα = 0 То по Биному Ньютона: α p n + β p n − (α + β) - действительно корень. αβ - тоже корень. (αβ) p n − αβ 2. α p n β p n − αβ - корень. 3. −α 4.−α −1 Таким образом поле GF (p n ) ∃n состоящий из корней многочлена x p − x. Структура подполей поля Галуа Теорема о структуре подполей GF (p n )GF (p m ) - поля Галуа. Тогда, GF (p n ) ≥ GF (p m ) ⇒ m|n(делит) То есть структура подполей определяется структурой делителей числа n. Доказательство Пусть GF (p n ) ≤ GF (p m ), где GF (p n ) = P GF (p m ) = F Так как P подполе F, то - векторное пространство над полем P. Пусть раз- мерность этого пространства K. | F |=| P | k 3 p n = (p m ) k n = mk Пусть m | n, тогда x pn −x x pm −x , по формуле геометрической прогрессии. Значит поле разложение нижнего многочлена содержится в поле разложения верх- него многочлена. Является подполем, а поле разложением GF (p n ) по 2 - ой теореме. Неприводимые многочлены в полях Галуа Теорема Пусть f (x) неприводимый многочлен над полем GF (p). α - корень GF (p n )(n - степень). Тогда α, α p , ..., α p n−1 - различные корни многочлена f (x). Если в поле Галуа добавить один корень, то многочлен разлагается на простые множители. Доказательство 0 = f (α) = α n + a n−1 α n−1 + ... + a 0 = 0, a ∈ GF (p) По условию дано, что 0 = f (α) = α n + a n−1 α n−1 + ... + a 0 = 0. Чтобы дака- зать теорему, нужно проверить, что возведение в степень p ост-ет корень корнем. Заметим, что a i ∈ GF (p) ∀ i a i p = a i (∗). Заметим в многочлене α на α p , получим (α p ) n + a n−1 (α p ) n−1 + ... + a 0 = исп-ся рав(*) и (α p ) n + a n−1 (α p ) n−1 + ... + a 0 = (α n ) p + a n−1 p (α n−1 ) p + ... + a 0 p , так как характеристика = p, то есть pα = 0, то по фомруле Бинома запи- шем так. (α n ) p + a n−1 p (α n−1 ) p + ... + a 0 p = (α n + a n−1 α n−1 + a 0 ) p = f (α) p = 0 p = 0. Примитивный элемент Определение Пораждающий элемент мультипликативной группы поля называется при- митивным. Теорема В любом конечном поле GF (p m ) существует примитивный элемент, то есть мультипликативная группа этого поля циклическая. Доказательство h = p n − 1 = p 1 α 1 − p s α n - разложение на простые множители. 4 Пусть a i h pi = 1 (не корень) Введем b i = a i n pi αi по теореме Лагранжа каждый элемент в степени равный порядку группы равен 1. b i p i αi = 1 a i h pi = 1 ⇒ порядок элементов b i равен a p i αi Элемент b = b 1 , b 2 , ..., b n - примитивный элемент, так как порядки всех b взаимно просты, то их НОК равно их произведению. Алгоритм нахождения примитивного элемента 1. Разложить на простые множители. 2. Найти все возможные примитивные элементы. 3. Предполагаемый примитивный элемент s - раз возводим в степени g h pi = 1 (i = 1, ..., s). φ(h − 1) - формула Эйлера. Линейные регистры сдвига с обратной связью Последовательность называется рекурентной, если ее текущий член за- висит от предыдущих членов. Если член последовательности зависит от одного предыдущего элемента, то данную последовательность называют цепью Маркова. Примеры: a n+1 = a n + α - Арифметическая прогрессия a n+1 = a n ∗ q - Геометрическая прогрессия a n+2 = a n+1 + a n - Ряд Фибоначи a n+k = b k−1 a n+k+1 + b k−2 a n+k−2 + · · · + b 0 a n + b - рекурентная последователь- ность k-го порядка Если b = 0, то последовательность однородная. Если последовательность рассматривается над конечным полем, то важной характеристикой являет- ся период . Поиск явного вида n-го члена. Первые k - значений, которые ни от чего не зависят могут быть заданы произвольно: a 0 = (a 1 , a 2 , · · · , a k ) - вектор инициализации. С каждой рекурентной последовательностью связывается ее характеристи- ческий многочлен. x k = b k−1 x k−1 + b k−2 x k−2 + · · · + b 0 5 Успех вычислений зависит от корней многочлена. Идеальный случай, когда корни попарно различны. Пусть α 1 , α 2 , · · · , α k - попарно различные корни характеристического мно- гочлена рекурентной последовательности. Тогда n-й член этой последова- тельности может быть задан в явном виде: a n = β 1 α n 1 + β 2 α n 2 + · · · + β n α n n Где β - решение системы β 1 α 0 1 + · · · + β k α 0 k = a 0 · · · · · · · · · β 1 α k−1 1 + · · · + β k α k−1 k = a k−1 Определитель этой системы - это определитель Вандермонда (W ) и он не равен 0, когда все корни попарно различны. Каждая рекурентная последовательность имеет матрицу: A = 0 0 · · · b 0 1 0 · · · b 1 0 0 · · · b k−1 Пусть P - поле, S 0 , S 1 , · · · Sn - последовательность. Последовательность называется рекурентной степени K: S n+k = a k−1 S n+k−1 + · · · + a 0 S n Так как первые K - элементов не связаны никакими ограничениями, то ¯ S 0 = (S 0 , S 1 , · · · S k−1 ) - вектор инициализации может быть задан произ- вольно. Различных векторов инициализации может быть q k штук. Длина периода. Матричная запись Характеристикой последовательности S является ее период. ¯ S 0 = ¯ 0 ⇒ q k − 1 A (k×k) = 0 0 · · · 0 a 0 1 0 · · · 0 a 1 0 1 · · · 0 a 2 0 0 · · · 1 a k−1 ¯ S 1 = (S 1 , S 2 , · · · S k ) q k −1 6 ¯ S 1 = ¯ S 0 · A n-ый вектор состояния ¯ S n = S 0 · A n Если n-ая степень матрицы А станет единичной матрицей ⇒ ¯ S n = ¯ S 0 и по- следний начнет повторяться. В зависимости от коэффициента a j - единич- ная матрица может не получиться. Сначала предпериод, а потом период. Как только среди векторов состояния появится тот, который был равен, последовательность начнет повторяться, поэтому сумма периода не может быть больше чем q k − 1. Лучший вектор инициализации, который гарантированно дает наибольший период - x k = a k−1 x k−1 + · · · + a 0 - характеристический многочлен. Решение линейного уравнения в кольце вычетов Пусть дано: ax = b(n) d = N OD(a, n) Теорема: Если d не делит b, то уравнение не имеет решение. Если d делит b, то решений будет d штук. Доказательство: Если d не делит b, то вычитая из ax у нас всегда будет получаться число, делящееся на d, значит b никогда не получится. Если d делит b, то a = da 0 b = db 0 n = dn ⇒ a 0 x = b 0 (n 0 ) Так как НОД(a 0 , n 0 ) = 1, то по следствию из алгоритма Евклида, то у a 0 есть обратный по умножению по модулю (n 0 ) ⇒ x 0 = a −1 0 b 0 (n 0 ) Непосредственно проверяется, что x = x 0 + in 0 0 < i < d ⇒ ax = b(n) Решение системы линейных уравнений по разным модулям x 2 + 1 - неприводимый многочлен x 2 + x + 2 - неприводимый многочлен Допустим наш характеристичесий многочлен над GF (3): f (x) = (x 2 + 1)(x 2 + x + 2) Если бы это было над полем R или Q характеристика 0, то нужно было бы добавить корни из этого характеристического уравнения. По теореме о кор- нях неприводимых многочленов поля Галуа добавив корень 1 многочлена, мы автоматически разложим на многочлены все остальные непрерывные многочлены данной степени: α 2 = −1 α 2 = −α − 2 = 2α + 1 7 Из соображения удобств вычислений к полю GF (3) мы добавим корень α 1-го многочлена, который будет удовлетворять соотношению α 2 = 2. По теореме о корнях неприводимых многочленов, корням x 2 + 1 будет α, α 3 : GF (3 2 ) = {0, 1, 2, α, 2α, α + 1, 2α + 1, 2α + 2, α + 2} Следующий шаг: Теперь среди 9 элементов поле GF (3 2 ) нужно найти корни 2-го многочлена (он неприводим). Первый способ: Перебрать все 6 элементов, непринадлежащих полю GF (3). Подставив в многочлен и проверить кто корень? 2 из 6 - корни. Второй способ: Найти корни по формуле решения квадратного уравнения. Возвращаемся к нашему полю GF (2 4 ). Так как α - не является примитив- ным, то нам придется найти примитивный элемент. |GF (2 4 )| = 16 15 = 5 ∗ 3 ⇒ примитивный элемент должен удовлетворрять двум неравенствам: g 3 = 1 g 5 = 1 Функция Эйлера ϕ(15) = ϕ(3)ϕ(5) = 2 ∗ 4 = 8 ⇒ примитивных элементов 8 штук. Алгоритм AES - замена столбцов AES (Advanced Encryption Standard) - основная кодировка c 2002 - 12 ра- ундов, в каждом раунде из исходного ключа по хитрому алгоритму выра- жаются ключ. Каждый раунд состоит из простых преобразований: 1) Сложение с раундом ключом. 2) Преобразование строк 3) Афинное преобразование на байт смотрят как на 8-мерный вектор над GF (2), замена S → As + b (A - циркулянт) Задание №1.1 Это работа с примитивным элементом в поле. Нахождение примитивного элемента p(простое число) в поле GF (p). Так как p = 467, то в поле GF (467) и количество примитивных элементов равно 232(по функции Эйлера). 8 Рис. 1: Непримитивный элемент Рис. 2: Примитивный элемент 2 Рис. 3: Непримитивный элемент 9 Рис. 4: Непримитивный элемент Рис. 5: Примитивный элемент 5 Рис. 6: Примитивный элемент 6 10 Рис. 7: Непримитивный элемент Рис. 8: Примитивный элемент Рис. 9: Непримитивный элемент 11 Рис. 10: Непримитивный элемент Задание №1.2 Решить систему уравнений по модулю p в поле GF (p). p = 467 - было выбранно рандомно в предыдущем заданиии. Следователь- но решить систему уравнений по модулю GF (467). 354x + 17y + 160z = 3 56x + 130y + 6z = 249 43x + 9y + 322z = 5 Рис. 11: Объявление матрицы 12 Рис. 12: Приведение к единичной матрице Рис. 13: Продолжение. Проверка. x = 403 y = 293 z = 128 Задание №1.3 Найти обратимый элемент по модулю GF (p). p = 467 ⇒ GF (467) 13 Рис. 14: Список из всех обратимых элементов Задание №1.4 Решить квадратное уравнение по модулю GF (p). 24x 2 − 365x + 1506 = 0 1. Написать программу, которая вычисляет квадраты всех элементов по- ля GF (p) 14 Рис. 15: Квадраты всех элементов GF (467) 2. Написать программу, которая вычисляет степени примитивного эле- мента поля GF (p) и выяснить какой степенью является дискрименант. Рис. 16: Примитивный элемент 2 в поле GF (467) Рис. 17: Решение квадратного уравнения в поле GF (467) D = 324, x 1 = 115, x 2 = 231. Ответ: 115, 231. Задание №1.5 15 ФИО α = 9 - количество букв фамилии(Присяжнюк). β = 4 - количество букв имени(Анна). γ = 13 - количество букв в отчестве(Александровна). Рис. 18: α β+γ mod 467 Задание №2.1 Зашифровать свое имя по алгоритму RSA Анна - 014140 = 14140 p = 151, q = 97 ⇒ n = p ∗ q = 14647 φ(n) = (p − 1)(q − 1) = n − p − q + 1 = 14647 − 151 − 97 + 1 = 14400 e = 839 - взаимопростое число с φ(n) (e, n) = (839, 14400) - открытый ключ Рис. 19: Зашифрованное число Задание №2.2 Найти 16 - ти значное простое число 16 Рис. 20: 16 - ти значное простое число i Задание №2.3 Линейный регистр сдвига с обратной связью. Пусть рекурентная последовательность задается характерестическим мно- гочленом x 4 + x 3 + x + 1. Следоавтельно, функция обратной связи имеет вид f = b 4 ⊕ b 2 ⊕ b 1 Допустим, изначальным состоянием регистра сдвига была последователь- ность [b 1 , b 2 , b 3 , b 4 ] = [1, 1, 0, 1]. Номер состояния b 1 , b 2 , b 3 , b 4 f = b 4 ⊕ b 2 ⊕ b 1 Генерируемый бит 0 1 1 0 1 1 1 1 1 1 1 0 0 0 2 0 1 1 1 0 1 3 0 0 1 1 1 1 4 1 0 0 1 0 1 5 0 1 0 0 1 0 6 1 0 1 0 1 0 7 1 1 0 1 1 1 То есть генерируемая последовательность такова: [1, 0, 1, 1, 1, 0, 0, 1...]. И период последовательности равен 7. Задание №3 17 Решение СЛУ по различным модулям Пусть дана система: 5x = 13 (mod 17) 2x = 6 (mod 9) 4x = 12 (mod 20) 1. Приведем систему к каноническому виду: Рис. 21: Правая часть системы x = 6 (mod 17) x = 3 (mod 9) x = 3 (mod 20) Решение первого сравнения: x = 6 + 17y Решение второго сравнения: 6 + 17y = 3 (mod 9) ⇒ 17y = 6 (mod 9) ⇒ y = 3 y = 3 + 9z Решение третьего сравнения: x = 6 + 17y = 6 + 17(3 + 9z) = 6 + 51 + 153z = 57 + 153z 57 + 153z = 3 (mod 20) ⇒ z = 2 (mod 20) z = 2 + 20t x = 6 + 17y y = 3 + 9z z = 2 + 20t Общее решение системы: x = 57 + 153(2 + 20t) = 57 + 306 + 3060t = 363 + 3060t x = 363 (mod 3060) Задание №4 18 1. По рекурентной последовательности написать её матрицу A и ха- рактеристический многочлен. Пусть p = 467, тогда будем работать в поле GF (467). k = 4 S 0 = (250, 127, 432, 156) - вектор инициализации ⇒ S n+4 = 250S n+3 + 127S n+2 + 432S n+1 + 156S n - рекурентная последова- тельность. Тогда матрица A: 0 0 0 250 1 0 0 127 0 1 0 432 0 0 1 156 Xарактеристический многочлен: x 4 = 250x 3 + 127x 2 + 432x + 156 2. Найти корни характерестического многочлена, которые лежат воз- можно в поле P. x 4 + 250x 3 + 127x 2 + 432x + 156 = (x + 129)(x + 226)(x + 370)(x + 459) Все четыре корня нам известны - α 1 = 338, α 2 = 241, α 3 = 97, α 4 = 8 3. Найти явную формулу этого многочлена. S n = β 1 α 1 n + β 2 α 2 n + β 3 α 3 n + β 4 α 4 n - явная формула. S 0 = 250 S 1 = 127 S 2 = 432 S 3 = 156 β 1 + β 2 + β 3 + β 4 = 250 β 1 α 1 + β 2 α 2 + β 3 α 3 + β 4 α 4 = 127 β 1 α 1 2 + β 2 α 2 2 + β 3 α 3 2 + β 4 α 4 2 = 432 β 1 α 1 3 + β 2 α 2 3 + β 3 α 3 3 + β 4 α 4 3 = 156 ⇒ β 1 + β 2 + β 3 + β 4 = 250 338β 1 + 241β 2 + 97β 3 + 8β 4 = 127 338 2 β 1 + 241 2 β 2 + 97 2 β 3 + 8 2 β 4 = 432 338 3 β 1 + 241 3 β 2 + 97 3 β 3 + 8 3 β 4 = 156 19 Рис. 22: Объявление матрицы 1 1 1 1 250 338 241 97 8 127 296 173 69 64 432 110 130 155 45 156 Рис. 23: Решение Крамером β 1 = 408 β 2 = 425 β 3 = 166 β 4 = 185 20 4. Явно вычислить последовательность, найти её период для импульс- ной функции. S n = 408α 1 n + 425α 2 n + 166α 3 n + 185α 4 n Период последовательности не больше чем 466, то есть p k − 1. Рис. 24: Нахождение периода Период равен 466. S 466 = 250, S 467 = 127, S 468 = 432 и так далее. 21 |