Modern Computer Algebra
From MaRDI portal
Publication:2862994
DOI10.1017/CBO9781139856065zbMath1277.68002MaRDI QIDQ2862994
Jürgen Gerhard, Joachim von zur Gathen
Publication date: 20 November 2013
complexitydiscrete mathematicscomputer algebramathematical softwarecomputational geometryalgorithmicsinformation theory and coding
Symbolic computation and algebraic computation (68W30) Combinatorics in computer science (68R05) Cryptography (94A60) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Factorization (11Y05) Primality (11Y11) Computational aspects and applications of commutative rings (13Pxx)
Related Items
Sum of Squares Decompositions of Polynomials over their Gradient Ideals with Rational Coefficients, Making Presentation Math Computable: Proposing a Context Sensitive Approach for Translating LaTeX to Computer Algebra Systems, Implementing the Tangent Graeffe Root Finding Method, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Computing minimal interpolation bases, The algebro-geometric method: Solving algebraic differential equations by parametrizations, A novel approach to integration by parts reduction, Finding elliptic curves with a subgroup of prescribed size, Polynomial Multiplication over Finite Fields in Time \( O(n \log n \), A Framework for Adversarially Robust Streaming Algorithms, Invariant Bilinear Forms on W-Graph Representations and Linear Algebra Over Integral Domains, Factorization of ℤ$$ \mathbb {Z}$$-Homogeneous Polynomials in the First q-Weyl Algebra, A log-log speedup for exponent one-fifth deterministic integer factorisation, Upper bounds on the heights of polynomials and rational fractions from their values, Certifying solutions to overdetermined and singular polynomial systems over \(\mathbb{Q}\), A unified approach to the Galois closure problem, On the complexity exponent of polynomial system solving, Integer multiplication in time \(O(n\log n)\), Fast and Simple Modular Interpolation Using Factorial Representation, On rational functions without Froissart doublets, Efficient RKA-Secure KEM and IBE Schemes Against Invertible Functions, Bounded Treewidth and Space-Efficient Linear Algebra, Fast computation of the \(N\)-th term of a \(q\)-holonomic sequence and applications, Parallelization of triangular decompositions: techniques and implementation, \texttt{PTOPO}: computing the geometry and the topology of parametric curves, Chordal Networks of Polynomial Ideals, On Matrices With Displacement Structure: Generalized Operators and Faster Algorithms, Fast Algorithms for Discrete Differential Equations, A New Black Box Factorization Algorithm - the Non-monic Case, New Sparse Multivariate Polynomial Factorization Algorithms over Integers, Algorithm for Connectivity Queries on Real Algebraic Curves, Improved complexity bounds for counting points on hyperelliptic curves, Flip Graphs for Matrix Multiplication, Computing the Characteristic Polynomial of Endomorphisms of a finite Drinfeld Module using Crystalline Cohomology, SLRA Interpolation for Approximate GCD of Several Multivariate Polynomials, p-adic algorithm for bivariate Gröbner bases, Efficient Generic Quotients Using Exact Arithmetic, A direct key recovery attack on SIDH, Factoring multivariate polynomials represented by black boxes: a Maple + C implementation, Affine Cartesian codes with complementary duals, Orienteering with one endomorphism, Fast systematic encoding of multiplicity codes, Algebraic algorithms for variants of subset sum, A quantum version of Pollard's Rho of which Shor's algorithm is a particular case, Deterministic factoring with oracles, Univariate polynomial factorization over finite fields with large extension degree, Chosen-ciphertext secure code-based threshold public key encryptions with short ciphertext, Improved straight-line extraction in the random oracle model with applications to signature aggregation, Improving bounds on elliptic curve hidden number problem for ECDH key exchange, Computers as a novel mathematical reality. II: Waring's problem, High-order lifting for polynomial Sylvester matrices, Integral reduction with Kira 2.0 and finite field methods, Interpolation of dense and sparse rational functions and other improvements in \texttt{FireFly}, Counting points on genus-3 hyperelliptic curves with explicit real multiplication, Fast Jacobian arithmetic for hyperelliptic curves of genus 3, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Balancing act: multivariate rational reconstruction for IBP, A fast randomized geometric algorithm for computing Riemann-Roch spaces, Succinct Diophantine-satisfiability arguments, An algebraic attack on ciphers with low-degree round functions: application to full MiMC, The equivariant complexity of multiplication in finite field extensions, Unnamed Item, Compositions and collisions at degree \(p^2\), Reconstructing rational functions with \texttt{FireFly}, Univariate Real Root Isolation over a Single Logarithmic Extension of Real Algebraic Numbers, Fast matrix multiplication and its algebraic neighbourhood, Enumeration of labelled 4-regular planar graphs. II: Asymptotics, An improved method for predicting truncated multiple recursive generators with unknown parameters, Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms, Barriers for Rank Methods in Arithmetic Complexity, Differential Privacy on Finite Computers, Jacobian Versus Infrastructure in Split Hyperelliptic Curves, Sato-Tate distributions, ZERO BIFURCATION DIAGRAMS FOR ABELIAN INTEGRALS: A STUDY ON HIGHER-ORDER HYPERELLIPTIC HAMILTONIAN SYSTEMS WITH THREE PERTURBATION PARAMETERS, Faster integer multiplication using plain vanilla FFT primes, Unnamed Item, Method for finding multiple roots of polynomials, AND–Decomposition of Boolean Polynomials with Prescribed Shared Variables, Fast Hermite interpolation and evaluation over finite fields of characteristic two, The complexity of sparse Hensel lifting and sparse polynomial factorization, An exponent one-fifth algorithm for deterministic integer factorisation, Unnamed Item, Integer Version of Ring-LWE and Its Applications, Computing approximate greatest common right divisors of differential polynomials, Randomized polynomial-time root counting in prime power rings, Minimal solutions of the rational interpolation problem, Character sums and deterministic polynomial root finding in finite fields, A theoretical investigation of the frisbee motion of red blood cells in shear flow, Counting points on hyperelliptic curves of genus 2 with real models, Counting points on superelliptic curves in average polynomial time, Unnamed Item, Accelerated tower arithmetic, Ideals Generated by Differential Equations, A Generalised Successive Resultants Algorithm, Automated Teaching System “Sets” (Research for Organizing the 1st Part of the Project), Computing 𝐿-polynomials of Picard curves from Cartier–Manin matrices, The multiple number field sieve for medium- and high-characteristic finite fields, Computing Hasse–Witt matrices of hyperelliptic curves in average polynomial time, Non-autonomous multidimensional Toda system and multiple interpolation problem, Segre-driven radicality testing, \textsf{Bingo}: adaptivity and asynchrony in verifiable secret sharing and distributed key generation, Computing the binomial part of a polynomial ideal, Analysis of periodic linear systems over finite fields with and without Floquet transform, A quantitative study of fork-join processes with non-deterministic choice: application to the statistical exploration of the state-space, Efficient rational creative telescoping, A unified FFT-based approach to maximum assignment problems related to transitive finite group actions, Smoothness test for polynomials defined over small characteristic finite fields, Polynomial-exponential decomposition from moments, Computational schemes for subresultant chains, Decoupling multivariate fractions, Interpolation cryptanalysis of unbalanced Feistel networks with low degree round functions, Fast exact algorithms using Hadamard product of polynomials, A certified program for the Karatsuba method to multiply polynomials, Generalized quasi-cyclic codes with arbitrary block lengths, Algebraic independence over positive characteristic: new criterion and applications to locally low-algebraic-rank circuits, Algorithmic issues of AND-decomposition of Boolean formulas, Even faster integer multiplication, Solving bivariate systems using rational univariate representations, Computing zero-dimensional tropical varieties via projections, A quasi-linear irreducibility test in \(\mathbb{K}x[y\)], Moduli-friendly Eisenstein series over the \(p\)-adics and the computation of modular Galois representations, Quantum compression relative to a set of measurements, A fast algorithm for computing the number of magic series, Sparse polynomial interpolation based on derivatives, Construction and number of self-dual skew codes over \(\mathbb{F}_{p^2}\), Artin-Schreier extensions of normal bases, Stabilization bounds for linear finite dynamical systems, Root repulsion and faster solving for very sparse polynomials over \(p\)-adic fields, Computing Riemann-Roch spaces via Puiseux expansions, Computing the topology of a plane or space hyperelliptic curve, The complexity of AND-decomposition of Boolean functions, The set of unattainable points for the rational Hermite interpolation problem, Normal bases from 1-dimensional algebraic groups, Subresultants of \((x-\alpha)^m\) and \((x-\beta)^n\), Jacobi polynomials and complexity, Faster interpolation algorithms for sparse multivariate polynomials given by straight-line programs, Directed evaluation, Nearly optimal refinement of real roots of a univariate polynomial, On the complexity of inverting integer and polynomial matrices, Algorithms for simultaneous Hermite-Padé approximations, Algorithms for commutative algebras over the rational numbers, Polynomial interpolation and identity testing from high powers over finite fields, Formalizing the LLL basis reduction algorithm and the LLL factorization algorithm in Isabelle/HOL, MathPartner computer algebra, Algorithm for constructing an analog of Plan's formula, Algorithm for constructing an analogue of the Binet formula, Low-rank parity-check codes over Galois rings, Relaxed Hensel lifting of triangular sets, Using symmetries in the index calculus for elliptic curves discrete logarithm, Computing the multilinear factors of lacunary polynomials without heights, Deterministic computation of the characteristic polynomial in the time of matrix multiplication, A verified implementation of the Berlekamp-Zassenhaus factorization algorithm, Efficient computation of the characteristic polynomial of a threshold graph, Constructing dominating sets in circulant graphs, Left-invariant Einstein metrics on \(S^3 \times S^3\), Bivariate triangular decompositions in the presence of asymptotes, The polynomial approximate common divisor problem and its application to the fully homomorphic encryption, On degrees of modular common divisors and the big prime gcd algorithm, A nearly optimal algorithm to decompose binary forms, Multilinear polynomial systems: root isolation and bit complexity, Verification protocols with sub-linear communication for polynomial matrix operations, Counting invariant subspaces and decompositions of additive polynomials, Counting points on hyperelliptic curves of type \(y^2=x^{2g+1}+ax^{g+1}+bx\), Fast computation of generic bivariate resultants, On the complexity of the Lickteig-Roy subresultant algorithm, On the complexity of computing with planar algebraic curves, Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants, Faster polynomial multiplication over finite fields using cyclotomic coefficient rings, Computing the equisingularity type of a pseudo-irreducible polynomial, All hyperbolic Coxeter \(n\)-cubes, A first step towards the skew duadic codes, Factorization of Boolean polynomials: parallel algorithms and experimental evaluation, An algorithm for constructing the resultant of two entire functions, Modular composition via factorization, Efficient \(q\)-integer linear decomposition of multivariate polynomials, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, Mechanisation of the AKS algorithm, Fast multivariate multi-point evaluation revisited, Identity testing and interpolation from high powers of polynomials of large degree over finite fields, Block-Krylov techniques in the context of sparse-FGLM algorithms, Asymptotics of 3-stack-sortable permutations, Subquadratic-time algorithms for normal bases, A probabilistic algorithm for verifying polynomial middle product in linear time, Factorizations for difference operators, Deciding multiple tiling by polygons in polynomial time, A non-local pedestrian flow model accounting for anisotropic interactions and domain boundaries, Factorization of polynomials given by arithmetic branching programs, Sampling polynomial trajectories for LTL verification, Determinisability of unary weighted automata over the rational numbers, Flexible and efficient verifiable computation on encrypted data, Extending Coggia-Couvreur attack on Loidreau's rank-metric cryptosystem, Computing Puiseux series: a fast divide and conquer algorithm, Fast computation of half-integral weight modular forms, On the problem of convexity for the restricted three-body problem around the heavy primary, A deterministic algorithm for finding \(r\)-power divisors, Polynomial modular product verification and its implications, A fast algorithm for computing the Smith normal form with multipliers for a nonsingular integer matrix, Simultaneous rational function reconstruction with errors: handling multiplicities and poles, Counting points on smooth plane quartics, Kira -- a Feynman integral reduction program, An improved condition for a graph to be determined by its generalized spectrum, Subresultant chains using Bézout matrices, An interpolation algorithm for computing Dixon resultants
