Гашков С.Б. Современная элементарная алгебра в задачах и решениях

Подождите немного. Документ загружается.

§ 2.9. Алгебра и криптология 131

2*. Докажите, что отображение x → f(x) = x

mod n всегда имеет 4

неподвижных точки в множестве Z

∗

и девять неподвижных точек в мно

жестве Z

(неподвижная точка отображения

––

это такое число a, которое

переходит в себя при этом отображении).

У к а з а н и е. Примените китайскую теорему об остатках.

3*. Докажите, что если s − 1 будет общим кратным чисел p −1

и q −1, то отображение x → f(x) = x

mod n будет тождественным.

Заметим, что для предотвращения очевидных атак на эту систему ре

комендуется:

а) не выбирать числа p и q слишком близкими друг к другу (реко

мендуется, чтобы их двоичные записи отличались по длине на несколько

разрядов), иначе облегчается возможность факторизации числа n;

б) следить за тем, чтобы число p − 1 не было делителем числа q −1

и наоборот, и вообще чтобы эти числа не имели бы большого общего

делителя, так как тогда возникает возможность найти ключ t перебором;

в) не допускать того, чтобы в разложении ϕ(n) на множители встре

чались только малые простые числа (по той же причине).

Для надежности можно было бы использовать только так называемые

безопасные простые числа, т. е. такие числа p, для которых и число

(p −1)

2 тоже простое. К сожалению, проблема генерации таких чисел

трудна, и до сих пор неизвестно, конечно или бесконечно их количество.

Заметим еще, что не рекомендуется использовать слишком малые чис

ла s и t (так как тогда опять появляется возможность нахождения ключа

перебором, но в случае малого s для этого, правда, нужно суметь пере

хватить одинаковое сообщение, посланное многим разным получателям),

а также такие числа s, что s − 1 будет общим кратным чисел p − 1 и q −1,

например, s = ϕ(n)

2 + 1, так как тогда зашифрованный текст всегда про

сто совпадает с незашифрованным. Кроме того, во всех случаях надо

следить, чтобы случайно не попасть в

неподвижную точку

4*. (Общий секретный ключ.) Нахождение индекса произвольно

го элемента из Z

относительно заданного первообразного корня a

(называемое коротко дискретным логарифмированием) требует весь

ма громоздких вычислений, и при p, состоящем из нескольких сотен

цифр, не под силу и суперЭВМ. Лишь в случае, когда p −1 имеет

только малые простые множители, известен сравнительно быстро рабо

тающий алгоритм дискретного логарифмирования.

На предположении о труднорешаемости задачи дискретного логариф

мирования основана следующая система Диффи

––

Хеллмана * откры-

того распределения ключей. Допустим, что A и B хотят, пользуясь

* У. Диффи и М. Хеллман

––

современные американские математики.

132 Глава II. Числа и группы

публичными каналами связи (например, электронной почтой), выработать

общую секретную информацию (общий ключ). Противник знает о зате

ях A и B и может перехватывать весь их обмен информацией.

Предложите протокол выработки общего ключа, роль которого играет

некоторый элемент из Z

∗

, причем для его выработки требуется обменять

ся двумя элементами из Z

∗

. Каждый из партнеров вычисляет свой эле

мент, пользуясь своим ключом (секретным элементом), а потом, получив

вычисленный партнером элемент, с помощью того же ключа вычисляет

общий ключ (он, разумеется, должен получиться одинаковым у обоих).

Алгоритм вычисления общего ключа должен быть простым, а алгоритм

взлома этой системы (конечно, при отсутствии информации о ключах

партнеров)

––

очень трудоемким.

У к а з а н и е. Возьмите в поле Z

какой

нибудь первообразный ко

рень g и воспользуйтесь тождеством (g

)

= (g

)

5*. (Алгоритм Гельфонда дискретного логарифмирования.) Дискрет

ный логарифм в конечном поле порядка q можно вычислить, сделав не бо

лее C

√

q log

q операций деления и не более C

√

q log

q операций срав

нения элементов поля.

