7. Расширение в теории чисел — пакет NumberTheory

Расширение в теории чисел

Мы уже описывали уникальные возможности систем Mathematica 3/4 в области обработки чисел и численных вычислений. Эти возможности существенно расширяет пакет NumberTheory, содержащий функции, реализующие алгоритмы теории чисел. Данный раздел посвящен знакомству с этим пакетом.

Цепные дроби — ContinuedFractions

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

• ContinuedFraction [х] — возвращает цепную дробь для рационального числа х;
• ContinuedFraction [х, n] — возвращает цепную дробь для числа х с числом членов п;
• ContinuedFractionForm [{а0, al,...}] — создает цепную дробь из списка {a0,al,...};
• Normal [ContinuedFractionForm[ {а0, al,...}]] — представление в нормальной форме.

Примеры разложения чисел на цепные дроби:

<<NumberTheory`

ContinuedFractionss ContinuedFraction[123/1234]//ContinuedFractionForm

ContinuedFraction[Sqrt[5], 10]//ContinuedFractionForm 2,

ContinuedFraction[GoldenRatio, 6 ] //ContinuedFractionForm

Table[ Normal[ContinuedFractionForm[Table[1, {n}]]], {n, 9}]

%- N[GoldenRatio]

{-0.618034, 0.381966, -0.118034, 0.0486327,

-0.018034, 0.00696601, -0.00264937, 0.00101363,-0.00038693}

В подпакете имеются также следующие функции:

• ToPeriodicForm[x] — дает десятичное представление для рациональнЪго числа 0 < х < 1;
• ToPeriodicForm [х, b] — дает представление рационального числа х числом с основанием b;
• PeriodicForm[ {а0,...}, {am,...}] — дает периодическую форму представления списков;
• PeriodicForm[ {а0,...}, {am,...},b] — дает периодическую форму представления списков с основанием b;
• Normal [ PeriodicForm [{а0,...}, {am,...}]] — преобразование в нормальную форму;
• Normal [PeriodicForm[ {а0,...}, {am,...} ,b] ] — преобразование в нормальную форму с основанием b.

Ниже представлены примеры применения этих функций:

ToPeriodicForm[ 1/50 ]

0.02

ToPeriodicForm[ 1/23 ]

0.0434782608695652173913

PeriodicForm[1,2,3,4]

0.1234

RealDigits[ N[ 1/23, 25 ] ]

{{4, 3, 4, 7, 8, 2, 6,

0, 8, 6, 9, 5, 6, 5, 2, 1, 7, 3, 9, 1, 3, 0, 4, 3, 5},

-1}

ToPeriodicForm[ 1/20, 2 ]

0.000011 ToPeriodicForm[ 1/127 ]

0.007874015748631496062992l2598425l968503937

Normal[%]

1/127

В системе Mathematica 4 функция ContinuedFraction стала встроенной. Имеется также встроенная функция FromContinuedFraction [list], которая строит цепную дробь по элементам списка list.

Улучшенное разложение на простые множители — FactorlntegerECM

Алгоритм разложения чисел на простые множители, реализованный в ядре Mathematiica 3, способен за 3 часа (на рабочих станциях) разлагать числа, имеющие до 18 цифр. Улучшенный алгоритм в подпакете FactorlntegerECM позволяет увеличить максимальное число цифр до 40. Реализуется разложение следующей функцией:

• FactorIntegerECM[n] — возвращает один из делителей числа п. Возможны опции FactorSize->q, CurveNumber->b и CurveCountLimit->c.

Примеры применения этой функции:

<<NumberTheory`FactorlntegerECM`

FactorIntegerECM[123456789]

34227

3*5*7*9

945

FactorlntegerECM[945]

189

Функции теории чисел — NumberTheory Functions

В подпакете NumberTheoryFunctions имеется ряд функций, относящихся к теории чисел:

• SquareFreeQ[n] — дает True, если п не имеет квадратичного фактора, и False в ином случае;
• NextPrime [n] — дает наименьшее простое число, превосходящее п;
• ChineseRemainderTheorem[listl, Iist2.] — дает наименьшее неотрицательное целое г, такое что Mod [r, Iist2] ==list1;
• SqrtMod [d, n] — дает квадратный корень из (d mod п) для нечетного n;
• PrimitiveRoot [n] — дает примитивный корень п;
• QuadraticRepresentation [d, n] — дает решение {х,у} для уравнения х ² + (d у) ² ==п для нечетного п и положительного d;
• ClassList[d] — дает список неэквивалентных квадратичных форм дискриминанта d для отрицательного и свободного от квадратов целого d вида 4n+1;
• ClassNumber [d] — дает список неэквивалентных квадратичных форм дискриминанта d;
• SumOf Squares [d, n] — дает число представлений целого числа п в виде суммы d квадратов;
• SumOf SquaresRepresentations [d, n] — дает список представлений целого числа п в виде суммы d квадратов, игнорируя порядок и знаки.

Примеры применения данных функций приведены ниже:

<<NumberTheory`NumberTheoryFunctions`

SquareFreeQ[2*3*5*7]

True SquareFreeQ[50]

False

NextPrime[1000000]

1000003

ChineseRemainderTheorem[{0, 1, 2}, {4, 9,

244

ChineseRemainderTheorem[Range[16], Prime[Range[16]]]

20037783573808880093

SqrtMod[3, 11]

5

SqrtMod[2, 10^64 +57]

876504467496681643735926111996

54610040103361197677707490912

2865

PrimitiveRoot[7]

3

QuadraticRepresentation[l, 13]

{3,. 2}

ClassList[-19]

{{1, 1, 5}}

ClassNumber[-10099]

25

SumOfSquaresRepresentations[3, 100]

{{0, 0, 10}, (0, 6, 8}}

Работа с простыми числами-PrimeQ

В подпакете PrimeQ в дополнение к функции ядра PrimeQ [n] имеется ряд функций для работы с простыми числами:

• ProvablePrimeQ [n] — возвращает True, если п проверено на простоту, и False в ином случае;
• PrimeQCertif icate [n] — возвращает сертификат о том, что n— простое или композитное число;
• ProvablePrimeQ [n, Certif icate->True] — возвращает сертификат, который может использоваться для проверки чисел на простоту;
• PrimeQCertif icateCheck [check, n] — проверяет, удостоверяет ли сертификат check простоту или композитность п.

Следующие примеры показывают работу с простыми числами:

<<NumberTheory` PrimeQ`

PrimeQ[127]

True

ProvablePrimeQ[127]

True

PrimeQCertificate[127]

{127, 3, {2, {3, 2, {2}.}, {7, 3, {2, {3, 2, {2}}}}}}

ProvablePrimeQ[127, Certificate->True]

(True, {127, 3, {2, {3, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}}}}

PrimeQCertificate[3511, SmallPrime -> 1000]

{{CertificatePrime -> 3511,

CertificatePoint->PointEC[2, 2467, 1447, 2135, 3511], Certif icateK-> 32, Certif icateM -> 3424,

CertificateNextPrime -*107, CertificateDiscriminant -> -7},

107, 2, {2, {53, 2, {2, {13, 2, {2, {3, 2, {2}}}}}}}}

Вычисление примитивных элементов — Primitive Element

Подпакет PrimitiveElement содержит всего одну функцию для вычисления примитивных элементов множественного алгебраического выражения:

• PrimitiveElement [z, {а1„а2,...} ] — возвращает список {b, { f1, f2,...}}, где b — примитивный элемент расширения рациональных алгебраических чисел al, а2,... и f1, f 2,... — полином переменной z, представляющей al, a2, ... как термы примитивного элемента.

Ее действие видно из следующего примера:

<<NumberTheory`PrimitiveElement`

PrimitiveElement[z, {Sqrt[2], Sqrt[3]}]

RootReduce[%[[2]] /. z -> %[[1]]]

Создание рядов Рамануджанат-Дирихле — Ramanujan

В подпакете Ramanujan определены следующие функции:

• RamanujanTau [n] — n-й коэффициент ряда Рамануджана т-Дирйхле (т _n );
• RamanujanTauGeneratingFunction [z] — производящая функция ряда Рамануджана т-Дирихле;
• RamanujanTauDirichletSeries [s] — ряд Рамануджана т-Дирихле f(s);
• RamanujanTauTheta [t] — функция Рамануджана т-Дирихле o(t)
• RamanujanTauZ [t] — функция Рамануджана т-Дирихле z(t).

Это довольно редкие функции, представляющие интерес для специалистов в теории чисел. Достаточно подробные их определения даны в справочной базе данных. Ограничимся приведением примеров их использования:

<<NumberTheory`Ramanujan`

RamanujanTau[5]

4830

Sum[RamanujanTau[n] z^n, {n, 5}]

z - 24 z2 + 252 z3 - 1472 z4 + 4830 z5

RamanujanTauGeneratingFunction[. 1]

0.00610209

RamanuJanTauGeneratingFunction[.99]

4.10287803703 x -1673

RamanujanTauDirichletSeries[6 + 9.221]

0.00040309-0.002390131

z = RamanujanTauZ[9.22]

0.00242388

theta = RamanujanTauTheta[9.22]

1.40372043366323 z Exp[-I theta]

0.00040309 - 0.00239013 I

Рационализация чисел — Rationalize

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

• ProjectiveRationalize [ {х0, xl,..., хn} ] — возвращает список целых чисел, дающих рациональные представления для чисел заданного списка;
• ProjectiveRationalize [ {х0, xl,..., хn} ,ргес] — возвращает список целых чисел, дающих рациональные представления с погрешностью не более 10- ^рreк
• Af f ineRationalize [ {х0, xl,..., хn} ] — возвращает список рациональных приближений для чисел заданного списка;
• Aff ineRationalize [ {х0, xl,..., xn} ,prec] — возвращает список рациональных приближений для чисел заданного списка, вычисленных с погрешностью не более 10- ^ргес .

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

<<NumberTheory` Rationalize`

Rationalize[N[3 Pi], 6]/ Rationalize[N[11 Pi], 6]

9/35

ProjectiveRationalize[{N[3 Pi], N[11 Pi]}]

{3, 11}

AffineRationalize[{N[3 Pi], N[11 Pi]}, 6]

{1065/113, 3905/113 }

Нахождение полинома, дающего заданный корень — Recognize

Подпакет Recognize содержит определение одноименной с ним функции в двух формах:

• Recognize [x,n,t] — находит полином переменной t степени, большей п, такой, что х является его корнем;
• Recognize [х, n, t, k] — находит полином переменной t степени, большей п, такой, что х является его корнем, и со штрафным весовым коэффициентом k, предназначенным для подавления генерации полиномов высших степеней.

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

<<NumberTheory`Recognize`

NSolve[2 x^3- x + 5 == 0]

{{x->-1.4797}, {x-> 0.739852-1.068711}-,

{x->0.739852+ 1.068711}}

sol = First[x /. %]

-1.4797

Recognize[sol, 3, t]

5-t+2t3

Recognize[sol, 2, t]

-225599 - 1464961 + 4032 t2

Recognize[N[Sqrt[3^(2/5)]], 5, t]

-3+t5

Recognize[N[Sqrt[3A(2/5)]], 5, t, 10]

-14625 + 11193 t + 328 t2 + 8813 + t4

Тета-функция Зигеля

Подпакет SiegelTheta содержит еще одну редкую функцию:

• SiegelTheta [z, s] — возвращает значение тета-функции Зигеля Q(Z, s).

Примеры вычисления этой функции даны ниже:

<< NumberTheory` SiegelTheta`

SiegelTheta[{1+1,2+1}, {2+1,-1+41}, {1.2, 2.3+.3I}]

0.973715-0.0002970481

Sum[E^(Pi I {tl,t2}.{ {1+1,2+1}, {2+1, -1+41} }.{tl,,t2} +

2 Pi I {tl,t2}.{l.2,2.3+.31}), {tl,-10,10>, {t2,-10,10}]

0.973715 - 0.000297048 I

В заключительной части этого примера дано вычисление тета-функции Зигеля по ее исходному определению.