Publication:4248250
From MaRDI portal
zbMath0936.11069MaRDI QIDQ4248250
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
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
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, 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., Counting Points in Medium Characteristic Using Kedlaya's Algorithm, Factoring multivariate polynomials via partial differential equations, Computing special powers in finite fields, 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, 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, Using symmetries in the eigenvalue method for polynomial systems, Topology and arrangement computation of semi-algebraic planar 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, 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, 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, Polynomial factorization over ${\mathbb F}_2$, 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
