scientific article; zbMATH DE number 1296282

zbMath0936.11069MaRDI QIDQ4248250

Jürgen Gerhard, Joachim von zur Gathen

Publication date: 7 June 1999

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

interpolationcomplexityGröbner basesfactorization of polynomials over finite fieldscryptographycomputer algebrasymbolic integrationfactorization of integersEuclidean algorithmprimality testssymbolic summationfast Fourier transform algorithmresultant computationRSA methodasymptotic cost of algorithmsasymptotically fast methodsHensel lifting lemmaLLL methodmodular calculus

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Number-theoretic algorithms; complexity (11Y16) Polynomials, factorization in commutative rings (13P05) Factorization (11Y05) Primality (11Y11) Computational number theory (11Yxx)

Related Items

On the computation of rational points of a hypersurface over a finite field, High-order lifting and integrality certification, Efficient data mappings for parity-declustered data layouts, A New Algorithm for Decoding Reed-Solomon Codes, Batched Point Location in SINR Diagrams via Algebraic Tools, BALANCED DENSE POLYNOMIAL MULTIPLICATION ON MULTI-CORES, EFFICIENT ALGORITHMS FOR THE BASIS OF FINITE ABELIAN GROUPS, Sparse polynomial interpolation based on diversification, Unnamed Item, Inversion Modulo Zero-Dimensional Regular Chains, 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, Certified dense linear system solving, Deterministic distinct-degree factorization of polynomials over finite fields, Sparser Johnson-Lindenstrauss Transforms, Quotients of polynomial rings and regular \(t\)-balanced Cayley maps on abelian groups, Real closures of models of weak arithmetic, Symbolic computations of first integrals for polynomial vector fields, On the computation of rational solutions of underdetermined systems over a finite field, Montgomery Residue Representation Fault-Tolerant Computation in GF(2 k ), 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, Zero-nonzero and real-nonreal sign determination, Computing cardinalities of -curve reductions over finite fields, ENERGY-AWARE STAGE ILLUMINATION, On deterministic sketching and streaming for sparse recovery and norm estimation, Parallel computation of real solving bivariate polynomial systems by zero-matching method, 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, An Algorithm for Computing a Basis of a Finite Abelian Group, Usage of modular techniques for efficient computation of ideal operations, A note on Gröbner bases and Berlekamp's algorithm, A fast parallel sparse polynomial GCD algorithm, Symbolic analysis of multiple steady states in a MAPK chemical reaction network, Drinfeld modules with complex multiplication, Hasse invariants and factoring polynomials over finite fields, Elimination for generic sparse polynomial systems, Change of order for regular chains in positive dimension, On the length of integers in telescopers for proper hypergeometric terms, From approximate factorization to root isolation with application to cylindrical algebraic decomposition, Fast algorithms for computing isogenies between elliptic curves, On irreducible divisors of iterated polynomials, Gaussian laws for the main parameters of the Euclid algorithms, Deterministic normal position transformation and its applications, Faà di Bruno's formula, lattices, and partitions, 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., Efficient CM-constructions of elliptic curves over finite fields, On the complexity of the resolvent representation of some prime differential ideals, Efficient construction of maximal and minimal representations of motifs of a string, 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, Complexity bounds on Semaev's naive index calculus method for ECDLP, Efficient algorithms for computing rational first integrals and Darboux polynomials of planar polynomial vector fields, Exact, efficient, and complete arrangement computation for cubic curves, Computing periods of rational integrals, Building counterexamples to generalizations for rational functions of Ritt's decomposition theorem, The complexity and depth of Boolean circuits for multiplication and inversion in some fields \(\mathrm{GF}(2^{n})\), Dynamical irreducibility of polynomials modulo primes, Bit Security of the CDH Problems over Finite Fields, Two efficient algorithms for the computation of ideal sums in quadratic orders, Factorization patterns on nonlinear families of univariate polynomials over a finite field, Computations with classical and p-adic modular forms, 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, Automatic Calculation of Plane Loci Using Gröbner Bases and Integration into a Dynamic Geometry System, The Mixed Binary Euclid Algorithm, Some Related Functions to Integer GCD and Coprimality, 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, On the complexity of torus knot recognition, On the linear complexity profile of nonlinear congruential pseudorandom number generators of higher orders, 2-adic point counting on \(K3\) surfaces, An exact and efficient approach for computing a cell in an arrangement of quadrics, The enumerability of P collapses P to NC, Point compression for the trace zero subgroup over a small degree extension field, A Recursive Method for Computing Zeta Functions of Varieties, 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\)], Chinese remainder theorem for cyclotomic polynomials in \(\mathbb Z[X\)], Efficient sampling of non-strict turnstile data streams, Polynomial-time algorithms for quadratic isomorphism of polynomials: the regular case, Computing discrete logarithms in the Jacobian of high-genus hyperelliptic curves over even characteristic finite fields, The Rabin cryptosystem revisited, Locating the closest singularity in a polynomial homotopy, Equivalence of polynomial identity testing and polynomial factorization, Arithmetic complexity of certain linear transformations, Computing Class Polynomials for Abelian Surfaces, Polynomial factorization over ${\mathbb F}_2$, On the number of solutions of systems of certain diagonal equations over finite fields, The arithmetic computational complexity of linear transforms, Bounds for polynomials on algebraic numbers and application to curve topology, 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, Affine equivalences of trigonometric curves, On division polynomial PIT and supersingularity, Factors of low individual degree polynomials, Fast operations on linearized polynomials and their applications in coding theory, Jebelean-Weber's algorithm without spurious factors, Blending implicit interval curves and surfaces, Multivariate subresultants in roots, 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, Modular composition modulo triangular sets and applications, Computing modular Galois representations, Symbolic-numerical solution of systems of linear ordinary differential equations with required accuracy, Linear recurrent sequences and polynomial roots, Index calculus in the trace zero variety, Sparse resultants and straight-line programs, Computing isolated roots of sparse polynomial systems in affine space, Genus 2 point counting over prime fields, An elementary approach to subresultants theory., Subresultants revisited., On lattice reduction for polynomial matrices, The orbit problem is in the GapL hierarchy, Incorporating decision procedures in implicit induction., Fast arithmetics in Artin-Schreier towers over finite fields, Polynomial algebra for Birkhoff interpolants, Sparse interpolation of multivariate rational functions, A note on Gao's algorithm for polynomial factorization, Complexity bounds for the rational Newton-Puiseux algorithm over finite fields, Algebraic osculation and application to factorization of sparse polynomials, On computation of the greatest common divisor of several polynomials over a finite field., Algorithms for combinatorial structures: well-founded systems and Newton iterations, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., 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, A probabilistic symbolic algorithm to find the minimum of a polynomial function on a basic closed semialgebraic set, Redundancy of minimal weight expansions in Pisot bases, Good reduction of Puiseux series and applications, Bit-size estimates for triangular sets in positive dimension, Efficient decomposition of separable algebras., Fast rectangular matrix multiplication and some applications, Sparse bivariate polynomial factorization, The complexity of computing all subfields of an algebraic number field, Algorithms for weighted sum of squares decomposition of non-negative univariate polynomials, Root refinement for real polynomials using quadratic interval refinement, On the bit complexity of polynomial system solving, A new method to compute the singularities of offsets to rational plane curves, Primality testing with Gaussian periods, Improving the topology computation of an arrangement of cubics, Rational solutions of ordinary difference equations, On the \(q\)th power algorithm, Indefinite summation of rational functions with factorization of denominators, On multivariate rational function decomposition, Irreducible decomposition of curves, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Simultaneous modular reduction and Kronecker substitution for small finite fields, Essentially optimal computation of the inverse of generic polynomial matrices, 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, Computability in linear algebra, On the complexities of multipoint evaluation and interpolation, On sign conditions over real multivariate polynomials, Topics in computational algebraic number theory, A parametric representation of totally mixed Nash equilibria, Determining the closed forms of the anomalous dimensions and Wilson coefficients from Mellin moments by means of computer algebra, Fast computation of Hermite normal forms of random integer matrices, Probabilistic algorithms for computing resolvent representations of regular differential ideals, A geometric index reduction method for implicit systems of differential algebraic equations, A simple and fast algorithm for computing exponentials of power series, Using symmetries in the eigenvalue method for polynomial systems, Topology and arrangement computation of semi-algebraic planar curves, A \(p\)-adic algorithm for computing the inverse of integer matrices, Probabilistic algorithm for finding roots of linearized polynomials, An algorithm for implicit interpolation, 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, A worst-case bound for topology computation of algebraic curves, Factoring polynomials over global fields, Computing differential characteristic sets by change of ordering, Computing zeta functions of Artin-Schreier curves over finite fields. II, Classical and quantum function reconstruction via character evaluation, Fast conversion algorithms for orthogonal polynomials, 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, Modular polynomials on Hilbert surfaces, Computer algebra and algebraic geometry -- achievements and perspectives, Computing rational forms of integer matrices, Linear differential operators for polynomial equations, Relax, but don't be too lazy, Average-case complexity of the Euclidean algorithm with a fixed polynomial over a finite field, 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, Skew-polynomial-sparse matrix multiplication, Isolating all the real roots of a mixed trigonometric-polynomial, Elimination ideal and bivariate resultant over finite fields, Faster integer multiplication using short lattice vectors, Unnamed Item, Computing isomorphisms and embeddings of finite fields, Fast integer multiplication using generalized Fermat primes, Additive decompositions of polynomials over unique factorization domains, 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, Counting Points in Medium Characteristic Using Kedlaya's Algorithm, Galois group computation for rational polynomials, Factoring polynomials over finite fields: A survey, On modular inverses of cyclotomic polynomials and the magnitude of their coefficients, An application of the method of additive chains to inversion in finite fields, The complete generating function for Gessel walks is algebraic, On the Complexity of the Montes Ideal Factorization Algorithm, Fat Fisher zeroes, The van Hoeij Algorithm for Factoring Polynomials, Factoring polynomials over local 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, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Algorithms for Function Fields, EVALUATION PROPERTIES OF SYMMETRIC POLYNOMIALS, Unnamed Item, Unnamed Item, On the Design and Optimization of a Quantum Polynomial-Time Attack on Elliptic Curve Cryptography, Symbolic Computation Software Composability, Unnamed Item, Unnamed Item