AngouriMath

Symbolics for .NET


Table of contents

AngouriMath

Navigation
Home Quick start Wiki Almanac Research What's new Try Use Angouri.org GitHub Report a bug Donate Contacts

PrimeFieldPolynomial

← Back to list of classes

Description

Summary

A univariate polynomial over the prime field F_p, stored densely as its
coefficients with the constant term first.

Remarks

The point of a prime field is that it is a field with no growth in it. Over the
rationals the Euclidean algorithm is unusable directly because the coefficients of
the remainder sequence explode — which is why PolynomialGcd has to
carry the whole subresultant apparatus. Here every coefficient is one machine word
no matter how long the computation runs, so the textbook algorithms are the ones
that are actually used: plain Euclid for the greatest common divisor, plain long
division, square-and-multiply for powers.
 That is what makes the field the working surface for factorisation. A polynomial
over the integers is factored by factoring it modulo a prime, where the problem is
finite, and lifting the result back — von zur Gathen and Gerhard,
Modern Computer Algebra, ch. 14, and Knuth, TAOCP vol. 2, §4.6.2.
PrimeFieldFactorization is the first half of that.
 Arithmetic is Int64 throughout, and every product of two reduced
coefficients has to fit without overflow. A reduced coefficient is at most
p - 1, an accumulator holds at most another p - 1 before the next
reduction, so the largest intermediate is p(p - 1) and the field is bounded
by MaxPrime accordingly. Nothing here uses a wider type, because
factorisation moduli are three digits and paying EInteger for them on
the inner loop would be the wrong trade.
 Instances are immutable, and the coefficient array of a live instance is never
written to after construction; the operations all build a fresh array. That is what
lets Coefficients hand the array out rather than copying it.
 The modulus is required to be prime and this does not check it, because a check
costs O(sqrt p) on every construction and every caller inside the library
knows its own modulus. Where a composite one does reach the arithmetic it surfaces
as a failure to invert rather than as a wrong answer, and
Factor(AngouriMath.Functions.PrimeFieldPolynomial) — the one entry point a modulus could
arrive at from outside — checks primality itself.

Members

























Angouri © 2019-2023 · Project's repo · Site's repo · Octicons · Transparency · 4378 pages online