Научная литература
booksshare.net -> Добавить материал -> Математика -> Коблиц Н. -> "Курс теории чисел и криптографии" -> 22

Курс теории чисел и криптографии - Коблиц Н.

Коблиц Н. Курс теории чисел и криптографии — Москва: Научное изд-во ТВП, 2001. — 254 c.
Скачать (прямая ссылка): theory-chisel-kriptographii.djvu
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 125 >> Следующая


Предложение II. 1. 3. Существует такая последовательность простых чисел р, что случайно выбранный в Fp элемент g оказывается образующим с вероятностью, стремящейся к нулю с ростом р.

Доказательство. Пусть {fij}j=2,3 — любая последовательность натуральных чисел, которые с ростом j к оо делятся на все большие количества последовательных простых чисел 2,3,5,7,... Можно взять, например, Uj = j\. Выберем в качестве Pj любое такое простое число, что Pj = 1 (mod rij). Почему такой выбор возможен? Это следует из теоремы Дирихле о простых числах в арифметической прогрессии, которая утверждает, что если целые числа кип взаимно просты, то существует бесконечно много простых чисел, сравнимых с к по модулю п. (Более того, простые числа «равномерно распределены» среди возможных вычетов к mod п, т.е. доля тех простых, которые сравнимы с данным к по модулю п, составляет 1/</з(п). Но этот факт нам здесь не понадобится.) Тогда множество простых, делящих pj — 1, содержит в себе простые, делящие rij, и, значит,

40

ГЛ. II. КОНЕЧНЫЕ ПОЛЯ И КВАДРАТИЧНЫЕ ВЫЧЕТЫ

V(Pj - 1

«, П (і-})-

простые l\rij

При j -> OO ЭТО Произведение СТреМИТСЯ к Пвсе простые ((1 ~ '

которое есть 0 (см. упражнение 23 §1.3). Предложение доказано.

Существование и единственность конечных полей с числом элементов, равным степени простого числа.

Как существование, так и единственность мы установим, доказав, что конечное поле с q = элементами есть поле разложения многочлена Xя — X. Следующее предложение показывает, что для каждого числа q, равного степени простого числа, существует одно и (с точностью до изоморфизма) только одно конечное поле с q элементами.

Предложение II. 1.4. Если F9 есть поле с q = элементами, то каждый его элемент удовлетворяет уравнению Xя — X = Ou F9 — это в точности множество корней этого уравнения. Обратно, для любой степени простого q = р^ поле разложения над Fp многочлена Xя — X есть поле из q элементов.

Доказательство. Предположим сначала, что F9 — конечное поле. Так как порядок каждого ненулевого элемента делит g — 1, такой элемент должен удовлетворять уравнению Xя 1 — 1 = О, а следовательно, и уравнению Xя — X = 0. Конечно, элемент 0 также удовлетворяет последнему уравнению. Таким образом, все элементы поля — корни многочлена Xя — X степени q. Так как этот многочлен не может иметь более q корней, его корни — в точности элементы F9. Заметим: это означает, что F9 есть поле разложения для многочлена Xя — X, т.е. наименьшее расширение Fp, которое содержит все его корни.

Обратно, пусть q = р^ есть степень простого числа р и F — поле разложения над Fp многочлена Xя — X. Заметим, что Xя - X имеет производную qX4 1 — 1 = — 1 (так как q кратно р и, следовательно, равно нулю в Fp). Поэтому Xя - X не имеет общих корней с производной (у которой вообще корней нет) и, следовательно, не имеет кратных корней. Поэтому F должно содержать, по крайней мере, q различных корней Xя - X. Однако мы утверждаем, что множество из q корней уже составляет поле. Ключевым является тот факт, что сумма и произведение корней многочлена Xя — X — снова его корни. Это нетрудно проверить для произведения: если а и b — корни многочлена, то ая = а, Ья = Ь и, значит, (ab)4 - ab = аяЬч - ab = ab - ab = О, т.е. ab — корень Xя - X. Чтобы убедиться в том, что сумма а + Ь также есть корень Xя - X, мы установим важное свойство полей ха-

§ 1. КОНЕЧНЫЕ ПОЛЯ

41

рактеристики р.

Лемма. Для любых элементов а, Ь поля характеристики р выполняется соотношение (a + b)p = ар + Ьр.

Утверждение леммы следует из того, что все промежуточные члены в биномиальном разложении Ej=o (j)a^P 3 обращаются в нуль, так как р!/((р — J)IjI) делится нар, если 0 < j < р.

2

Последовательное применение леммы дает: ap + bp = (a + b)p,ap +

2 2

bp = (ар + 6Р)Р = (a + b)p ,..., а4 + Ьч = (а 4- б)9. Таким образом, если aq = а и bq = 6, то (а + b)4 = а4 + Ьч = а + 6, и а + & есть корень А'9 — А\ Мы заключаем теперь, что множество из q корней есть наименьшее поле, содержащее все корни многочлена Xя — X, т. е. поле разложения этого многочлена есть поле из q элементов. Предложение доказано.

По ходу доказательства мы показали, что возведение элементов в степень р сохраняет сложение и умножение. В следующем предложении мы выведем другие важные следствия этого факта.

Предложение II. 1.5. Пусть F9 — конечное поле из q = р* элементов и пусть а — отображение F9, при котором элементу а сопоставляется ар: о~(а) = ар. Тогда а есть автоморфизм поля F9 (т. е. взаимно однозначное отображение поля в себя, сохраняющее сложение и умножение). Элементы F9, не изменяющиеся при действии сг, — это в точности элементы простого поля Fp; f-я степень а есть тождественное отображение, и меньшие степени а этим свойством не обладают.

Доказательство. Отображение возведения в степень всегда сохраняет умножение, а сохранение сложения вытекает из леммы в доказательстве предложения II. 1. 4. Заметим, что j-я степень а (результат j-кратного применения а) есть отображение а3: а ь-> ар . Таким образом, неподвижные элементы отображения а3 — это корни
Предыдущая << 1 .. 16 17 18 19 20 21 < 22 > 23 24 25 26 27 28 .. 125 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed