?

Log in

No account? Create an account
немного про конечные поля - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

немного про конечные поля [июн. 5, 2018|11:40 pm]
Anatoly Vorobey
[Tags|]

  • свалка ссылок и выписок про историю конечных полей
  • постараюсь вкратце объяснить для нематематиков, чтоб совсем скучно не было, но лишь вкратце
  • математики называют "полем" набор чисел, с которыми можно делать обычные операции плюс, минус, умножить, делить (кроме деления на ноль), с обычными их свойствами: от перестановки слагаемых сумма не меняется, можно раскрывать скобки, итд. итд.
  • например, все рациональные числа (т.е. положительные и отрицательные целые и дроби) это поле, обозначают Q
  • все действительные числа (с десятичной запятой) это поле, обозначают R
  • все комплексные числа (...) это поле, обозначают C
  • но кроме того, бывают поля конечного размера, в них всего конечный набор "чисел"
  • самый простой пример - берем простое число p и считаем всё по модулю p (то есть берем остатки от деления на p). Например, p=5, тогда у нас в поле есть числа {0,1,2,3,4}, плюс и умножить как обычно, но по модулю p, 3*3 mod 5 = 9 mod 5 = 4, поэтому в этом поле 3*3=4. Казалось бы, мы не можем делить, потому что нет дробей типа 1/2, но оказывается, что из-за "по модулю" все можно поделить: 1 поделить на 2 будет 3, потому что 3*2 = 1 по модулю 5. Это поле называется F_5. Для любого простого p есть поле F_p.
  • если p не простое число, то это не работает и поля нет, потому что не все "делится": например, по модулю 6 нельзя поделить 1/3, потому что 3*x всегда либо 0 либо 3 по модулю 6, и не может быть 1.
  • поля вида F_p изучались начиная с 18 века, особенно много для их изучения сделал Эйлер (он конечно не называл это так, с его точки зрения он изучал свойства операций по модулю), Лежандр, потом Гаусс
  • есть и другие конечные поля, не только вида F_p, и их впервые построил Эварист Галуа, гениальный французский математик, погибший на дуэли в возрасте 21 года
  • у поля вида F_p размер (число элементов) ровно p, от 0 до p-1. У любого конечного поля размер обязан быть степенью простого числа, какое-то p^n. Например, есть конечное поле размером 9 (степень тройки), но нет поля размером 6 (не степень простого). У этого факта есть очень простое и потрясающе красивое доказательство, которое требует, однако, знания высшей математики, см. конец записи
  • возьмем какое-то конечное поле, например F_p: {0,1,2,3,4} по модулю 5, возьмем какой-то ненулевой элемент и начнем умножать на самого себя, рано или поздно мы придем к 1. Например: 4*4 = 16 = 1 mod 5, пришли всего за один шаг. С другой стороны, 3*3=4 mod p, (3*3)*3=4*3=12=2 mod p, (3*3*3)*3=2*3 = 6 = 1 mod p. То есть 3->4->2->1, по дороге к 1 мы прошли сквозь все ненулевые элементы. Если есть число, которое по модулю p проходит сквозь все ненулевые остатки, если его возводить в степень, то оно называется "примитивный элемент". В поле F_5, как мы увидели, 3 примитивный элемент, а 4 нет.
  • есть теорема: в любом конечном поле есть примитивный элемент. На современном языке это звучит так: "мультипликативная группа конечного поля циклична".
  • впервые эту теорему доказали только для всех F_p, а не конечных полей вообще, потому что это было до Галуа, и про другие поля не знали.
  • первое подробное доказательство есть в книге Гаусса Disquisitiones Arithmeticae (1801), параграф 52. У этой книги есть английский перевод, его можно скачать в обычном месте. Кроме того, есть доказательство Эйлера на четверть века раньше, и Лежандра между ними, но они не столь точные, как доказательство Гаусса
  • согласно Гауссу, в доказательстве Эйлера есть две "дыры", хотя Андре Вейль, знаменитый математик 20 века, написавший книгу об истории теории чисел, пишет в ней, что Гаусс придрался к Эйлеру и серьезных проблем с его доказательством нет
  • доказательство Эйлера есть в его статье Demonstrationes circa residua... (Е449, 1772). Эта статья до сих пор не переведена с латыни, как и большинство трудов Эйлера. Есть проект перевода всех непереведенных работ Эйлера, и есть определенный прогресс.
  • Галуа в своей работе про другие конечные поля (не F_p), просто пишет, что в них наличие примитивного элемента доказывается "аналогично" случаю F_p. Это в общем верно, если использовать доказательство Гаусса (но не Эйлера).
  • у теоремы про примитивный элемент есть несколько простых доказательств, которые можно сформулировать на современном языке. В этой заметке Кита Конрада собрано 7 доказательств. Они сформулированы для F_p, но 6 из них работают без изменений для любого конечного поля.
  • почти все доказательства пользуются следующим фактом, который верен в любом поле (не только конечном): у многочлена степени n не может быть больше n корней. Например, у квадратного уравнения есть не более 2 корней, у кубического не более 3, итд. Это может показаться тривиальным, но требует доказательства. В конечном поле именно этот факт позволяет доказать, что есть примитивный элемент.
  • интересный факт: до сих пор никто не знает, как найти примитивный элемент для данного F_p. Например, 97 простое число, значит есть примитивный элемент в F_97 (даже больше одного): может, это 2? может, 3? может, 4? Как узнать? Лучше чем пробовать возводить в степень и смотреть, что получится, математики пока не придумали.
  • мне интересно было, есть ли другие доказательства этой теоремы, не пользующиеся этим фактом о корнях многочленов, и как ее первоначально доказывали, когда придумали. Доказательств, не пользующихся фактом про многочлены, я не нашел (кроме конкретного случая F_p, см. седьмое доказательство Конрада). Первоначальные док-ва Гаусса и Эйлера уже пользовались фактом о корнях многочлена, хотя они конечно не оперировали понятиями "многочлен" или "поле". Гаусс просто и элегантно доказывает этот факт индукцией по степени многочлена (пар. 43 его книги). На современном языке это немедленно следует из алгоритма деления многочленов с остатком в кольце многочленов F[x] над полем F.
  • рекомендую отличную статью Heinz Liineburg, "On the Early History of Galois Fields", Finite Fields and Applications 1999, p. 341. Рассказывает более подробно и точно материал, описанный выше, и многое другое. Книжка есть в обычном месте.
  • Историческая книга Андре Вейля называется "Number theory: an approach through history. From Hammurapi to Legendre". Я собираюсь ее прочитать
  • приложение. Как доказать, что размер любого поля степень простого числа. Пусть есть конечное поле F. Выделим его "простое подполе" P следующим образом: 0, 1, 1+1, 1+1+1, .... пока не будет опять 0. Число элементов в простом подполе должно быть простым p, потому что иначе это не поле (если например число элементов p*q, то (1+1+1... p раз)(1+1+1... q раз) = 0). Все поле F может теперь быть рассмотрено как векторное пространство над полем P. Если размер базиса в этом пространстве n, то число элементов F равно p^n, все.