6*. (Разделение секретного ключа на части.) Допустим, что вам по

ручили организовать доступ к секретной информации на компьютере для

трех сотрудников банка так, чтобы они, только собравшись втроем, смог

ли получить ее. Каждому вы сообщаете ключ

––

некоторое большое (на

пример, стозначное) число, которое он хранит в секрете от остальных.

Паролем, который открывает секретную информацию, является неизвест

ное никому из них число, которое, однако, можно быстро определить (ра

зумеется, с помощью компьютера) по трем упомянутым ключам. В случае

же отсутствия одного из них для определения пароля придется (даже зная

алгоритм определения пароля по ключам) перебрать 9 ·10

вариантов

возможного значения неизвестного ключа (а это пока не доступно даже

суперЭВМ). Кроме того, для надежности вы можете периодически менять

ключи. Это смогут сделать даже сами работники банка (договорившись

только о размерах ключей, чтобы гарантировать их отличие друг от друга,

и выбирая в качестве ключей, например, числа вида 2

+ 1), и сохранить

пароль в тайне даже от вас.

Предложите алгоритм определения пароля по ключам, основанный

на применении китайской теоремы об остатках.

У к а з а н и е. Следующий алгоритм принадлежит Шамиру *. Вы

берем 3 больших попарно взаимно простых числа, например, числа

Ферма a

= 2

+ 1, a

= 2

n+1

+ 1, a

= 2

n+2

+ 1. Пусть i

компаньон

* А. Шамир

––

современный израильский математик.

§ 2.9. Алгебра и криптология 133

в качестве ключа выбирает произвольное число k

в пределах от 1

до a

−1. Тогда, собравшись вместе, они могут выработать пароль k,

взяв в качестве него такое число в пределах от 1 до a −1, a = a

которое при делении на a

дает в остатке k

. Как было показано в этом

параграфе, число k можно вычислить по формуле k = k

′

− [k

′

a]a, где

′

+kn

, n

−a

=1, m

, j 6=k6=i 6= j.

Для вычисления n

можно применить алгоритм Евклида. Нетрудно на

писать программу для компьютера, которая будет вычислять пароль k

после того, как

компаньоны

, таясь друг от друга, введут в него свои

ключи. Положим N = 2

. Если двое, в тайне от третьего, захотят найти

ключ k, то им придется перебрать все возможные варианты выбора тре

тьего ключа (потому что разным способам выбора ключей соответствуют

разные значения k), т. е. перебрать не менее 2

вариантов.

7*. Предложите алгоритм разделения секрета со свойствами, ана

логичными предыдущему, но основанный на лагранжевой интерполяции.

Глава III. Многочлены

§ 3.1. Кольцо многочленов

Возьмем произвольное кольцо K и назовем многочленом над этим

кольцом формальную сумму

f(x) = a

+ a

n−1

+ ... + a

x + a

где элементы a

, a

, ..., a

n−1

, a

, n > 0, принадлежат кольцу K, а x

––

не входящий в кольцо символ переменной.

Определение 65. Элементы кольца a

, ..., a

называются коэффи-

циентами многочлена. Будем рассматривать только многочлены, у ко

торых старший коэффициент a

отличен от нуля.

Степенью многочлена называется в этом случае число n, обозна

чаемое далее как deg f(x).

Элементы кольца K , не равные 0, будем рассматривать как мно-

гочлены нулевой степени. Нуль также считаем многочленом. Степень

у нулевого многочлена не определена.

Определение 66. Многочлены

f(x) = a

+ a

n−1

+ ... + a

x + a

g(x) = b

+ a

m−1

+ ... + b

x + b

называются равными, если m = n и равны все коэффициенты при соот

ветствующих степенях переменной, т. е. a

= b

, i = 0, 1, .. ., n.

Определим арифметические операции на множестве многочленов K [x]

с коэффициентами из кольца K.

Определение 67. Назовем суммой многочленов

f(x) = a

+ a

n−1

+ ... + a

x + a

g(x) = b

+ a

m−1

+ ... + b

x + b

многочлен h(x), коэффициент которого при x

