Publication:4248250

Joachim von zur Gathen, Jürgen Gerhard

Publication date: 7 June 1999

interpolation; complexity; Gröbner bases; factorization of polynomials over finite fields; cryptography; computer algebra; symbolic integration; factorization of integers; Euclidean algorithm; primality tests; symbolic summation; fast Fourier transform algorithm; resultant computation; RSA method; asymptotic cost of algorithms; asymptotically fast methods; Hensel lifting lemma; LLL method; modular calculus

Mathematics Subject Classification ID

68W30: Symbolic computation and algebraic computation

68-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science

11Y16: Number-theoretic algorithms; complexity

13P05: Polynomials, factorization in commutative rings

11Y05: Factorization

11Y11: Primality

11Yxx: Computational number theory

Related Items

Computing isolated roots of sparse polynomial systems in affine space, Genus 2 point counting over prime fields, Fast arithmetics in Artin-Schreier towers over finite fields, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, Algebraic osculation and application to factorization of sparse polynomials, Algorithms for combinatorial structures: well-founded systems and Newton iterations, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Simultaneous modular reduction and Kronecker substitution for small finite fields, Real solution isolation with multiplicity of zero-dimensional triangular systems, An alternative class of irreducible polynomials for optimal extension fields, An algebraic approach to continuous collision detection for ellipsoids, Gcd of multivariate polynomials via Newton polytopes, Topics in computational algebraic number theory, Distribution results for low-weight binary representations for pairs of integers, On efficient sparse integer matrix Smith normal form computations, Matrix structure and loss-resilient encoding/decoding, The orbit problem is in the GapL hierarchy, Polynomial algebra for Birkhoff interpolants, Sparse interpolation of multivariate rational functions, A note on Gao's algorithm for polynomial factorization, On coefficients of polynomials over finite fields, Homotopy techniques for multiplication modulo triangular sets, Computing the equidimensional decomposition of an algebraic closed set by means of lifting fibers, Redundancy of minimal weight expansions in Pisot bases, Good reduction of Puiseux series and applications, Bit-size estimates for triangular sets in positive dimension, On multivariate rational function decomposition, Irreducible decomposition of curves, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Computability in linear algebra, On the complexities of multipoint evaluation and interpolation, Determining the closed forms of the anomalous dimensions and Wilson coefficients from Mellin moments by means of computer algebra, A geometric index reduction method for implicit systems of differential algebraic equations, Using symmetries in the eigenvalue method for polynomial systems, Topology and arrangement computation of semi-algebraic planar curves, A worst-case bound for topology computation of algebraic curves, Jebelean-Weber's algorithm without spurious factors, Blending implicit interval curves and surfaces, Multivariate subresultants in roots, Fast rectangular matrix multiplication and some applications, Improving the topology computation of an arrangement of cubics, Rational solutions of ordinary difference equations, On the $q$th power algorithm, On sign conditions over real multivariate polynomials, A parametric representation of totally mixed Nash equilibria, Fast computation of Hermite normal forms of random integer matrices, Probabilistic algorithms for computing resolvent representations of regular differential ideals, A simple and fast algorithm for computing exponentials of power series, A $p$-adic algorithm for computing the inverse of integer matrices, Probabilistic algorithm for finding roots of linearized polynomials, Number of irreducible polynomials and pairs of relatively prime polynomials in several variables over finite fields, A parallel extended GCD algorithm, Fast algorithms for computing Jones polynomials of certain links, Linear dynamical systems over finite rings, Fast arithmetic for triangular sets: from theory to practice, Interpolation of polynomials given by straight-line programs, Deformation techniques for sparse systems, Factoring polynomials over global fields, Computing differential characteristic sets by change of ordering, Fast conversion algorithms for orthogonal polynomials, Linear recurrent sequences and polynomial roots, An elementary approach to subresultants theory., Subresultants revisited., On lattice reduction for polynomial matrices, Incorporating decision procedures in implicit induction., On computation of the greatest common divisor of several polynomials over a finite field., Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Efficient decomposition of separable algebras., Algorithms for exponentiation in finite fields, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, Computer algebra and algebraic geometry -- achievements and perspectives, Essentially optimal computation of the inverse of generic polynomial matrices, Computing zeta functions of Artin-Schreier curves over finite fields. II, Classical and quantum function reconstruction via character evaluation, Computing rational forms of integer matrices, Linear differential operators for polynomial equations, Relax, but don't be too lazy, Inversion of two level circulant matrices over $\mathbb{Z}_{p}$, Fast computation of discrete invariants associated to a differential rational mapping, Complexity results for triangular sets, High-order lifting and integrality certification, Efficient data mappings for parity-declustered data layouts, Efficient construction of maximal and minimal representations of motifs of a string, Polynomial evaluation and interpolation on special sets of points, Numeric vs. symbolic homotopy algorithms in polynomial system solving: a case study, Complexity of integer quasiconvex polynomial optimization, Simple forms of higher-order linear differential systems and their applications in computing regular solutions, Fast algorithms for computing isogenies between ordinary elliptic curves in small characteristic, Representation attacks on the Braid Diffie-Hellman public key encryption, Fast computation of special resultants, On inverse systems and squarefree decomposition of zero-dimensional polynomial ideals, An algorithm to solve integer linear systems exactly using numerical methods, A polynomial time algorithm for finding rational general solutions of first order autonomous ODEs, Polynomial root separation examples, Computation of unirational fields, Parameter choices on Guruswami-Sudan algorithm for polynomial reconstruction, A note on Gröbner bases and Berlekamp's algorithm, Change of order for regular chains in positive dimension, Gaussian laws for the main parameters of the Euclid algorithms, Faà di Bruno's formula, lattices, and partitions, Counting Points in Medium Characteristic Using Kedlaya's Algorithm, Factoring multivariate polynomials via partial differential equations, Computing special powers in finite fields, Modular equations for hyperelliptic curves, On the interpolation of bivariate polynomials related to the Diffie-Hellman mapping, The complete generating function for Gessel walks is algebraic, On the Complexity of the Montes Ideal Factorization Algorithm, The van Hoeij Algorithm for Factoring Polynomials, Fault-Tolerant Finite Field Computation in the Public Key Cryptosystems, Computing Hilbert Class Polynomials, Computing Zeta Functions in Families of C a,b Curves Using Deformation, USING GRÖBNER BASES FOR FACTORING POLYNOMIALS OVER ALGEBRAIC EXTENSION FIELDS, An application of the method of additive chains to inversion in finite fields, $\mathbf{Li}^{\boldsymbol{(p)}}$-service? An algorithm for computing $\boldsymbol{p}$-adic polylogarithms, Fast convolutions meet Montgomery, Explicit Formulas for Efficient Multiplication in $\mathbb{F}_{3^{6m}}$, Refined Noether Normalization Theorem and Sharp Degree Bounds for Dominating Morphisms, Algorithms for Function Fields, EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS, On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography, Symbolic Computation Software Composability, Galois group computation for rational polynomials, Factoring polynomials over finite fields: A survey, Fat Fisher zeroes, Factoring polynomials over local fields., Construction of explicit Runge-Kutta pairs with stiffness detection, Polynomial interpolation of cryptographic functions related to Diffie-Hellman and discrete logarithm problem, Theory of computational complexity. Part 9. Transl. from the Russian., On the complexity of the resolvent representation of some prime differential ideals, Exact, efficient, and complete arrangement computation for cubic curves, Building counterexamples to generalizations for rational functions of Ritt's decomposition theorem, On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders, An exact and efficient approach for computing a cell in an arrangement of quadrics, The enumerability of P collapses P to NC, Constructive recognition of finite alternating and symmetric groups acting as matrix groups on their natural permutation modules., Integers and polynomials: comparing the close cousins $\mathbb Z$ and $\mathbb F_q[x$], Certified dense linear system solving, Deterministic distinct-degree factorization of polynomials over finite fields, EFFICIENT ALGORITHMS FOR THE BASIS OF FINITE ABELIAN GROUPS, An Algorithm for Computing a Basis of a Finite Abelian Group, A $p$-adic algorithm to compute the Hilbert class polynomial, The complexity of class polynomial computation via floating point approximations, Computing modular polynomials in quasi-linear time, Computations with classical and p-adic modular forms, Automatic Calculation of Plane Loci Using Gröbner Bases and Integration into a Dynamic Geometry System, Polynomial factorization over ${\mathbb F}_2$, BALANCED DENSE POLYNOMIAL MULTIPLICATION ON MULTI-CORES, Two efficient algorithms for the computation of ideal sums in quadratic orders, Fast computation of a rational point of a variety over a finite field, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, A Recursive Method for Computing Zeta Functions of Varieties, Montgomery Residue Representation Fault-Tolerant Computation in GF(2 k ), ENERGY-AWARE STAGE ILLUMINATION, Fast algorithms for computing isogenies between elliptic curves, Efficient CM-constructions of elliptic curves over finite fields, An Algorithm for Symbolic Solving of Differential Equations and Estimation of Accuracy, Subquadratic Polynomial Multiplication over GF(2 m ) Using Trinomial Bases and Chinese Remaindering