Поле является алгебраическим понятием, которое может быть определено как множество, имеющее не менее двух элементов, над которыми заданы две бинарные ассоциативные и коммутативные операции — сложения и умножения. Кроме того, для существования поля нужны два особых элемента — нуль 0, задающий правило сложения а + 0 = а, и единица 1 для задания правила умножения а*1 = 1. Определено также понятие противоположного элемента -а, такого что а + (-а) = 0, и обратного элемента а-- ¹ , такого что a- ¹ а = 1. Поле характеризуется размером р и целым положительным целым d, называемым степенью расширения.

Пакет задает набор функций GF[p] [{k}], GF[p,l] [{k}], GF[p, {0,1}] [{k}], GF[p,d] HGF[p,ilist] [elist], действие которых иллюстрируют следующие примеры:

Вряд ли подробное их описание заинтересует большинство читателей. Специалистов по полям не затруднит более детальное знакомство с этими функциями в разделе Add-ons справочной базы данных. Там же можно найти описание ряда других функций, относящихся к теории конечных полей.

Оценка интервалов изоляции корней полиномов — Rootlsolation

Следующие функции подпакета Rootlsotation позволяют оценивать интервалы изоляции для действительных и комплексных корней полиномов:

• CountRoots [poly, {x,ml,m2} ] — возвращает число корней полинома poly от переменной х в комплексном интервале {ml, m2 };
• RealRootsIntervals [poly] — возвращает разделенный интервал изоляции для вещественных корней полинома poly;
• RealRootsIntervals [polyl,poly2,...] — возвращает разделенные интервалы изоляции для вещественных корней нескольких полиномов;
• ComplexRootsIntervals [poly] — возвращает разделенный интервал изоляции для комплексных корней полинома;
• ComplexlRootsIntervals [polyl, poly2,...] — возвращает разделенные интервалы изоляции для комплексных корней нескольких полиномов;
• Contractlnterval [a,n] — возвращает интервал изоляции для числа а с точностью, задаваемой числом знаков результата п.

Если конечные поля — понятие достаточно экзотическое, то полиномы встреча- ются сплошь и рядом во многих математических и научно-технических расчетах. В пакете расширения Algebra определен ряд новых операций над полиномами. Начнем их рассмотрение с функции PolynomialExtendedGCD:

• PolynomialExtendedGCD [polyl, poly2 ] — возвращает наибольший общий делитель двух полиномов;
• PolynomialExtendedGCD[polyl,poly2,Modulus->p] —возвращает наи- больший общий делитель двух полиномов по модулю р.

<<Algebra"PolynomialExtendedGCD

PolynomialExtendedGCDlxл2 + 3 х + 2, Expand[(x + 1)(х + 2)], Modulus->7]

{2+ Зх+х2, (0, 1}}

PolynomialExtendedGCD[

Expand[ ((12+1) z^2 + 5 z + I) (I z + 3)], Expand[ ((9+1) z + (3+1)) ((31) z +9)]]

{-31+z,

{- 2261/3341+ 710I/3341( 35/3341- 3951/10023)+ (5959/20046- 20531/20046)z}}

Далее следует функция PolynomialPowerMod [polyl, n, (poly2, р} ], которая является существенно ускоренной версией функции PolynomialMod.

• степени ускорения свидетельствует следующий пример:

<<Algebra`PolynomialPowerMod`

Timing[PolynomialPowerMod[1 + х, 200, х^З + x^2 + 1, Prime[4750]]][[1]], Timing [ PolynomialMod [ (1 + x)^200, x^ + х^2 + 1, Prime [4750] ]][[1]]

{0. Second, 2.37 Second)

В данном случае вычисления по функции PolynomialPowerMod оказались вы- полненными менее чем за 0.01 с, что дает нулевой результат.

Еще одна функция в трех ее модификациях работает с симметричными полиномами:

• SymmetricReduction [ {xl,...,xn}, k] — возвращает симметричный полином степени k по переменным {х1,..., хn);
• SymmetricReduction [f, {xl,...,xn}] — возвращает часть полинома {p,q} по переменным {х1,...,хп}, где f=p+q, причем р есть симметричная часть, q — остаток;
• SymmetricReduction [f, {xl,...,xn}, {s1,..., sn} ] — возвращает часть полинома (p,q) попеременным {xl, ...,xn}, где элементарный симметричный полином представляет список {s1,..., sn}.

Следующий пример поясняет создание симметричного полинома 4-й степени по переменным {х,у, z,w,t}:

<<Algebra` SymmetricPolynomials`

SyiranetricPolynomial[{x, y, z, w, t}, 4]

twxy+ twxz+ twyz+txyz+wxyz

Действие других функций поясняют следующие примеры:

SynraetricReduction[(х + у)^2 + (х + z)^2 + (z + у)^2, {х, у, z}]

{2 (х+у+ z)2- 2 (xy+xz+yz), 0}

SymmetricReduction[х^5 + у^5 + z^4, {х, у, z}, {s1, s2, s3}]

{s15- 5s13s2 + 5s1s22+ 5sl2s3- 5s2s3, z4-z5}

Преобразование полиномов в схему Горнера — Horner

Подпакет Horner в системе Mathematica 4 реализует хорошо известную схему вычисления полиномов — схему Горнера. При ней операции возведения в степень заменяются операциями умножения. Для этого служит функция Horner:

• Horner [poly] — устанавливает полином poly в форму Горнера;
• Horner [poly, vars] — устанавливает полином ряда переменных vars в форму Горнера.

Примеры преобразования полиномов в схему Горнера:

<<NumericalMath`Horner`

Horner[ 11 х^3 -4 х^2 + 7 х + 2 ]

2+ х (7 + х (-4 + 11х))

Horner[ а х^3 + bх^2 + с х + d, х ]

d+ х (с + х (b + ах))

Horner[ х^(1/3) + х + х^(3/2) ]

Схема Горнера может использоваться и для отношения полиномов:

Horner [polyl/poly2] и Horner [polyl/poly2, varsl,vars2] .

Эти функции можно использовать для улучшенного представления аппроксимации Паде, что демонстрирует следующий пример:

<<Calculus ` Fade`

approx = Padef Exp[Log[x] -х] , {х, 0, 3, 2}]]

Horner[ approx ]

Переход к схеме Горнера дает ряд преимуществ перед обычным вычислением полиномов: уменьшается время вычислений, повышается их точность, уменьшается вероятность расхождения численных методов, в которых используются полиномы. В системе Mathematica 3 подпакет Corner находился в пакете расширения NumberMath, что было не вполне логично.