равен c

= a

+ b

для лю

бого i = 0, 1, .. ., max{n, m}.

Если один или несколько старших коэффициентов у рассматривае

мой суммы равны нулю (а это возможно лишь при n = m), то они просто

§ 3.1. Кольцо многочленов 135

удаляются из нее, так, чтобы старший из оставшихся коэффициентов

был отличен от нуля. Многочлен, имеющий только один ненулевой коэф

фициент, называется одночленом. Аналогично определяются двучлены

и трехчлены.

Определение 68. Произведением многочленов

f(x) = a

+ a

n−1

+ ... + a

x + a

g(x) = b

+ a

m−1

+ ... + b

x + b

называется многочлен h(x), коэффициент которого при x

равен

j+k=i

З а м е ч а н и е. Указанную сумму можно понимать и как сумму

j=0

i−j

если условиться, что все входящие в нее коэффициенты с индексами,

не лежащими в пределах от 0 до n, равны нулю.

Теорема 57. Множество всех многочленов над кольцом K

––

кольцо.

Д о к а з а т е л ь с т в о. Нулевым элементом кольца многочленов яв

ляется нулевой многочлен, отождествляемый с нулем кольца K , а еди

ничным

––

единица кольца K .

Обратным элементом для произвольного многочлена

f(x) = a

+ a

n−1

+ ... + a

x + a

относительно операции сложения является многочлен

−f(x) = (−a

+ (−a

n−1

+ ... + (−a

)x + (−a

получающийся из исходного

сменой знака

у всех коэффициентов. По

этому вычитание многочленов осуществляется так же, как и сложение,

но с заменой операции сложения коэффициентов на операцию вычитания.

Выполнение аксиом коммутативной группы относительно операции

сложения непосредственно вытекает из справедливости этих аксиом для

кольца коэффициентов, которое, кстати, можно считать содержащимся

в соответствующем кольце многочленов.

Легко видеть, что каждый многочлен равен сумме всех своих одно

членов.

136 Глава III. Многочлены

Аксиома дистрибутивности (другими словами, распределительный за

кон умножения относительно сложения) для кольца многочленов легко

следует из тождеств

j+k=i

+ c

) =

j+k=i

а аксиома ассоциативности умножения для кольца многочленов легко

следует из аксиомы дистрибутивности, если с ее помощью выполнять

умножение многочленов, разбивая их на суммы одночленов и складывая

потом получившиеся произведения одночленов, для которых выполнение

ассоциативного закона относительно умножения очевидно.

Теорема 58. Степень суммы многочленов над кольцом не пре-

восходит наибольшей из степеней слагаемых.

Д о к а з а т е л ь с т в о. Для двух слагаемых это очевидно из опре

деления операции сложения. Для случая многих слагаемых это легко

доказывается по индукции.

Напомним, что областью целостности называется кольцо без де

лителей нуля.

Упражнение 56. Докажите, что

а) кольцо целых чисел является областью целостности;

б) любое поле также является областью целостности.

Теорема 59. В кольце многочленов над областью целостности

степень произведения ненулевых многочленов равна сумме степе-

ней сомножителей.

Д о к а з а т е л ь с т в о. Доказательство для случая двух сомножите

лей следует из определения умножения многочленов: наибольшая воз

можная степень x в произведении многочленов f(x) = a

+ a

n−1

+ ... + a

x + a

, a

6= 0, и g(x) = b

+ a

m−1

+ ... + b

x + b

6= 0, равна n + m, т. к. a

6= 0 согласно свойству области целост

ности. Для случая нескольких сомножителей это легко доказывается

по индукции.



Если в кольце K есть делители нуля, то теорема 59 неверна.

Упражнение 57. Например, если K = Z

, то

3x ·

2x =

0, и в этом

случае степень произведения меньше суммы степеней сомножителей. Для

произвольного кольца коэффициентов степень произведения не больше

суммы степеней сомножителей.

Определение 69. Если для многочленов f(x) и g(x) 6= 0 справедливо

