Solving sparse linear equations over finite fields
From MaRDI portal
Publication:3746790
DOI10.1109/TIT.1986.1057137zbMath0607.65015MaRDI QIDQ3746790
Publication date: 1986
Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)
finite fieldsrankdeterminantprobabilistic algorithmsparse systemsminimum polynomialrandom methodcoordinate recurrence method
Matrices over special rings (quaternions, finite fields, etc.) (15B33) Numerical computation of determinants (65F40) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Algorithm 1021: SPEX Left LU, Exactly Solving Sparse Linear Systems via a Sparse Left-looking Integer-preserving LU Factorization, Reduction of Huge, Sparse Matrices over Finite Fields Via Created Catastrophes, Skew-polynomial-sparse matrix multiplication, Individual discrete logarithm with sublattice reduction, Elimination ideal and bivariate resultant over finite fields, A new algebraic approach to the regular syndrome decoding problem and implications for PCG constructions, Roundoff-Error-Free Basis Updates of LU Factorizations for the Efficient Validation of Optimality Certificates, Lattice enumeration for tower NFS: a 521-bit discrete logarithm computation, On the complexity of solving generic overdetermined bilinear systems, Lattice enumeration and automorphisms for tower NFS: a 521-bit discrete logarithm computation, Foreword, Factoring polynomials over finite fields: A survey, Computation of a 768-Bit Prime Field Discrete Logarithm, Exact Solution of Sparse Linear Systems via Left-Looking Roundoff-Error-Free LU Factorization in Time Proportional to Arithmetic Work, A Brief History of Pairings, Black box linear algebra, Early termination in sparse interpolation algorithms, The space complexity analysis in the general number field sieve integer factorization, Computing discrete logarithms in cryptographically-interesting characteristic-three finite fields, A Rank Attack Against Extension Field Cancellation, The irreducibility of some level 1 Hecke polynomials, Finding succinct ordered minimal perfect hash functions, On index calculus algorithms for subfield curves, Factoring multivariate polynomials via partial differential equations, The SIAM 100-Digit Challenge: a decade later. Inspirations, ramifications, and other eddies left in its wake, Evaluation of Solving Time for Multivariate Quadratic Equation System Using XL Algorithm Over Small Finite Fields on GPU, An efficient structural attack on NIST submission DAGS, On Fast and Provably Secure Message Authentication Based on Universal Hashing, Discrete logarithms in \(\mathrm{GF}(p)\), Efficient matrix preconditioners for black box linear algebra, Certified dense linear system solving, Certified sparse linear system solving, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Algebraic and numerical techniques for the computation of matrix determinants, On efficient sparse integer matrix Smith normal form computations, Dynamic Galois theory, Univariate polynomial factorization over finite fields, Techniques for exploiting structure in matrix formulae of the sparse resultant, Quantum walks on generalized quadrangles, Implicitization of curves and (hyper)surfaces using predicted support, Accelerating Iterative SpMV for the Discrete Logarithm Problem Using GPUs, Quasi-subfield polynomials and the elliptic curve discrete logarithm problem, Index calculus in the trace zero variety, Clustered planarity testing revisited, Automating algorithm selection: checking for matrix properties that can simplify computations, Probabilistic analysis of Wiedemann's algorithm for minimal polynomial computation, Hanani-Tutte for radial planarity. II, Hanani-Tutte for Radial Planarity II, Cache Optimized Solution for Sparse Linear System over Large Order Finite Field, Improvements of algebraic attacks for solving the rank decoding and MinRank problems, Technical history of discrete logarithms in small characteristic finite fields. The road from subexponential to quasi-polynomial complexity, Solving sparse linear systems of equations over finite fields using bit-flipping algorithm, Discrete logarithm problem using index calculus method, Sparse FGLM algorithms, Computing the sign or the value of the determinant of an integer matrix, a complexity survey., Growth Functions and Automatic Groups, Computing with polynomials given by black boxes for their evaluations: greatest common divisors, factorization, separation of numerators and denominators, The index calculus method using non-smooth polynomials, On the density of normal bases in finite fields, New techniques for the computation of linear recurrence coefficients, Nearly optimal solution of rational linear systems of equations with symbolic lifting and numerical initialization, Using symmetries in the index calculus for elliptic curves discrete logarithm, An algorithm to solve integer linear systems exactly using numerical methods, Reconstructing a phylogenetic level-1 network from quartets, A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields, New results on quasi-subfield polynomials, Exact solutions to linear programming problems, Index calculus attack for Jacobian of hyperelliptic curves of small genus using two large primes, Improved agreeing-gluing algorithm, Special prime numbers and discrete logs in finite prime fields, Parametrization of Newton's iteration for computations with structured matrices and applications, Subquadratic computation of vector generating polynomials and improvement of the block Wiedemann algorithm, Kaltofen's division-free determinant algorithm differentiated for matrix adjoint computation, Improved algorithms for computing determinants and resultants, Subquadratic-time factoring of polynomials over finite fields, Cohomology of congruence subgroups of $ {SL}_4(\mathbb {Z})$. III, Factoring: algorithms, computations, and computers, Updating key size estimations for pairings, The Function Field Sieve in the Medium Prime Case, A note on the factorization method of Niederreiter, The black-box Niederreiter algorithm and its implementation over the binary field, Hanani-Tutte for approximating maps of graphs, Unnamed Item, A Rigorous Time Bound for Factoring Integers, Indiscreet logarithms in finite fields of small characteristic, A Rigorous Subexponential Algorithm For Computation of Class Groups, Block-Krylov techniques in the context of sparse-FGLM algorithms, Fast matrix decomposition in \(\mathbb F_2\), Weakness of \(\mathbb{F}_{3^{6 \cdot 1429}}\) and \(\mathbb{F}_{2^{4 \cdot 3041}}\) for discrete logarithm cryptography, Using number fields to compute logarithms in finite fields, Roundoff-Error-Free Algorithms for Solving Linear Systems via Cholesky and LU Factorizations, Решение систем линейных уравнений при вычислении логарифмов в конечном простом поле, Parallel GNFS algorithm integrated with parallel block Wiedemann algorithm for RSA security in cloud computing, Probabilistic analysis of block Wiedemann for leading invariant factors, Matrices in elimination theory, Refined analysis to the extended tower number field sieve, Density of normal elements, An Optimal Bloom Filter Replacement Based on Matrix Solving, Analysis of multivariate encryption schemes: application to Dob, Sparse Gaussian Elimination Modulo p: An Update, Extended Tower Number Field Sieve: A New Complexity for the Medium Prime Case, Measuring and computing natural generators for homology groups, Euclid’s algorithm and the Lanczos method over finite fields, Challenges of symbolic computation: My favorite open problems. With an additional open problem by Robert M. Corless and David J. Jeffrey, A new efficient algorithm for computing Gröbner bases \((F_4)\), Unnamed Item, Unnamed Item, The RCH method for computing minimal polynomials of polynomial matrices, Computing newforms using supersingular isogeny graphs, Modifications to the number field sieve, Solving linear equations over GF(2): Block Lanczos algorithm, Factorization of polynomials and some linear-algebra problems over finite fields, Parallel algorithms for matrix normal forms, Symbolic and numeric methods for exploiting structure in constructing resultant matrices, The multiple number field sieve for medium- and high-characteristic finite fields, An algebraic approach to the rank support learning problem
