Polynomial Mathematics リファレンス
リファレンス 用 polynomials: roots, factoring, interpolation, および finite フィールド operations.
Polynomial Operations
Polynomials are sums of terms a_i * x^i. Degree is the highest power with non-zero coefficient. Addition and multiplication follow standard rules; multiplication is O(n*m) naively, O(n log n) with FFT. The Fundamental Theorem of Algebra: degree-n polynomial has n complex roots (counting multiplicity). Polynomial division gives quotient and remainder (Euclidean domain). GCD of polynomials via Euclidean algorithm. Factoring over integers is hard (LLL-based for high degree). Derivatives and integrals follow power rules. Polynomial evaluation uses Horner's method for efficiency.
- degree
- Highest power
- FTA
- n roots in C
- Horner
- Efficient eval
non-zero coeffcounting multiplicityO(n) multsRoots and Interpolation
Rational root theorem finds rational roots of integer polynomials. Quadratic formula for degree 2. Cubic and quartic have formulas; quintic+ generally do not (Galois theory). Newton's method numerically approximates roots. Lagrange interpolation finds a polynomial through n+1 points in O(n^2). Newton form builds incrementally. Polynomial evaluation at multiple points uses multi-point evaluation (FFT-based). Finite field polynomials (over Fp) are central to error-correcting codes (Reed-Solomon) and secret sharing (Shamir). Polynomial commitment schemes (KZG) are used in zk-SNARKs.
- quadratic
- Degree 2 formula
- Lagrange
- Interpolate points
- finite field
- Over Fp
-b±sqrt(b^2-4ac)/2aO(n^2)Reed-Solomon, Shamir