Улучшенное разложение на простые множители — 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}}}}}}}}
