47. [М50] Некоторая цитата из литературного источника х = ЖхХг, представленная в ASCII-кодах, в зашифрованном виде выглядит как (х? mod N, xi mod Л) =

(14E97EF6C631D92591B89CDBAB48444AO4612C01AA29C2A8FAlOFA804EF7AC3CEO3D7D3667C4D3E132A24A68 E6797FE28660DC3ADF327474B86B0CBD5387A49872CE012269A59B3E4B3BD83B74681A78AD7B6D1772A7451B, 15B026E2AEEO96A9542590184CF62F72B2E8E8DD794AEF8511F2S91E6BC2C8B8A8E48AF1FEO4FF2FD933E73O 92O5A3418DBB9BB8C6A7665DA3O9S31735FE86C741D1261B34CB2668FA34DOC0C28575A2454E3DB0OE408AC7)

В шестнадцатеричных обозначениях, где Л равно

17B2353B9595ECA69FEF80940160C4084286D12S5FFE49D114F2E633F82C88DS224FC4AA6F9104CED2BCA810 BEA76157FFDC78F9656A0ED9B3F6CCAB990O1B8B2671F4EBD09S926FO7F9BEES111E837SDFD71693628AD8D1.

Что собой представляет х?

Проблема распознавания простых чисел из составных и разложения составных чисел на простые множители является одной из самых важных и полезных среди всех арифметических задач.

... Высокое призвание науки в том, кажется, и состоит, чтобы любой вклад в решение такой элегантной и знаменитой проблемы

усердно культивировался.

- к. Ф. ГАУСС (С. F. GAUSS), Disquisitiones Arithmetics. Article 329 (1801)

4.6. ПОЛИНОМИАЛЬНАЯ АРИФМЕТИКА

Изученные нами технологии естественным образом применимы не только к числам, но и к различным математическим величинам. В этом разделе речь пойдет о полиномах, что представляет шаг вперед по сравнению с числами. Формально говоря, полином над S представляет собой выражение вида

и{х) = UnX" +----h щх + Uo, (1)

где коэффициенты и„, ..., ui, uo -элементы некоторой алгебраической системы 5, а переменная х может рассматриваться как формальный символ без определенного значения. Будем полагать, что алгебраическая система S представляет собой коммутативное кольцо с единицей. Это означает, что S допускает операции сложения, вычитания и умножения, удовлетворяющие обычным свойствам: сложение и умножение являются ассоциативными и коммутативными бинарными операциями, определенными на 5, причем умножение дистрибутивно по отношению к сложению. Существует также единичный элемент по сложению О и единичный элемент по умножению 1, такие, что а + 0 = аиа-1 = а для всех а из S. Вычитание является обратной по отношению к сложению операцией, но о возможности деления как об операции, обратной по отношению к умножению, ничего не предполагается.

Полином Оа;"+"-------Оа;"+-ьи„а;"н-----\-uix + uo рассматривается как идентичный

полиному (1), хотя формально он отличается от него.

Мы говорим, что (1) является полиномом степени п со старшим коэффициентом Un, если Un ф 0; в этом случае запишем*

deg(u)=n, e{u) = Un. (2)

Кроме того, по определению

deg(O) = -00, еф) = О, (3)

где О означает нулевой полином, т. е. полином, все коэффициенты которого равны нулю. Мы говорим также, что и{х) - нормированный полином, если его старший коэффициент £{и) равен 1.

Арифметика полиномов состоит, в первую очередь, из сложения, вычитания и умножения; иногда к этим операциям добавляются другие, например, деление, возведение в степень, разложение на множители и поиск наибольшего общего делителя. Сложение, вычитание и умножение определяются естественным образом, как если бы переменная х была элементом 5: мы складьшаем или вычитаем полиномы посредством сложения или вычитания коэффициентов при одинаковых степенях х. Умножение выполняется согласно правилу

(UrX -f • • • -Н Uo){VsX + . . . + Wo) = -f • • • -f Шо,

Wk = UoVk -f uiVk-i Н-----h Uk-ivi -f UkVQ. (4)

В последней формуле Ui и Vj рассматриваются как равные нулю при i > г п j > s соответственно.

* Здесь символ t означает leading {ведущий; в русскоязычной математической литературе - старший). - Прим. перев.

Алгебраическая система S обычно представляет собой множество целых или рациональных чисел. Она может быть и множеством полиномов (с другими, отличными от X переменными); тогда (1) - полином от нескольких переменных. В частности, алгебраическая система S может состоять из целых чисел О, 1, m - 1 со сложением, вычитанием и умножением, выполняемыми по модулю т (см. формулу 4.3.2-(11)); этот важный случай называется полиномиальной арифметикой по модулю т. Особенно важна полиномиальная арифметика по модулю 2, когда каждый коэффициент равен О или 1.

Читатель должен обратить внимание на сходство между полиномиальной арифметикой и арифметикой многократной точности (раздел 4.3.1), где основание счисления b заменено на х. Основное отличие состоит в том, что коэффициент Uk при в полиномиальной арифметике, вообще говоря, никак не связан с соседними коэффициентами Uk±i, так что понятие "перенос" из одного места в другое в полиномиальной арифметике отсутствует. В действительности полиномиальная арифметика по модулю Ь, по существу, идентична арифметике с многократной точностью по основанию b за исключением отсутствия переносов. Например, сравним умножение (1101)2 на (1011)2 в двоичной системе счисления с аналогичным умножением -Ь -ь 1 на -Ь X -ь 1 по модулю 2.

Двоичные числа Полиномы по модулю 2

1101 1101

X 1011 X 1011

1101 1101

1101 1101

1101 1101

10001111 1111111

Произведение этих полиномов по модулю 2 получено путем отказа от всех переносов и составляет х + х + х + х + х + х + 1. Если умножать полиномы так же, как целще числа, без получения остатков по модулю 2, результат будет равен х + х + X* + Зх + х + X + 1; переносы в данном случае также не используются, однако коэффициенты в произведении могут оказаться произвольно большими.

В связи с сильным сходством полиномиальной арифметики и арифметики с многократной точностью нет необходимости подробно обсуждать операции сложения, вычитания и умножения в этом разделе. Однако нужно отметить некоторые аспекты, отличающие практическое использование полиномиальной арифметики от арифметики многократной точности. Очень часто при работе с полиномами наблюдается тенденция к появлению большого количества нулевых коэффициентов и полиномов огромных степеней, а потому желательно использовать специальные формы представления полиномов (см. раздел 2.2.4). Кроме того, арифметика полиномов от нескольких переменных приводит к программам, которые легче всего понять в рамках рекурсии (эта ситуация будет обсуждаться в главе 8). Хотя методы сложения, вычитания и умножения полиномов сравнительно просты и понятны, несколько важных аспектов полиномиальной арифметики достойны специального рассмотрения. В следующих разделах будут обсуждаться деление полиномов и связаннью с ним методы, такие как поиск наибольшего общего делителя и разложение на множители. Мы рассмотрим также проблему эффективного вычисления