Complexity questions in number theory

DOI10.1007/BF02104748zbMath0566.10001OpenAlexW2021335023MaRDI QIDQ1059094

M. A. Frumkin

Publication date: 1985

Published in: Journal of Soviet Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf02104748

zbMATH Keywords

computational complexitybibliographyopen problemslinear diophantine equationscomputational number theorycontinued fraction algorithmquadratic diophantine equationsdiophantine inequalitiesdiophantine approximationsalgorithms in number theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quadratic and bilinear Diophantine equations (11D09) Research exposition (monographs, survey articles) pertaining to number theory (11-02) Continued fractions and generalizations (11J70) Diophantine inequalities (11D75) Radix representation; digital problems (11A63)

Related Items

On random nonsingular Hermite normal form ⋮ Computing algorithms for the reduction of a Hermite algorithm with polynomial coefficients

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A generalization of the algorithm for continued fractions related to the algorithm of Viggo Brunn
• Number of natural solutions of a system of linear Diophantine equations
• Fundamental units of cubic fields of positive discriminant
• Machine-independent description of certain machine complexity classes
• Approximation properties of Jacobi's algorithm
• Explicit representations of Dirichlet approximations
• Riemann's hypothesis and tests for primality
• Using the Blankinship algorithm to find the general solution of a linear diophantine equation
• On best two-dimensional Dirichlet-approximations and their algorithmic calculation
• The metrical theory of Jacobi-Perron algorithm
• The Jacobi-Perron algorithm its theory and application
• Fast computation of continued fraction expansions.
• The least quadratic non residue
• An Introduction to the Geometry of Numbers
• On the Computational Complexity of Determining the Solvability or Unsolvability of the Equation X 2 - DY 2 = -1
• Polynomial Algorithms for Computing the Smith and Hermite Normal Forms of an Integer Matrix
• A two-dimensional continued fraction algorithm for best approximations with an application in cubic number fields.
• Every Prime Has a Succinct Certificate
• An Effective Number Geometric Method of Computing the Fundamental Units of an Algebraic Number Field
• Minkowski Reduction of Integral Matrices
• Calculating the General Solution of a Linear Diophantine Equation
• Algorithm and bound for the greatest common divisor of n integers
• A New Version of the Euclidean Algorith
• Euclid's Algorithm for Large Numbers