разложение f(x) = g(x) ·h(x) + r(x), где h(x) и r(x)

––

некоторые другие

многочлены, причем deg r(x) < deg g(x), то h(x) называется частным,

а r(x)

––

остатком.

§ 3.1. Кольцо многочленов 137

Теорема 60 (о делении с остатком). Для любых многочленов f(x)

и g(x) 6= 0 над произвольным полем F частное и остаток существу-

ют и определены однозначно как многочлены над тем же полем F.

Д о к а з а т е л ь с т в о. Существование частного и остатка очевидно

в случае deg f(x) < deg g(x).

В случае deg f(x) > deg g(x) применим для их нахождения следующий

алгоритм деления с остатком.

Предположим, что f(x) = a

+ a

n−1

+ ... + a

x + a

и g(x) =

= b

+ a

m−1

+ ... + b

x + b

, тогда f(x) −

n−m

g(x) = h(x),

причем deg h(x) < n. Затем поделим h(x) на g(x) и т. д. Процедура за

кончится, так как на каждом шаге будет понижаться степень разности

до тех пор, пока она не станет меньше m = deg g(x). Тогда получим, что

f(x) = g(x) ·ϕ(x) + r(x), причем deg r(x) < deg g(x).

Доказательство единственности проведем от противного. Пусть

f(x) = g(x) ·h

(x) + r

(x) = g(x) ·h

(x) + r

(x),

тогда g(x) · (h

(x) −h

(x)) = r

(x) −r

(x). Если бы h

(x) −h

(x) 6= 0,

то степень левой части была бы больше степени правой. То есть

(x) =h

(x), а значит, и r

(x) = r

(x). Противоречие.

З а м е ч а н и е. Для доказательства единственности требуется, по

крайней мере, чтобы кольцо коэффициентов было областью целостности.

Для доказательства существования в случае, если K не поле, достаточно

считать, что старший коэффициент g(x) равен 1.

Далее у нас изредка будут встречаться и многочлены от нескольких

переменных. Определения основных понятий в этом случае, как прави

ло, являются естественными обобщениями соответствующих определений

для одной переменной.

Назовем многочленом над кольцом K от переменных x

, ..., x

конечную формальную сумму

f(x) =

, ..., i

...i

... x

где коэффициенты a

...i

принадлежат кольцу K , а x

, ..., x

––

не входя

щие в кольцо символы переменных.

Определение 70. Многочлены

f(x) =

, ..., i

...i

... x

, g(x) =

, ..., i

...i

... x

называются равными, если попарно равны все их коэффициенты

...i

= b

...i

138 Глава III. Многочлены

Определение 71. Многочлен, имеющий только один ненулевой ко

эффициент, называется одночленом. Степенью одночлена называется

сумма степеней всех его переменных. Степенью многочлена называется

максимальная из степеней всех его одночленов. Одночлены с макси

мальной степенью называются старшими одночленами. Так же назы

ваются их коэффициенты.



Старших одночленов может быть несколько.

П р и м е р ы. 1. Многочлен x

+ x

––

неполный квадрат суммы.

2. Если переменных немного, то стараются обходится без индексов:

+ xy + y

Будем рассматривать только многочлены, у которых старшие коэф

фициенты отличны от нуля.

Элементы кольца K , не равные 0, будем рассматривать как много-

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

Множество всех определенных выше многочленов от переменных

, ..., x

обозначают K[x

, ..., x

]. Определим арифметические опера

ции на этом кольце.

Определение 72. Назовем суммой многочленов

f(x) =

, ..., i

...i

... x

, g(x) =

, ..., i

...i

... x

многочлен

f(x) + g(x) =

, ..., i

...i

+ b

...i

... x

а произведением

––

многочлен, получающийся из суммы

f(x) g(x) =

...,i

...i

... j

+ j

... x

+ j

приведением подобных членов.

П р и м е р ы. 1. x

−y

= (x −y) (x + y).

2. x

−y