СсылкаОтветить

Comments:
[User Picture]From: utnapishti
2018-06-05 08:50 pm
[Боюсь, что большинству не-математиков слово "модуль" знакомо исключительно в смысле "absolute value".]
(Ответить) (Thread)
[User Picture]From: avva
2018-06-05 10:05 pm
Добавил объяснение про остаток, может, поможет :)
(Ответить) (Parent) (Thread)
[User Picture]From: livelight
2018-06-05 08:59 pm
> есть и другие конечные поля, не только вида Z_p, и их впервые построил Эварист Галуа, гениальный французский математик, погибший на дуэли в возрасте 21 года

А можете на пальцах какой-нибудь простой пример привести?
(Ответить) (Thread)
[User Picture]From: buddha239
2018-06-05 09:02 pm
Как все Ваши Z_p глаза режут - просто не передать!:)
(Ответить) (Thread)
[User Picture]From: xgrbml
2018-06-05 09:18 pm
С языка сняли. F_p это, или Z/pZ.

Z_p --- то ж кольцо целых p-адических чисел. Про него, кстати, тоже можно в таком духе рассказать.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: timur0
2018-06-05 09:03 pm
"Арифметические исследования" Гаусса переведены и на русский.
(Ответить) (Thread)
[User Picture]From: avva
2018-06-05 09:31 pm
Спасибо, не знал!
(Ответить) (Parent) (Thread)
[User Picture]From: vladimir000
2018-06-05 09:17 pm
> у многочлена степени n не может быть больше n корней

Я, все-таки,укушен Гауссом а не Галуа, для меня это комбинация утверждений "у многочлена степени n имеется минимум один корень" оно же дама с собачкой) + линейное уравнение имеющее два корня тривиально;)
(Ответить) (Thread)
From: (Anonymous)
2018-06-06 04:58 pm
> у многочлена степени n имеется минимум один корень

Это только в специально обученных полях.
(Ответить) (Parent) (Thread)
From: (Anonymous)
2018-06-05 10:41 pm
Википедия говорит, что Эварист Галуа в возрасте двадцати лет погиб, а не 21-го. Совершенно малозначительный факт, но решил указать :)
(Ответить) (Thread)
From: (Anonymous)
2018-06-05 11:12 pm
> математики называют "полем" набор чисел

Не чисел, а объектов. Скажем, функций или классов. Это важно, так как ниже вы пишете про конечные поля порядка p^n, и у читателя может сложиться впечатление, что это такие же поля остатков по модулю как F_p, просто у них модуль составной, а это не так.
(Ответить) (Thread)
[User Picture]From: kray_zemli
2018-06-06 04:55 am
А если математики научатся легко находить примитивный элемент, скажется ли это как-то на надёжности существующих криптографических алгоритмов?
(Ответить) (Thread)
[User Picture]From: buddha239
2018-06-06 06:03 am
Насколько я понимаю, нет. Скорее, немного упростит шифрование. Впрочем, реальных проблем эта задача, вроде бы, и так не создает.
(Ответить) (Parent) (Thread)
[User Picture]From: 38irtimd
2018-06-11 12:40 pm
не знал, кстати, что это именно Галуа открыл F_{p^n}. в математическом французском конечные поля называют "corps de Galois", а я как-то не придавал значения.
(Ответить) (Thread)
[User Picture]From: avva
2018-06-12 10:30 am
Здорово, не знал, что так называют.
(Ответить) (Parent) (Thread)