Улучшенное разложение на простые множители — 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] — дает решение {х,у} для уравнения х 2 + (d у) 2 ==п для нечетного п и положительного 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}}}}}}}}

 



Содержание раздела

---

---