= (x −y) (x

+ xy + y

3. x

+ y

= (x + y) (x

−xy + y

4. x

−y

= (x −y)(x

n−1

+ x

n−2

y + .. . + xy

n−2

+ y

n−1

5. x

2n+1

+ y

2n+1

= (x + y) (x

−x

2n−1

y + ... − xy

2n−1

+ y

6. Еще примерами могут служить биномиальная и полиномиальная

теоремы.

§ 3.1. Кольцо многочленов 139

Аналогично случаю одной переменной доказывается следующая тео

рема.

Теорема 61. Множество многочленов K[x

, . .., x

] образует це-

лостное кольцо относительно операций сложения и умножения.

Нулевым элементом кольца многочленов является нулевой мно-

гочлен, отождествляемый с нулем кольца K , а единичным

––

едини-

ца кольца K .

Обратным элементом для произвольного многочлена f(x) отно-

сительно операции сложения является многочлен, получающийся

из исходного сменой знака у всех коэффициентов. Каждый много-

член равен сумме всех своих одночленов.

Степень суммы многочленов над кольцом не превосходит наи-

большей из степеней слагаемых.

Теорема 62. В кольце многочленов над областью целостности

степень произведения ненулевых многочленов равна сумме степе-

ней сомножителей.

Верна также

Теорема 63. Кольца K [x

, .. ., x

] и (K [x

, . .., x

n−1

]) [x

] изоморфны.

Д о к а з а т е л ь с т в о. Для установления изоморфизма достаточно

представить любой многочлен

f(x) =

, ..., i

...i

... x

как многочлен от одной переменной x

f(x) =



...i

... x

n−1



но с коэффициентами из кольца K[x

, ..., x

n−1

]. Например,

+ x

= x

+ x

) + x

при этом степень полученного многочлена от x

называется степенью

по x

исходного многочлена от переменных x

, ..., x

Упражнение 58. Докажите аккуратно последние три теоремы.



Деление с остатком на многочлены нескольких переменных так

просто не переносится.

Задачи и упражнения к § 3.1

В этом цикле задач рассматриваем только многочлены над полем ра

циональных чисел.

140 Глава III. Многочлены

1. Найдите сумму коэффициентов многочлена (1−1998x +1999x

)

2001

2. Сравнить коэффициенты при x

1994

в многочленах

а) (1 −1994x + 1993x

)

2000

и (1 + 1994x + 1993x

)

2000

;

б) (1 −1994x

+ 1993x

)

2000

и (1 + 1994x

+ 1993x

)

2000

3. Найдите коэффициент при x

в многочлене

(1 + x)

1000

+ x(1 + x)

999

+ ... + x

999

(1 + x) + x

1000

4. Найдите остаток от деления x + x

+ x

+ ... + x

на: а) x − 1;

б)* x

−1.

5. Многочлен при делении на x − a дает остаток b, а при делении

на x −c

––

остаток d. Какой остаток будет при делении на (x −a) (x −c)?

6*. Найдите коэффициент при x

в частном от деления x

1994

−1 на

+ x

+ 2x

+ x + 1.

У к а з а н и е. Сначала поделить с остатком на x

−1, а потом умно

жить на многочлен

−1

+ x

+ 2x

+ x + 1

7*. Найдите все многочлены P(x), для которых справедливо тожде

ство

xP(x −1) = (x −26)P(x).

8*. Пусть f(x) = 1 + x + x

+ x

. Найдите остаток от деления

f(x

) на f(x).

9*. Многочлен P(x) с а) натуральными; б) целыми коэффициентами

при любом n принимает натуральное значение с суммой десятичных

цифр s(n). Докажите, что последовательность s(n) содержит бесконечно

много одинаковых чисел.

10. Многочлен от двух переменных x

1994

+ 1 нельзя представить

в виде произведения двух многочленов от переменных x и y соответст

венно.

11. Разделить многочлен

а) (x + 1)

−x

−2x −1 на x(x + 1) (2x + 1);

б) nx

n+1

− (n + 1)x

+ 1 на (x − 1)

12. Если x −1 делит P(x

), то x

−1 делит P(x

13*. При каком целом a многочлен x

+x +90 делится на x

−x +a?